AKS Primes Algorithmus in Python

Question

Vor ein paar Jahren wurde es, dass in P PRIMES ist . Gibt es Algorithmen Implementierung ihre Primzahltest in Python? Ich wollte einiges Benchmarks mit einem naiven Generator und sehen für mich laufen, wie schnell es ist. Ich würde implementieren es mich, aber ich verstehe nicht das Papier genug noch das zu tun.

Answer 1

Kurze Antwort: Nein, das AKS-Test ist nicht der schnellste Weg primality zu testen. Es gibt viel viel schnellen Primzahltests, die entweder die (verallgemeinerte) Riemann-Hypothese übernehmen und / oder randomisiert werden. (ZB Miller-Rabin ist schnell und einfach zu implementieren.) Der eigentliche Durchbruch des Papiers theoretisch war, was beweist, dass ein determinis Polynomialzeit-Algorithmus zum Testen primality vorhanden ist, ohne dass die GRH oder andere unbewiesene Vermutungen anzunehmen.

Das heißt, wenn Sie wollen zu verstehen und umzusetzen, Scott Aaronson Kurzartikel könnte helfen. Es geht nicht in allen Details, aber Sie können auf Seite 10 von 12 starten, und es gibt genug. :-) Es gibt auch eine Liste der Implementierungen (meist in C ++) hier.

Auch für die Optimierung und Verbesserung (um mehrere Größenordnungen), könnte man unter diesen Bericht oder (älteren) Crandall und Papadopoulos Bericht , oder (noch älter) Daniel J Bernstein Bericht . Alle von ihnen haben ziemlich detaillierte Pseudo-Code, der sich gut für die Implementierung verleiht.

Answer 2

Ja, schau auf AKS-Test für Primzahlen Seite auf 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)])

und der Ausgang ist:

# 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]