¿Por qué todo el mundo piensa prueba de primarity AKS es una gran cosa?

Question

Puede alguien explicar por qué las queratosis actínicas de la prueba es buena?

Como yo entiendo las queratosis actínicas, un número $p$ es primo, si todos los coeficientes del polinomio $(x+a)^p$, excepto la primera y la última, son múltiples de $p$.

Parece que la prueba tarda mucho tiempo en ejecutarse. Mira, número de coeficientes es O(p) y, para los grandes números, la validación de si un número es $p$'s de múltiples tomas ln(p). Así, el total es O(p* ln(p)).

El ingenuo promariamente prueba (intentan dividir a $p$ por todos los números de arriba a la raíz cuadrada de $p$), lleva el mismo tiempo.

Me estoy perdiendo algo?

Answer 1

El AKS prueba es más complicado que lo que usted describe, que era conocido en la década de 1600 y se sabe que de tiempo exponencial. De hecho, lo que usted describe es peor que el más ingenuo de prueba de la división. Por desgracia, la numberphile de vídeo ha hecho que mucha gente piensa que esta es la queratosis actínicas de la prueba.

Si miramos un gráfico de tiempos para algunos primalidad implementaciones de prueba, en un log-log de la escala, se puede ver la queratosis actínica (el real) tiene buenas líneas rectas, muestra de ello es polinomial en el tamaño de la entrada, y resulta que los tres implementaciones tienen exponentes de alrededor de 6, que se espera. También se puede ver que es más eficiente que la prueba de la división después de la entrada es lo suficientemente grande (el ensayo en particular método de la división de saltar múltiplos de 2/3/5/7). El uso de todos los de la colección de mejoras Bernstein publicó, el punto de cruce es realmente no es tan grande (~16 dígitos para estas implementaciones)

Como se espera, la prueba de la división es exponencial en el tamaño de la entrada. La queratosis actínica es el polinomio, y APR-CL y ECPP son prácticamente una mucho más rápido que cualquiera, con menor exponentes así.

La queratosis actínicas de la prueba fue muy importante para la teoría, y es extremadamente inteligente. Esto no ha llevado aún a la práctica mejor que la de los otros métodos. Como Se Jagy señala, Granville del papel es un gran recurso para la comprensión de la historia, el algoritmo y el significado.

Answer 2

El algoritmo AKS es una prueba constructiva de "Primos es en P" y por lo tanto de gran interés teórico.

Sin embargo no se utiliza en la práctica ya que hay métodos más rápidos disponibles (APR-CL y ECPP).