Il problema della fattorizzazione di un numero nei suoi fattori primi è noto fin dai
tempi di Euclide.
In particolare è noto che dato un qualsiasi numero intero positivo esiste un solo prodotto
di numeri primi uguale al numero dato. L'individuazione dei fattori di questo prodotto prende
appunto il nome di fattorizzazione.
2300 anni dopo Euclide il problema della fattorizzazione resta un problema arduo, nel senso che
non si conosce un algoritmo che sia in grado di fattorizzare un numero intero in tempi ragionevoli
(per ragionevoli qui intendiamo tempi polinomiali, o meglio ancora lineari, o meglio ancora logaritmici).
Il metodo più generale per trovare i fattori primi di un intero resta quello delle divisioni
successive, ben noto nelle scuole medie: dato il numero N, si individuano i numeri primi fino
a √N. Iniziando da t = 2 si tenta di
dividere N per t; se la divisione è esatta si è trovato un fattore; il quoziente prende
allora il posto di N e si continua per tentativi, prima con t = 2, poi con t = 3, con t = 5 ...
