Algorithme des amorces AKS en Python
il y A quelques années, il a été prouvé que PRIMES is in P. Y a-t-il des algorithmes implémentant leur test de primalité en Python? Je voulais lancer quelques benchmarks avec un générateur naïf et voir par moi-même à quelle vitesse il est. Je le ferais bien moi-même, mais je ne comprends pas encore assez le papier pour le faire.
2 réponses
réponse rapide: non, le test AKS n'est pas le moyen le plus rapide de tester la primalité. Il y a beaucoup beaucoup tests de primalité plus rapides qui supposent l'hypothèse (généralisée) de Riemann et/ou sont randomisés. (E. g. Miller-Rabin est rapide et simple à mettre en œuvre.) La véritable percée du papier a été théorique, prouvant qu'un déterministe l'algorithme de temps polynomial existe pour tester la primalité, sans supposer le GRH ou d'autres non prouvés conjecture.
cela dit, si vous voulez comprendre et de l'appliquer, Scott Aaronson court article peut aider. Il ne va pas dans tous les détails, mais vous pouvez commencer à la page 10 de 12, et il donne assez. :-) Il y a aussi un liste des implémentations (surtout en C++) ici.
aussi, pour l'optimisation et les améliorations (de plusieurs ordres de grandeur), vous pourriez vouloir regarder rapport, ou (plus) Crandall et le rapport de Papadopoulos!--4-->, ou (encore plus vieux) rapport de Daniel J. Bernstein. Tous ont un pseudo-code assez détaillé qui se prête bien à la mise en œuvre.
Oui, aller regarder les AKS test pour les nombres premiers page sur 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)])
et le résultat est:
# 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]