AKS Primes algoritmo en Python hace

Question

unos años, se comprobó que PRIMES is in P. ¿Hay algún algoritmo que implemente their primality test en Python? Quería ejecutar algunos puntos de referencia con un generador ingenuo y ver por mí mismo qué tan rápido es. Lo implementaría yo mismo, pero todavía no entiendo el papel lo suficiente como para hacerlo.

Answer 1

respuesta rápida: no, la prueba AKS no es la manera más rápida para poner a prueba de primalidad. Hay mucho mucho más rápidas pruebas de primalidad que, o bien asumen el (generalizada) hipótesis de Riemann y/o se asignaron al azar. (Por ejemplo Miller-Rabin es rápido y fácil de implementar.) El verdadero avance del papel era teórica, lo que demuestra que existe un algoritmo deterministaen tiempo polinómico para primalidad pruebas, sin asumir la GRH u otras conjeturas no probadas.

Dicho esto, si se quiere entender y poner en práctica que, Scott Aaronson's short article podría ayudar. No entra en todos los detalles, pero puede comenzar en la página 10 de 12, y da suficiente. :-) También hay un list of implementations (principalmente en C++) aquí.

Además, para la optimización y mejoras (en varios órdenes de magnitud), es posible que desee ver en this report, o (más) Crandall and Papadopoulos's report, o (aún mayores) Daniel J Bernstein's report. Todos ellos tienen pseudocódigo bastante detallado que se presta bien a la implementación.

Answer 2

Sí, ir a buscar a AKS test for primes página en 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)]) 

y la salida es:

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