AKS Python'daki algoritma algoritması

Question

Birkaç yıl önce, PRIMES is in P olduğu kanıtlanmıştır. Python'da their primality test'u uygulayan herhangi bir algoritma var mı? Saf bir jeneratörle bazı kriterler vermek istedim ve kendim için ne kadar hızlı olduğunu görüyorum. Onu kendim uygularım, ama henüz bunu yapmak için yeterince kağıt anlamadım.

Answer 1

Hızlı cevap: hayır, AKS testi birincilliği test etmenin en hızlı yolu değildir. Ya (genelleştirilmiş) Riemann hipotezini kabul eden ve/veya randomize olan çok çok daha hızlı primalite testleri vardır. (Örn. Miller-Rabin, uygulanması hızlı ve basittir.) Kağıdın gerçek atılımı, GRH veya diğer onaylanmamış varsayımlar varsayılmadan, ilkelliği test etmek için deterministik polinom zamanı algoritmasının mevcut olduğunu kanıtlayan teorikti.

Bu, eğer anlamak ve uygulamak istiyorsanız, Scott Aaronson's short article yardımcı olabilir. Tüm ayrıntılara girmez, ancak 12'nci sayfa 10'dan başlayabilir ve yeterlidir. :-) Ayrıca burada bir list of implementations (çoğunlukla C++) var.

Ayrıca (birkaç büyüklük sırası ile) optimizasyonu ve iyileştirmeler için, sen this report veya (eski) Crandall and Papadopoulos's report veya (eski hala) Daniel J Bernstein's report bakmak isteyebilirsiniz. Hepsinin kendini uygulama için iyi bir şekilde ödünç veren oldukça ayrıntılı sözde kodu var.

Answer 2

Evet,

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

rosettacode.org üzerinde AKS test for primes sayfaya baktığınız gidip çıktısı:

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