Una prueba de primalidad es un algoritmo para saber si un número entero es primo .
La prueba más sencilla es la siguiente: para probar N , comprobamos si es divisible por uno de los números enteros incluidos en sentido amplio entre 2 y N-1. Si la respuesta es negativa, entonces N es primo; de lo contrario, es compuesto.
Varios cambios mejoran el rendimiento de este algoritmo:
Las pruebas probabilísticas no son pruebas de primalidad en sentido estricto (forman parte de los métodos de Montecarlo ): no permiten garantizar con certeza que un número sea primo, pero su bajo costo en tiempo de cómputo las convierte en excelentes candidatas para Las aplicaciones en criptología a menudo dependen críticamente de números primos grandes y aceptan una tasa de error siempre que sea muy baja: se denominan números primos industriales (in) . La idea básica de probar la primordialidad de un número N es la siguiente:
Después de varias iteraciones, si N no se reconoce como un número compuesto , probablemente se declara primo .
Dada una prueba, puede haber ciertos números compuestos que se declaren "probablemente primos" independientemente del testigo. Estos números resistentes a la prueba se denominan números pseudoprime para esta prueba.
La prueba de primalidad probabilística más simple es la prueba de primordialidad de Fermat . La prueba de primalidad de Miller-Rabin y la prueba de primordialidad de Solovay-Strassen son variantes más sofisticadas que detectan todos los compuestos. Cualquiera de estas pruebas se utiliza cuando se requiere un número primo después de un cálculo lo más breve posible mientras se acepta un pequeño margen de duda, por ejemplo, en el cifrado RSA o en el protocolo de intercambio de claves Diffie-Hellman .
La prueba ciclotómica es una prueba de primalidad determinista; demostramos que su tiempo de ejecución es O ( n zueco (log (n)) ), donde n es el número de dígitos de N y c es una constante independiente de n . Su complejidad es menor que un polinomio .
Se puede demostrar que la prueba de primalidad de la curva elíptica realiza O ( n 6 ), pero solo mediante el uso de algunas conjeturas de la teoría analítica de números aún no probadas pero ampliamente aceptadas como verdaderas. En la práctica, esta prueba es más lenta que la prueba ciclotómica para números con más de 10,000 dígitos.
La implementación de estos dos métodos es bastante difícil y, por lo tanto, el riesgo de error debido a la implementación es mayor que el de los métodos probabilísticos mencionados anteriormente.
Si la hipótesis de Riemann generalizada es cierta, la prueba de Miller-Rabin se puede convertir a una versión determinista con un tiempo de ejecución Õ ( n 4 ). En la práctica, este algoritmo es más lento que los dos anteriores.
En 2002, Manindra Agrawal, Neeraj Kayal y Nitin Saxena describieron una prueba de primalidad determinista (la prueba de primalidad AKS ) que se ejecuta en Õ ( n 12 ). Además, de acuerdo con una conjetura (no probada, por lo tanto, pero ampliamente reconocida como verdadera), se ejecutaría en Õ ( n 6 ). Por lo tanto, es la primera prueba de primalidad determinista del tiempo de ejecución polinomial . En la práctica, este algoritmo es más lento que los otros métodos.
La teoría de números proporciona métodos; un buen ejemplo es la prueba de Lucas-Lehmer para comprobar si un número es primo. Esta prueba está relacionada con el hecho de que el orden multiplicativo de un cierto número a módulo n es n -1 para un número primo n cuando a es una raíz primitiva . Si podemos demostrar que a es una raíz primitiva de n , podemos demostrar que n es primo.
En teoría de la complejidad , el problema PRIMES es el problema de la decisión de pertenecer al lenguaje formal que contiene números primos, escritos en binario:
BONIFICACIÓN = {10, 11, 101, 111, 1011, ...}
donde 10, 11, 101, 111, 1011 ... son las escrituras binarias de los números primos 2, 3, 5, 7, 11, etc.
PRIMES está en co-NP : de hecho, sus COMPOSITES complementarios, es decir, la decisión de pertenecer al conjunto de números no primos, está en NP , porque podemos decidir COMPOSITES en tiempo polinomial por el número de dígitos del número a probar. , en una máquina de Turing no determinista , adivinando un factor.
En 1975, Vaughan Pratt (en) demostró que existe un certificado de PRIMAS verificables en tiempo polinomial. Por tanto, PRIMES también está en NP y, por tanto, en NP ∩ coNP .
Los algoritmos Solovay-Strassen y Miller-Rabin muestran que PRIMES está en coRP . En 1992, el algoritmo de Adleman-Huang muestra que PRIMES está en RP . Por lo tanto, PRIMES está en ZPP = RP ∩ coRP .
La prueba de primalidad de Adleman - Pomerance - Rumely (en) de 1983 muestra que PRIMES está en QP (tiempo cuasi-polinómico), una clase que no ha demostrado ser comparable a una de las clases mencionadas anteriormente.
La prueba de primalidad AKS es un algoritmo de tiempo polinómico y finalmente muestra PRIMAS está en P . Pero PRIMES no ha demostrado ser P-completo . No sabemos si PRIMES está en NC o en LOGSPACE por ejemplo. Pero sabemos que PRIMES no está en AC 0 .