Per prima cosa, lasciatemi parlare di AKS. AKS è molto importante per la teoria , ma non è utilizzato nella pratica. Non è veloce, e non è un "modo di trovare numeri primi" di solito usato come un setaccio. È un test di primalità - cioè, dato un numero N , risponde deterministicamente se N è primo o no. Esistono altri metodi che funzionano milioni di volte più velocemente (ad esempio BPSW o M-R deterministico sotto 2 ^ 64, APR-CL o ECPP sopra). Questo presuppone anche che tu abbia bisogno di una prova: BPSW più alcuni test M-R sono abbastanza buoni per quasi tutti e saranno ancora più veloci.
Internet ama AKS perché sembra che dovrebbe essere veloce. L'unico algoritmo del tempo polinomiale deterministico noto! Ciò è causato da un fraintendimento degli algoritmi randomizzati e da un errore da parte dei poster di implementare o addirittura utilizzare questi metodi nella pratica.
AKS, da Wikipedia o v6 paper , è semplice al livello più alto. Ci sono alcuni trucchi come assicurarsi di fare i registri correttamente e alcune efficienze di implementazione nei passaggi 2/3. Implementare correttamente znorder non è troppo difficile, specialmente se sei rilassato e non preoccuparti troppo dell'efficienza (il punto 5 domina completamente il tempo). Il passaggio 5 è complicato, perché devi fare un modulo di elevanza del risonanza polinomiale efficiente N e un polinomio. Direi innanzitutto di farlo funzionare e lavorare, quindi preoccuparsi di soluzioni efficienti come la segmentazione binaria.
Ci sono molte implementazioni in giro. Programmazione Praxis ha un bel post sul blog, con discussione e un paio di implementazioni. Vedi Part 1 e Parte 2 . La parte 2 mostra l'implementazione dell'algoritmo "V6" (l'algoritmo aggiornato degli autori originali).
- L'implementazione di Bornemann in Pari. Uno dei più veloci, utilizza alcuni miglioramenti e un bel euristico / r / s.
- Programming Praxis ha una versione relativamente inefficiente in Scheme. Facile da seguire e l'autore spiega ogni passaggio.
- Qualcuno ha pubblicato una bella versione di Python su Programming Praxis, anche se funziona solo fino a 8 cifre.
- Ho versioni di Perl, C e C + GMP su github, con tre algoritmi ciascuno. La versione V6 è quella della carta aggiornata. La versione di Voloch + Bornemann include i miglioramenti che Bornemann mostra e fino a quando non ho implementato la terza versione, è stata l'implementazione open source più veloce di AKS. La terza versione utilizza il teorema 4.1 del documento di Bernstein del 2004, che include la maggior parte delle ottimizzazioni pubblicate. È > 10 volte più veloce della versione di Voloch + Bornemann.
- Yijun Yuan ha una versione molto leggibile su github che implementa l'algoritmo v6 usando NTL. Non è veloce, ma è abbastanza facile da seguire dal giornale.
- Ci sono molte versioni veramente negative là fuori (dato che ci sono quasi tutti gli algoritmi a cui si può pensare).
Un problema con AKS è che gli dai un numero, che si allontana e dice "Prime" o "Composite". Ho visto molte implementazioni che danno la risposta sbagliata per alcuni input (a causa di un bug nell'implementazione). Pensaci. Questo dovrebbe essere una prova - dopotutto, abbiamo eseguito l'input attraverso alcuni test Miller-Rabin, forse BPSW, siamo quasi sicuri che il numero sia davvero primo, e ora abbiamo deciso di volere la certezza più vicina al 100% possibile. Tuttavia, se non abbiamo la certezza che il programma sia stato eseguito correttamente, quale era il punto? Questo è il motivo per cui ritengo che l'ECPP sia una scelta molto migliore per le prove di primalità, poiché fornisce un certificato che può essere rapidamente controllato indipendentemente in qualsiasi momento. Dato che è anche milioni di volte più veloce di AKS, è una scelta facile.