Prueba de primalidad de Fermat

Prueba de primalidad probabilística

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

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$

Si queremos comprobar si p es primo, podemos elegir números enteros aleatorios a no divisibles por p y ver si se cumple la congruencia. Si no se cumple para un valor de a , entonces p es compuesto. Es poco probable que esta congruencia se cumpla para un valor aleatorio a si p es compuesto. ^[1] 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 se cumple trivialmente para , porque la relación de congruencia es compatible con la exponenciación . También se cumple trivialmente para si p es impar, por la misma razón. Es por eso que uno generalmente elige un a aleatorio en el intervalo . ${\displaystyle a\equiv 1{\pmod {p}}}$ ${\displaystyle a\equiv -1{\pmod {p}}}$ ${\displaystyle 1<a<p-1}$

Cualquiera tal que

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

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

Si elegimos un a tal que

${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$

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

Ejemplo

Supongamos que queremos determinar si n  = 221 es primo. Elegimos aleatoriamente 1 < a < 220, digamos a  = 38. Comprobamos la congruencia anterior y descubrimos que se cumple:

${\displaystyle a^{n-1}=38^{220}\equiv 1{\pmod {221}}.}$

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

${\displaystyle a^{n-1}=24^{220}\equiv 81\not \equiv 1{\pmod {221}}.}$

Por lo tanto, 221 es compuesto y 38 fue, en efecto, un mentiroso de Fermat. Además, 24 es un testigo de Fermat para 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

Repetir k veces:

Elija un número aleatorio en el rango [2, n − 2]

Si , entonces devuelve compuesto ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$

Si nunca se devuelve el compuesto: devuelve probablemente el primo

Los valores a 1 y n -1 no se utilizan ya que la igualdad se cumple para todos los n y todos los n impares respectivamente, por lo tanto, probarlos no agrega ningún valor.

Complejidad

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

Defecto

Hay infinitos pseudoprimos de Fermat para cualquier base dada a > 1. ^{[1] : Teorema 1} Peor aún, hay infinitos números de Carmichael . ^[2] Estos son números para los cuales todos los valores de con son mentirosos de Fermat. Para estos números, la aplicación repetida de la prueba de primalidad de Fermat realiza lo mismo que una simple búsqueda aleatoria 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 ^[3] es menor que la función de número primo n/log(n) ), hay suficientes de ellos como para que la prueba de primalidad de Fermat no se use a menudo en la forma anterior. En cambio, se usan más comúnmente otras extensiones más poderosas de la prueba de Fermat, como Baillie–PSW , Miller–Rabin y Solovay–Strassen . ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle \operatorname {gcd} (a,n)=1}$

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

${\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$(es decir ) ${\displaystyle \operatorname {gcd} (a,n)=1}$

son testigos de Fermat. Para demostrarlo, sea testigo de Fermat y , , ..., mentirosos de Fermat. Entonces ${\displaystyle a}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{2}}$ ${\displaystyle a_{s}}$

${\displaystyle (a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}}$

y por tanto todos son testigos de Fermat. ${\displaystyle a\cdot a_{i}}$ ${\displaystyle i=1,2,...,s}$

Aplicaciones

Como se mencionó anteriormente, la mayoría de las aplicaciones utilizan una prueba de Miller-Rabin o Baillie-PSW para determinar la primalidad. A veces, primero se realiza una prueba de Fermat (junto con una división de prueba por primos pequeños) para mejorar el rendimiento. GMP, desde la versión 3.0, utiliza una prueba de Fermat en base 210 después de la división de prueba y antes de ejecutar las pruebas de Miller-Rabin. Libgcrypt utiliza 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. ^[4]

Como excepción, OpenPFGW utiliza únicamente la prueba de Fermat para la comprobación de primos probables. El programa se utiliza normalmente con entradas de varios miles de dígitos con el objetivo de alcanzar la máxima velocidad con entradas muy grandes. Otro programa conocido que se basa únicamente en la prueba de Fermat es PGP , donde solo se utiliza para la comprobación de valores aleatorios grandes autogenerados (un programa homólogo de código abierto, GNU Privacy Guard , utiliza una prueba previa de Fermat seguida de pruebas de Miller-Rabin).

Referencias

1. Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (julio de 1980). "Los pseudoprimos hasta 25·109" (PDF) . Matemáticas de la computación . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR  2006210.
2. Alford, WR ; Granville, Andrew ; Pomerance, Carl (1994). "Hay infinitos números de Carmichael" (PDF) . Anales de Matemáticas . 140 (3): 703–722. doi :10.2307/2118576. JSTOR  2118576.
3. Paul Erdős (1956). "Sobre pseudoprimos y números de Carmichael". Publ. Matemáticas. Debrecen . 4 : 201–206. SEÑOR  0079031.
4. Joe Hurd (2003), Verificación de la prueba de primalidad probabilística de Miller-Rabin , pág. 2, CiteSeerX 10.1.1.105.3196 

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2001). "Sección 31.8: Pruebas de primalidad". Introducción a los algoritmos (segunda edición). MIT Press; McGraw-Hill. pág. 889–890. ISBN 0-262-03293-7.{{cite book}}: CS1 maint: multiple names: authors list (link)