AKS algorytm Primy w Pythonie

Question

Kilka lat temu udowodniono, że PRIMES is in P. Czy są jakieś algorytmy implementujące their primality test w Pythonie? Chciałem uruchomić testy porównawcze z naiwnym generatorem i przekonać się, jak szybko to działa. Zrobiłbym to sam, ale nie do końca rozumiem papier, żeby to zrobić.

Answer 1

Szybka odpowiedź: nie, test AKS nie jest najszybszym sposobem na przetestowanie prymatu. Istnieje wiele bardzo szybkich testów, które zakładają (uogólnioną) hipotezę Riemanna i/lub są randomizowane. (Np. Miller-Rabin jest szybki i prosty w implementacji.) Prawdziwy przełom w tej dziedzinie był teoretyczny, co dowodzi, że istnieje algorytm wielomianowy deterministyczny, który nie jest w stanie przyjąć GRH lub innych nieudowodnionych przypuszczeń.

To powiedziawszy, jeśli chcesz je zrozumieć i wdrożyć, może pomóc Scott Aaronson's short article. Nie zawiera wszystkich szczegółów, ale możesz zacząć od strony 10 z 12 i daje wystarczająco dużo. :-) Istnieje również list of implementations (głównie w C++) tutaj.

Ponadto, w celu optymalizacji i ulepszeń (o kilka rzędów wielkości), warto spojrzeć na this report lub (starsze) Crandall and Papadopoulos's report lub (starsze nadal) Daniel J Bernstein's report. Wszystkie mają dość szczegółowy pseudo-kod, który nadaje się do implementacji.

Answer 2

Tak, przejdź spojrzeć na AKS test for primes stronie na 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)]) 

i wyjście jest:

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