Prueba de primalidad de Fermat

La prueba de primalidad de Fermat es una prueba probabilística para determinar si un número es un primo probable.

Concepto

El pequeño teorema de Fermat establece que si p es primo y a no es divisible por p, entonces

ap− − 1↑ ↑ 1()modp).{displaystyle a^{p-1}equiv 1{pmod {p}}

Si uno quiere probar si p es primo, entonces podemos elegir números enteros aleatorios a no divisibles por p y ver si la igualdad sostiene Si la igualdad no se cumple para un valor de a, entonces p es compuesto. Es poco probable que esta congruencia se mantenga para un a aleatorio si p es compuesto. Por lo tanto, si la igualdad se cumple para uno o más valores de a, entonces decimos que p es probablemente primo.

Sin embargo, tenga en cuenta que la congruencia anterior es trivial para a↑ ↑ 1()modp){displaystyle aequiv 1{pmod {p}}, porque la relación congruencia es compatible con la exponentiación. También es trivial para a↑ ↑ − − 1()modp){displaystyle aequiv -1{pmod {p} si p es extraño, por la misma razón. Es por eso que uno suele elegir un azar a en el intervalo <math alttext="{displaystyle 1<a1.a.p− − 1{displaystyle 1 se hizo realidadp-1}<img alt="{displaystyle 1<a.

Cualquier a tal que

an− − 1↑ ↑ 1()modn){displaystyle a^{n-1}equiv 1{pmod {n}}

cuando n es compuesto se conoce como mentiroso de Fermat. En este caso n se llama pseudoprimo de Fermat a base a.

Si elegimos una a tal que

an− − 1≢1()modn){displaystyle a^{n-1}not equiv 1{pmodn}}

entonces a se conoce como un testigo de Fermat por la composición de n.

Ejemplo

Supongamos que deseamos determinar si n = 221 es primo. Elige al azar 1 < a < 220, digamos a = 38. Comprobamos la igualdad anterior y encontramos que se cumple:

an− − 1=38220↑ ↑ 1()mod221).{displaystyle a^{n-1}=38^{220}equiv 1{pmod {221}}

O 221 es primo, o 38 es un mentiroso de Fermat, así que tomamos otro a, digamos 24:

an− − 1=24220↑ ↑ 81≢1()mod221).{displaystyle a^{n-1}=24^{220}equiv 81not equiv 1{pmod {221}}}

Así que 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:

Inputs: n: un valor para probar la primalidad, n√3; k: un parámetro que determina el número de veces para probar la primalidad

Producto: composite si n es compuesto, de lo contrario probablemente la primera

Repito k veces:

Pick a al azar en el rango [2, n − 2

Si an− − 1≢1()modn){displaystyle a^{n-1}not equiv 1{pmodn}}, luego regresa composite

Si el compuesto nunca es devuelto: retorno probablemente la primera

Los valores a 1 y n-1 no se usan porque la igualdad es válida para todos los n y todos los impares n respectivamente, por lo tanto, probarlos no agrega ningún valor.

Complejidad

Usando algoritmos rápidos para exponenciación modular y multiplicación de precisión múltiple, el tiempo de ejecución de este algoritmo es O(k log² n registro registro n) = Õ(k registro²n), donde k es el número de veces que probamos un a aleatorio, y n es el valor que queremos probar para primalidad; consulte la prueba de primalidad de Miller-Rabin para obtener más detalles.

Defecto

Hay infinitamente muchos pseudoprimes de Fermat a cualquier base dada a título. Aún peor, hay infinitamente muchos números de Carmichael. Estos son números n{displaystyle n} para la cual Todos valores de a{displaystyle a} con gcd⁡ ⁡ ()a,n)=1{displaystyle operatorname {gcd} (a,n)=1} son mentirosos de Fermat. Para estos números, la aplicación repetida de la prueba de primalidad Fermat realiza lo mismo que una simple búsqueda aleatoria de factores. Mientras que 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 inferior a la función número principal n/log(n))) hay suficientes de ellos que la prueba de primalidad de Fermat no se utiliza a menudo en la forma anterior. En su lugar, otras extensiones más poderosas de la prueba Fermat, como Baillie–PSW, Miller–Rabin y Solovay–Strassen son más comúnmente utilizadas.

En general, si n{displaystyle n} es un número compuesto que no es un número de Carmichael, entonces al menos la mitad de todo

a▪ ▪ ()Z/nZ)Alternativa Alternativa {displaystyle ain (mathbb {Z}/nmathbb {Z}} {fn}} (i.e. gcd⁡ ⁡ ()a,n)=1{displaystyle operatorname {gcd} (a,n)=1})

son testigos de Fermat. Por prueba de esto, vamos a{displaystyle a} ser un testigo de Fermat y a1{displaystyle A_{1}, a2{displaystyle a_{2},... as{displaystyle A_{s} Ser mentirosos de Fermat. Entonces...

()a⋅ ⋅ ai)n− − 1↑ ↑ an− − 1⋅ ⋅ ain− − 1↑ ↑ an− − 1≢1()modn){displaystyle (acdot a_{i} {n-1}equiv a^{n-1}cdot a_{i} {n-1}equiv a^{n-1}not equiv 1{pmod {n}}

y todo a⋅ ⋅ ai{displaystyle acdot a_{i} para i=1,2,...,s{displaystyle i=1,2,...,s} son testigos de Fermat.

Aplicaciones

Como se mencionó anteriormente, la mayoría de las aplicaciones usan una prueba de Miller-Rabin o Baillie-PSW para primalidad. A veces, primero se realiza una prueba de Fermat (junto con alguna división de prueba por números primos pequeños) para mejorar el rendimiento. GMP desde la versión 3.0 utiliza una prueba de Fermat de 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.

Como excepción, OpenPFGW usa solo la prueba de Fermat para las pruebas principales probables. El programa se usa típicamente con entradas de varios miles de dígitos con el objetivo de máxima velocidad 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 valores aleatorios grandes autogenerados (una contraparte de código abierto, GNU Privacy Guard, usa una prueba previa de Fermat seguida de pruebas de Miller-Rabin).