Algoritmo AKS Primes in Python
Domanda
Alcuni anni fa, è stato dimostrato che PRIMES è in P . Esistono algoritmi che implementano il loro test di primalità in Python? Volevo eseguire alcuni benchmark con un generatore ingenuo e vedere di persona quanto è veloce. Lo implementerei da solo, ma non ho ancora capito abbastanza il documento per farlo.
Soluzione
Risposta rapida: no, il test AKS non è il modo più veloce per testare la primalità. Esistono test di primalità molto più veloci molto che assumono l'ipotesi (generalizzata) di Riemann e / o sono randomizzati. (Ad esempio Miller-Rabin è veloce e semplice da implementare.) La vera svolta del documento era teorico, dimostrando che esiste un algoritmo deterministico per il tempo polinomiale per testare la primalità, senza assumere il GRH o altre congetture non dimostrate.
Detto questo, se vuoi comprenderlo e implementarlo, Il breve articolo di Scott Aaronson potrebbe aiutare. Non entra in tutti i dettagli, ma puoi iniziare da pagina 10 di 12 e dà abbastanza. :-) C'è anche un elenco di implementazioni (principalmente in C ++) qui.
Inoltre, per l'ottimizzazione e i miglioramenti (per diversi ordini di grandezza), potresti voler guardare questo rapporto o (precedente) Crandall e Rapporto di Papadopoulos o (ancora vecchio) Rapporto di Daniel J Bernstein . Tutti hanno uno pseudo-codice abbastanza dettagliato che si presta bene all'implementazione.
Altri suggerimenti
Sì, vai alla test AKS per numeri primi su rosettacode.org
def expand_x_1(p):
ex = [1]
for i in range(p):
ex.append(ex[-1] * -(p-i) / (i+1))
return ex[::-1]
def aks_test(p):
if p < 2: return False
ex = expand_x_1(p)
ex[0] += 1
return not any(mult % p for mult in ex[0:-1])
print('# p: (x-1)^p for small p')
for p in range(12):
print('%3i: %s' % (p, ' '.join('%+i%s' % (e, ('x^%i' % n) if n else '')
for n,e in enumerate(expand_x_1(p)))))
print('\n# small primes using the aks test')
print([p for p in range(101) if aks_test(p)])
e l'output è:
# p: (x-1)^p for small p
0: +1
1: -1 +1x^1
2: +1 -2x^1 +1x^2
3: -1 +3x^1 -3x^2 +1x^3
4: +1 -4x^1 +6x^2 -4x^3 +1x^4
5: -1 +5x^1 -10x^2 +10x^3 -5x^4 +1x^5
6: +1 -6x^1 +15x^2 -20x^3 +15x^4 -6x^5 +1x^6
7: -1 +7x^1 -21x^2 +35x^3 -35x^4 +21x^5 -7x^6 +1x^7
8: +1 -8x^1 +28x^2 -56x^3 +70x^4 -56x^5 +28x^6 -8x^7 +1x^8
9: -1 +9x^1 -36x^2 +84x^3 -126x^4 +126x^5 -84x^6 +36x^7 -9x^8 +1x^9
10: +1 -10x^1 +45x^2 -120x^3 +210x^4 -252x^5 +210x^6 -120x^7 +45x^8 -10x^9 +1x^10
11: -1 +11x^1 -55x^2 +165x^3 -330x^4 +462x^5 -462x^6 +330x^7 -165x^8 +55x^9 -11x^10 +1x^11
# small primes using the aks test
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]