La prueba de primalidad de Fermat es una prueba probabilística para determinar si un número es un número primo probable .
Concepto
El pequeño teorema de Fermat establece que si p es primo y a no es divisible por p , entonces
Si uno quiere probar si p es primo, entonces podemos elegir números enteros aleatorios a no divisibles por p y ver si se cumple la igualdad. Si la igualdad no se cumple para un valor de a , entonces p es compuesto. Esta congruencia es poco probable que mantener durante un azar un si p es compuesto. [1] Por lo tanto, si la igualdad es válida para uno o más valores de a , entonces decimos que p es probablemente primo .
Sin embargo, tenga en cuenta que para , la congruencia anterior es trivial. También se cumple trivialmente si p es impar y. Por esta razón, generalmente se elige un número a en el intervalo.
Cualquier una tal que
cuando n es compuesto a se conoce como mentiroso de Fermat . En este caso n se denomina pseudoprime de Fermat a la base a .
Si hacemos escoger un un tal que
entonces a se conoce como testigo de Fermat de la composición de n .
Ejemplo
Suponga que deseamos determinar si n = 221 es primo. Elija aleatoriamente 1 < a <220, digamos a = 38. Verificamos la igualdad anterior y encontramos que se cumple:
O 221 es primo, o 38 es un mentiroso de Fermat, por lo que tomamos otra a , digamos 24:
Entonces 221 es compuesto y 38 era de hecho un mentiroso de Fermat. Además, 24 es un testigo de Fermat de la composición de 221.
Algoritmo
El algoritmo se puede escribir de la siguiente manera:
- Entradas : n : un valor para probar la primalidad, n > 3; k : un parámetro que determina la cantidad de veces que se debe probar la primalidad
- Salida : compuesto si n es compuesto, de lo contrario probablemente primo
- Repite k veces:
- Elija al azar en el rango [2, n - 2]
- Si , luego devuelve compuesto
- Si nunca se devuelve el compuesto: devolver probablemente primo
Los unos valores 1 y n -1 no se utilizan como la igualdad se cumple para todos n y todos los impares n , respectivamente, por lo tanto probándolos añade ningún valor.
Complejidad
Usando algoritmos rápidos para exponenciación modular y multiprecision multiplicación, el tiempo de ejecución de este algoritmo es O ( k log 2 n log log n ) = Õ ( k log 2 n ) , donde k es el número de veces que ensayan una al azar una , y n es el valor que queremos probar para determinar si es primordial; consulte la prueba de primalidad de Miller-Rabin para obtener más detalles.
Falla
Primero, hay infinitos pseudoprimes de Fermat .
Un defecto más grave es que hay infinitos números de Carmichael . Estos son númerospara lo cual todos los valores de con son mentirosos de Fermat. Para estos números, la aplicación repetida de la prueba de primalidad de Fermat tiene el mismo rendimiento que una búsqueda aleatoria simple de factores. Si bien los números de Carmichael son sustancialmente más raros que los números primos (el límite superior de Erdös para el número de números de Carmichael es menor que la función de número primo n / log (n) ) [2] hay suficientes de ellos que la prueba de primalidad de Fermat no se usa con frecuencia en el formulario anterior. En cambio, otras extensiones más potentes de la prueba de Fermat, como Baillie – PSW , Miller – Rabin y Solovay – Strassen se utilizan con más frecuencia.
En general, si es un número compuesto que no es un número de Carmichael, entonces al menos la mitad de todos
- (es decir )
son testigos de Fermat. Como prueba de esto, dejemos ser testigo de Fermat y , , ..., sean mentirosos de Fermat. Luego
y asi todos por son testigos de Fermat.
Aplicaciones
Como se mencionó anteriormente, la mayoría de las aplicaciones utilizan una prueba de Miller – Rabin o Baillie – PSW para determinar la primacía. A veces, se realiza primero una prueba de Fermat (junto con alguna división de prueba por pequeños números primos) para mejorar el rendimiento. GMP desde la versión 3.0 utiliza una prueba de Fermat base 210 después de la división de prueba y antes de ejecutar las pruebas de Miller-Rabin. Libgcrypt usa un proceso similar con base 2 para la prueba de Fermat, pero OpenSSL no lo hace.
En la práctica, con la mayoría de las bibliotecas de números grandes, como GMP, la prueba de Fermat no es notablemente más rápida que una prueba de Miller-Rabin y puede ser más lenta para muchas entradas. [3]
Como excepción, OpenPFGW usa solo la prueba de Fermat para probables pruebas principales. El programa se usa típicamente con entradas de varios miles de dígitos con el objetivo de velocidad máxima con entradas muy grandes. Otro programa bien conocido que se basa solo en la prueba de Fermat es PGP, donde solo se usa para probar grandes valores aleatorios autogenerados (una contraparte de código abierto, GNU Privacy Guard , usa una prueba previa de Fermat seguida de pruebas de Miller-Rabin).
Referencias
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein (2001). "Sección 31.8: Prueba de primalidad". Introducción a los algoritmos (Segunda ed.). Prensa del MIT; McGraw-Hill. pag. 889–890. ISBN 0-262-03293-7.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (julio de 1980). "Los pseudoprimes a 25 · 10 9 " (PDF) . Matemáticas de la Computación . 35 (151): 1003–1026. doi : 10.1090 / S0025-5718-1980-0572872-7 . JSTOR 2006210 .
- ^ Paul Erdős (1956). "Sobre pseudoprimes y números de Carmichael". Publ. Matemáticas. Debrecen . 4 : 201–206.
- ^ Joe Hurd (2003), Verificación de la prueba de primalidad probabilística de Miller-Rabin , p. 2, CiteSeerX 10.1.1.105.3196