print - Algoritmo AKS Primes en Python

python prime number generator

Question

Hace unos años, se demostró que PRIMES está en P. ¿Hay algún algoritmo implementando su prueba de primalidad 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 forma más rápida de probar la primalidad. Hay pruebas de primalidad mucho más rápidas que o bien suponen la hipótesis (generalizada) de Riemann y / o son aleatorias. (Por ejemplo, Miller-Rabin es rápido y fácil de implementar). El verdadero avance del documento fue teórico, demostrando que existe un algoritmo determinista de tiempo polinomial para probar la primalidad, sin asumir el GRH u otras conjeturas no probadas.

Dicho eso, si quiere comprenderlo e implementarlo, el breve artículo de Scott Aaronson 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 una lista de implementaciones (principalmente en C ++) aquí.

Además, para la optimización y las mejoras (en varios órdenes de magnitud), es posible que desee consultar este informe , o (más antiguo) el informe de Crandall y Papadopoulos , o (más antiguo) el informe de Daniel J. Bernstein . Todos ellos tienen pseudocódigo bastante detallado que se presta bien a la implementación.

Answer 2

Sí, ve a la prueba de AKS para la página de primos 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 el resultado 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]