Prueba de primalidad

Una prueba de primalidad es un algoritmo para determinar si un número de entrada es primo . Entre otros campos de las matemáticas , se utiliza en criptografía . A diferencia de la factorización de enteros , las pruebas de primalidad generalmente no proporcionan factores primos , sino que solo indican si el número de entrada es primo o no. Se considera que la factorización es un problema computacionalmente difícil, mientras que la prueba de primalidad es relativamente sencilla (su tiempo de ejecución es polinomial con respecto al tamaño de la entrada). Algunas pruebas de primalidad demuestran que un número es primo, mientras que otras, como la de Miller-Rabin, demuestran que un número es compuesto . Por lo tanto, estas últimas podrían denominarse con mayor precisión pruebas de composición en lugar de pruebas de primalidad.

La prueba de primalidad más simple es la división por ensayo : dado un número de entrada,${\displaystyle n}$, comprueba si es divisible por algún número primo entre 2 y${\displaystyle {\sqrt {n}}}$(es decir, si la división no deja resto ). Si es así, entonces${\displaystyle n}$es compuesto . De lo contrario, es primo. ^{[ 1 ]} Todos los divisores${\displaystyle p\geq {\sqrt {n}}}$debe tener un divisor${\displaystyle {\frac {n}{p}}\leq {\sqrt {n}}}$y un divisor primo${\displaystyle q}$de${\displaystyle {\frac {n}{p}}}$y por lo tanto buscando divisores primos como máximo${\displaystyle {\sqrt {n}}}$es suficiente.

Por ejemplo, consideremos el número 100, cuyos divisores son estos números:

1, 2, 4, 5, 10, 20, 25, 50, 100.

Cuando todos los divisores posibles hasta${\displaystyle n}$Al realizar pruebas, algunos divisores se descubrirán dos veces . Para observar esto, consideremos la lista de pares de divisores de 100:

${\displaystyle 1\times 100,\;2\times 50,\;4\times 25,\;5\times 20,\;10\times 10,\;20\times 5,\;25\times 4,\;50\times 2,\;100\times 1}$.

Productos anteriores${\displaystyle 10\times 10}$son lo contrario de los productos que aparecieron anteriormente. Por ejemplo,${\displaystyle 5\times 20}$y${\displaystyle 20\times 5}$son recíprocos entre sí. Además, el de los dos divisores,${\displaystyle 5\leq {\sqrt {100}}=10}$y${\displaystyle 20\geq {\sqrt {100}}=10}$Esta observación se generaliza a todos${\displaystyle n}$: todos los pares divisores de${\displaystyle n}$contienen un divisor menor o igual que${\displaystyle {\sqrt {n}}}$, por lo que el algoritmo solo necesita buscar divisores menores o iguales a${\displaystyle {\sqrt {n}}}$para garantizar la detección de todos los pares divisores. ^{[ 1 ]}

Además, 2 es un primo que divide a 100, lo que prueba inmediatamente que 100 no es primo. Todo entero positivo, excepto 1, es divisible por al menos un número primo según el Teorema Fundamental de la Aritmética . Por lo tanto, el algoritmo solo necesita buscar divisores primos menores o iguales a 100.${\displaystyle {\sqrt {n}}}$.

Para otro ejemplo, consideremos cómo este algoritmo determina la primalidad de 17. Uno tiene${\displaystyle 4<{\sqrt {17}}<5}$y los únicos primos${\displaystyle \leq {\sqrt {17}}}$son 2 y 3. Ninguno divide a 17, lo que demuestra que 17 es primo. Para un último ejemplo, consideremos 221. Uno tiene${\displaystyle 14<{\sqrt {221}}<15}$y los números primos${\displaystyle \leq {\sqrt {221}}}$son 2, 3, 5, 7, 11 y 13. Al comprobar cada uno, se descubre que${\displaystyle {\frac {221}{13}}=17}$, demostrando que 221 no es primo.

En los casos en que se calcula la lista de primos${\displaystyle \leq {\sqrt {n}}}$no es factible, todos los números entre${\displaystyle 2}$y${\displaystyle {\sqrt {n}}}$se puede comprobar de forma sencilla (y lenta) para encontrar divisores. Una mejora sencilla consiste en comprobar la divisibilidad por 2 y solo por los números impares entre 3 y${\displaystyle {\sqrt {n}}}$, puesto que la divisibilidad por un número par implica la divisibilidad por 2.

Este método se puede mejorar aún más. Observe que todos los números primos mayores que 5 son de la forma${\displaystyle 6k+i}$para un número entero no negativo${\displaystyle k}$y${\displaystyle i\in \{1,5\}}$. De hecho, cada número entero es de la forma${\displaystyle 6k+i}$para un entero positivo${\displaystyle k}$y${\displaystyle i\in \{0,1,2,3,4,5\}}$. Dado que 2 divide${\displaystyle 6k,6k+2}$, y${\displaystyle 6k+4}$y 3 divisiones${\displaystyle 6k}$y${\displaystyle 6k+3}$, los únicos restos posibles módulo 6 para un primo mayor que 3 son 1 y 5. Por lo tanto, una prueba de primalidad más eficiente para${\displaystyle n}$es comprobar si${\displaystyle n}$es divisible por 2 o 3, entonces para comprobar todos los números de la forma${\displaystyle 6k+1}$y${\displaystyle 6k+5}$que son${\displaystyle \leq {\sqrt {n}}}$Esto es casi tres veces más rápido que probar todos los números hasta${\displaystyle {\sqrt {n}}}$.

Generalizando aún más, todos los números primos mayores que${\displaystyle p_{m}}$(el${\displaystyle m}$el enésimo número primo) son de la forma${\displaystyle p_{m}\#\cdot k+i}$, dónde${\displaystyle \{k,i\in \mathbb {Z} \mid 0\leq i<p_{m}\#\land {\text{gcd}}\left(p_{m}\#,i\right)=1\}}$y${\displaystyle p_{m}\#}$es el primordio – el producto del primero${\displaystyle m}$primos.

Por ejemplo, considere${\displaystyle p_{3}\#=2\cdot 3\cdot 5=30}$. Todos los números enteros son de la forma${\displaystyle 30k+i}$, dónde${\displaystyle \{k,i\in \mathbb {Z} \mid 0\leq i<30\}}$Ahora, 2 divide${\displaystyle 0,2,4,\dots ,28}$, 3 divisiones${\displaystyle 0,3,6,\dots ,27}$y 5 divisiones${\displaystyle 0,5,10,\dots ,25}$. Por lo tanto, todos los números primos mayores que 30 son de la forma${\displaystyle 30k+i}$para${\displaystyle i\in \{1,7,11,13,17,19,23,29\}}$. Por supuesto, no todos los números de la forma${\displaystyle p_{m}\#\cdot k+i}$con${\displaystyle i}$coprimo a${\displaystyle p_{m}\#}$son primordiales. Por ejemplo,${\displaystyle 19\cdot 23=437=210\cdot 2+17=p_{4}\#\cdot 2+17}$no es primo, aunque 17 es coprimo con${\displaystyle p_{4}\#=2\cdot 3\cdot 5\cdot 7}$.

Mientras${\displaystyle \lim _{m\to \infty }{\frac {\phi \left(p_{m}\#\right)}{p_{m}\#}}=0}$, dónde${\displaystyle \phi \left(m\right)}$es la función totiente de Euler , que comprueba la divisibilidad por todos los primos que son menores que${\displaystyle p_{m}\#}$aún es necesario. Se pueden aplicar de forma recursiva observaciones análogas a las anteriores , dando como resultado la Criba de Eratóstenes .

Una forma de acelerar estos métodos (y todos los demás mencionados a continuación) es precalcular y almacenar una lista de todos los números primos hasta un cierto límite, como todos los primos hasta 200. (Dicha lista se puede calcular con la Criba de Eratóstenes o mediante un algoritmo que prueba cada incremento).${\displaystyle m}$contra todos los números primos conocidos${\displaystyle \leq {\sqrt {m}}}$). Luego, antes de realizar la prueba${\displaystyle n}$para la primacía con un método a gran escala,${\displaystyle n}$Primero se puede comprobar si es divisible por algún número primo de la lista. Si es divisible por alguno de esos números, entonces es compuesto y se pueden omitir las demás pruebas.

Una prueba de primalidad simple pero ineficiente utiliza el teorema de Wilson , que establece que${\displaystyle p}$es primo si y solo si:

${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$

Aunque este método requiere aproximadamente${\displaystyle p}$Las multiplicaciones modulares, ^{[ 2 ]} lo hacen poco práctico, los teoremas sobre primos y residuos modulares forman la base de muchos métodos más prácticos.

Estas son pruebas que parecen funcionar bien en la práctica, pero no están probadas y, por lo tanto, técnicamente hablando, no son algoritmos. La prueba de primalidad de Fermat y la prueba de Fibonacci son ejemplos sencillos, y son efectivas cuando se combinan. John Selfridge ha conjeturado que si p es un número impar y p ≡ ±2 (mod 5), entonces p será primo si se cumplen las dos condiciones siguientes:

• 2 ^{p −1} ≡ 1 (mod p ),
• f _{p +1} ≡ 0 (mod p ),

donde f _k es el k -ésimo número de Fibonacci . La primera condición es la prueba de primalidad de Fermat usando base 2.

En general, si p ≡ a (mod x² ⁺ 4), donde a es un no residuo cuadrático (mod x² ⁺ 4), entonces p debe ser primo si se cumplen las siguientes condiciones:

• 2 ^{p −1} ≡ 1 (mod p ),
• f ( x ) _{p +1} ≡ 0 (mod p ),

f ( x ) _k es el k -ésimo polinomio de Fibonacci en x .

Selfridge , Pomerance y Wagstaff ofrecieron conjuntamente 620 dólares por un contraejemplo o prueba de que no existe ninguno, ^{[ 3 ]} y el premio ahora debe ser entregado por la Fundación de Teoría de Números .

Las pruebas probabilísticas son más rigurosas que las heurísticas, ya que proporcionan límites demostrables sobre la probabilidad de ser engañado por un número compuesto. Varias pruebas de primalidad populares son pruebas probabilísticas. Estas pruebas utilizan, además del número probado n , otros números a que se eligen al azar de algún espacio muestral ; las pruebas de primalidad aleatorias habituales nunca informan que un número primo sea compuesto, pero es posible que un número compuesto se informe como primo. La probabilidad de error se puede reducir repitiendo la prueba con varios valores de a elegidos independientemente ; para dos pruebas de uso común, para cualquier compuesto n, al menos la mitad de los a detectan la composición de n , por lo que k repeticiones reducen la probabilidad de error a como máximo 2 ^{− k} , que se puede hacer arbitrariamente pequeño aumentando k .

La estructura básica de las pruebas de primalidad aleatorias es la siguiente:

1. Elige un número al azar .
2. Comprueba la igualdad (correspondiente a la prueba elegida) entre a y el número n dado . Si la igualdad no se cumple, entonces n es un número compuesto y a es un indicador de dicha composición, y la prueba finaliza.
3. Vuelva al paso uno hasta alcanzar la precisión requerida.

Después de una o más iteraciones, si no se encuentra que n sea un número compuesto, entonces se puede declarar que probablemente sea primo .

A principios del siglo XX, se demostró que un corolario del pequeño teorema de Fermat podía usarse para probar la primalidad. ^{[ 9 ]} Esto dio como resultado la prueba de primalidad de Pocklington . ^{[ 10 ]} Sin embargo, como esta prueba requiere una factorización parcial de n  −  1, el tiempo de ejecución seguía siendo bastante lento en el peor de los casos. La primera prueba de primalidad determinista significativamente más rápida que los métodos ingenuos fue la prueba de ciclotomía ; se puede demostrar que su tiempo de ejecución es O ((log n ) ^{c log log log n} ), donde n es el número a probar para la primalidad y c es una constante independiente de n . Se hicieron varias mejoras adicionales, pero no se pudo demostrar que ninguna tuviera un tiempo de ejecución polinomial. (El tiempo de ejecución se mide en términos del tamaño de la entrada, que en este caso es ~ log n , que es el número de bits necesarios para representar el número n .) Se puede demostrar que la prueba de primalidad de curva elíptica se ejecuta en O((log n ) ⁶ ), si algunas conjeturas sobre la teoría analítica de números son ciertas. De manera similar, bajo la hipótesis generalizada de Riemann (que Miller, confusamente, llama la " hipótesis extendida de Riemann "), se puede demostrar que la prueba determinista de Miller , que forma la base de la prueba probabilística de Miller-Rabin, se ejecuta en Õ ((log n ) ⁴ ). ^{[ 11 ]} En la práctica, este algoritmo es más lento que los otros dos para tamaños de números que se pueden manejar. Debido a que la implementación de estos dos métodos es bastante difícil y crea un riesgo de errores de programación, a menudo se prefieren pruebas más lentas pero más simples.        

En 2002, Manindra Agrawal , Neeraj Kayal y Nitin Saxena inventaron la primera prueba de tiempo polinomial determinista incondicionalmente demostrable para la primalidad . La prueba de primalidad AKS se ejecuta en Õ((log n ) ¹² ) (mejorada a Õ((log n ) ^7.5 ) ^{[ 12 ]} en la revisión publicada de su artículo), que puede reducirse aún más a Õ((log n ) ⁶ ) si la conjetura de Sophie Germain es verdadera. ^{[ 13 ]} Posteriormente, Lenstra y Pomerance presentaron una versión de la prueba que se ejecuta en tiempo Õ((log n ) ⁶ ) incondicionalmente. ^{[ 14 ]}    

Agrawal, Kayal y Saxena sugieren una variante de su algoritmo que se ejecutaría en Õ((log n ) ³ ) si la conjetura de Agrawal es verdadera; sin embargo, un argumento heurístico de Hendrik Lenstra y Carl Pomerance sugiere que probablemente sea falsa. ^{[ 12 ]} Una versión modificada de la conjetura de Agrawal, la conjetura de Agrawal-Popovych, ^{[ 15 ]} aún podría ser verdadera. 

En la teoría de la complejidad computacional , el lenguaje formal correspondiente a los números primos se denomina PRIMES. Es fácil demostrar que PRIMES pertenece a Co-NP : su complemento COMPOSITES pertenece a NP porque se puede determinar la composición adivinando un factor de forma no determinista.

En 1975, Vaughan Pratt demostró que existía un certificado de primalidad que se podía comprobar en tiempo polinomial, y por lo tanto que PRIMES estaba en NP , y por consiguiente en ⁠${\displaystyle {\mathsf {NP\cap coNP}}}$Consulte el certificado de primacía para obtener más detalles.

El posterior descubrimiento de los algoritmos de Solovay-Strassen y Miller-Rabin puso a PRIMES en coRP . En 1992, el algoritmo de Adleman-Huang ^{[ 7 ]} redujo la complejidad a ⁠${\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}}$⁠ , que sustituyó el resultado de Pratt.

La prueba de primalidad de Adleman-Pomerance-Rumely de 1983 colocó a PRIMES en QP ( tiempo cuasipolinomial ), que no se sabe que sea comparable con las clases mencionadas anteriormente.

Debido a su tratabilidad en la práctica, los algoritmos de tiempo polinomial que asumen la hipótesis de Riemann y otras evidencias similares, se sospechaba desde hace tiempo, aunque no se había demostrado, que la primalidad podía resolverse en tiempo polinomial. La existencia de la prueba de primalidad AKS finalmente resolvió esta antigua cuestión y colocó a PRIMES en P. Sin embargo, no se sabe si PRIMES es P-completo , y se desconoce si pertenece a clases que se encuentran dentro de P, ^como NC o L. Se sabe que PRIMES no está en AC ^{0. [} 16 ^]

Existen ciertos métodos de teoría de números para comprobar si un número es primo, como la prueba de Lucas y la prueba de Proth . Estas pruebas suelen requerir la factorización de n  +  1, n − 1 o una cantidad similar, lo que significa que no son útiles para pruebas de primalidad de propósito general, pero a menudo resultan bastante eficaces cuando se sabe que el número n sometido a prueba tiene una forma especial.

La prueba de Lucas se basa en el hecho de que el orden multiplicativo de un número a módulo n es n − 1 para un número primo n cuando a es una raíz primitiva módulo n . Si podemos demostrar que a es primitivo para n , podemos demostrar que n es primo.

• Enlace obsoleto en archive.today (archivado el 20/12/2012) – Implementación de la prueba de primalidad de Solovay-Strassen en Maple
• Cómo distinguir los números primos de los números compuestos, por DJ Bernstein (cr.yp.to)
• Las páginas principales (primes.utm.edu)
• Prueba de primalidad de Lucas con N  − 1 factorizado  (MathPages.com) en los archivos web de la Biblioteca del Congreso (archivado el 6 de agosto de 2010).
• PRIMABOINCA es un proyecto de investigación que utiliza ordenadores conectados a Internet para buscar un contraejemplo a algunas conjeturas. La primera conjetura ( la conjetura de Agrawal ) fue la base para la formulación del primer algoritmo determinista de prueba de primos en tiempo polinomial ( algoritmo AKS ).