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 .

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 se quiere comprobar si p es primo, se pueden elegir 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 improbable que esta congruencia se cumpla para un a aleatorio 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${\displaystyle a\equiv 1{\pmod {p}}}$, porque la relación de congruencia es compatible con la exponenciación . También se cumple trivialmente para${\displaystyle a\equiv -1{\pmod {p}}}$Si p es impar, por la misma razón. Por eso, normalmente se elige un valor aleatorio a en el intervalo${\displaystyle 1<a<p-1}$.

Cualquiera de tal tipo 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 en 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 .

Supongamos que queremos determinar si n  =  221 es primo. Elegimos aleatoriamente 1 < a < 220, digamos a  =  38. Verificamos la congruencia anterior y encontramos 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 era, en efecto, un mentiroso de Fermat. Además, 24 es un testigo de Fermat de la composición de 221.

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 el número de veces que se prueba la primalidad.

Salida : compuesto si n es compuesto, de lo contrario probablemente primo

Repetir k veces:

Elige un número al azar en el rango [2, n − 2].

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

Si nunca se devuelve compuesto: devolver probablemente primo

Los valores de 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 que probarlos no añade ningún valor.

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${\displaystyle n}$para los cuales todos los valores de${\displaystyle a}$con${\displaystyle \operatorname {gcd} (a,n)=1}$son mentirosos de Fermat. Para estos números, la aplicación repetida de la prueba de primalidad de Fermat produce el mismo resultado 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 como para que la prueba de primalidad de Fermat no se utilice con frecuencia en la forma anterior. En cambio, se utilizan con mayor frecuencia otras extensiones más potentes de la prueba de Fermat, como Baillie-PSW , Miller-Rabin y Solovay-Strassen .

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

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

son testigos de Fermat. Para probar esto,${\displaystyle a}$ser testigo de Fermat y${\displaystyle a_{1}}$,${\displaystyle a_{2}}$, ...,${\displaystyle a_{s}}$Sean mentirosos de Fermat. Entonces

${\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 así todos${\displaystyle a\cdot a_{i}}$para${\displaystyle i=1,2,...,s}$son testigos de Fermat.

Análogo al residuo de Lucas-Lehmer ,${\displaystyle r=a^{n-1}{\pmod {n}}}$Se denomina residuo de Fermet de n a base a . Existen algunas variantes que producen diferentes tipos de residuos, ^{[ 4 ]} siendo el más importante el residuo primo probable fuerte (SPRP). ^{[ 5 ]}

Como se mencionó anteriormente, la mayoría de las aplicaciones utilizan la prueba de Miller-Rabin o Baillie-PSW para determinar la primalidad. En ocasiones, se realiza primero una prueba de Fermat (junto con algunas divisiones de prueba por números 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.

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. ^{[ 8 ]}

Como excepción, OpenPFGW utiliza únicamente la prueba de Fermat para la comprobación de números primos probables. El programa se suele utilizar con entradas de miles de dígitos, buscando la máxima velocidad con entradas muy grandes. Otro programa conocido que se basa exclusivamente en la prueba de Fermat es PGP, donde se utiliza únicamente para la comprobación de valores aleatorios grandes autogenerados (una contraparte de código abierto, GNU Privacy Guard , utiliza una prueba previa de Fermat seguida de pruebas de Miller-Rabin).

• 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  edición). MIT Press; McGraw-Hill. págs.  889-890 . ISBN 0-262-03293-7.