Qual è l'algoritmo di fattorizzazione dei primi più veloce ad oggi?

La risposta è: dipende. Supponiamo che ti venga dato un input arbitrario che non ha una forma speciale. L'algoritmo più efficiente è una ricetta che utilizza singoli algoritmi di fattorizzazione. Queste sono tutte le possibilità:

Per input molto piccoli, usa la divisione di prova per i numeri primi (o una ruota per avvicinarsi senza dover avere o generare numeri primi). Questo funziona meglio fino a ~1M, a seconda delle implementazioni. Qualche divisione di prova è sempre una buona idea per rimuovere i fattori piccoli.

Pollard Rho funziona abbastanza bene. Quando l'input diventa più grande (ad esempio > 2^32 ma meno di 2^64), SQUFOF tipicamente funziona più velocemente.

Una volta più grande di 2^64, Pollard Rho può ancora valere un po' di tempo per trovare piccoli fattori, ma P-1 e ECM sono migliori quando si cerca più in profondità.

Quadratic Sieve tipicamente è meglio iniziare da qualche parte nell'intervallo 30-40 cifre e continuare fino a 95-105 cifre.

Dopo di che, NFS (GNFS) è l'algoritmo più efficiente.

=================================================

Nota che, a parte i piccoli input, il metodo più efficiente non è semplicemente scegliere uno di questi ed eseguirlo, ma invece passare attraverso una sequenza. Abbiamo anche bisogno di un efficiente test di primalità, che è un altro argomento. Per esempio, dato un numero arbitrario di 150 cifre, la cosa migliore da fare non è semplicemente iniziare ad eseguire NFS. Dovremmo rimuovere i piccoli divisori -- prima con una divisione di prova (forse con un GCD veloce, o un albero dei resti, o solo un test di divisibilità), poi usando gli algoritmi che sono efficienti nel trovare piccoli divisori: Pollard Rho, P-1 e ECM. Questi troveranno efficientemente piccoli divisori (nel caso di ECM's "piccolo" può essere 20+ cifre!). Perché preoccuparsi di Rho e P-1 se ECM è più efficiente nel lungo periodo? Perché una breve corsa di Rho o P-1 è tipicamente più veloce di ECM se i divisori sono piccoli. Alcune persone non si preoccupano di questa ottimizzazione e passano direttamente all'ECM (notando che come si esegue l'ECM in termini di dimensioni e numero di curve finisce per essere una discussione simile), e le implementazioni contano.

Una volta che hai eseguito "abbastanza" P-1 / ECM, e il numero che devi ancora elaborare è composito, allora scegli QS o NFS.

Per il caso sub-128-bit, posso dare l'esempio di Grandlund e Möller's GNU factor. Fa la divisione di prova per piccoli numeri primi seguita da Pollard Rho o SQUFOF. Perl/ntheory è più complicato, usando più algoritmi e più ottimizzazione per piccoli input.

Per input più grandi, yafu è un programma di fattorizzazione allo stato dell'arte. Inizia con la divisione di prova, fa un po' di Pollard Rho, poi inizia a mescolare P-1 e ECM in una sequenza di dimensioni e curve che funzionano bene in media, poi sceglie QS o NFS in base alla dimensione di input rimanente e al punto di crossover misurato per la macchina. Questo segue fondamentalmente quello che ho descritto.