Número pseudoprimo fuerte

Un número pseudoprimo fuerte es un número compuesto que satisface el test de primalidad de Miller-Rabin. Todos los números primos pasan esta prueba, pero también pasa una pequeña fracción de los compuestos, lo que los convierte en números pseudoprimos.

A diferencia de los pseudoprimos de Fermat, para los cuales existen números que son pseudoprimos para todas las bases de números coprimos (los números de Carmichael), no hay compuestos que sean pseudoprimos fuertes para todas las bases.

Motivación y primeros ejemplos[editar]

Supóngase que se quiere investigar si n = 31697 es un probable primo (PRP). Se elige entonces por ejemplo la base a = 3, inspirada en el pequeño teorema de Fermat, y se calcula:

${\displaystyle 3^{31696}\equiv 1{\pmod {31697}}}$

Esto demuestra que 31697 es un PRP de Fermat (en base 3), por lo que se puede sospechar que es un número primo. Ahora, se reduce a la mitad repetidamente el exponente:

${\displaystyle 3^{15848}\equiv 1{\pmod {31697}}}$

${\displaystyle 3^{7924}\equiv 1{\pmod {31697}}}$

${\displaystyle 3^{3962}\equiv 28419{\pmod {31697}}}$

El primer par de veces no arroja nada interesante (el resultado sigue siendo 1 módulo 31697), pero en el exponente 3962 se observa un resultado que no es ni 1 ni menos 1 (es decir, 31696) módulo 31697. Esto prueba que 31697 es de hecho compuesto (es igual a 29×1093). Tomando el módulo a primo, el residuo 1 no puede tener otras raíces cuadradas que 1 y menos 1. Esto demuestra que 31697 no es un pseudoprimo fuerte en base 3.

Para otro ejemplo, elíjase n = 47197 y calcúlese de la misma manera:

${\displaystyle 3^{47196}\equiv 1{\pmod {47197}}}$

${\displaystyle 3^{23598}\equiv 1{\pmod {47197}}}$

${\displaystyle 3^{11799}\equiv 1{\pmod {47197}}}$

En este caso, el resultado sigue siendo 1 (mod 47197) hasta llegar a un exponente impar. En esta situación, se dice que 47197 es un primo probable fuerte de base 3. Debido a que resulta que este PRP es de hecho compuesto (se puede ver eligiendo otras bases que no sean 3), se tiene que 47197 es un pseudoprimo fuerte respecto a la base 3.

Finalmente, considérese n = 74593, de donde se obtiene:

${\displaystyle 3^{74592}\equiv 1{\pmod {74593}}}$

${\displaystyle 3^{37296}\equiv 1{\pmod {74593}}}$

${\displaystyle 3^{18648}\equiv 74592{\pmod {74593}}}$

Aquí se llega a menos 1 módulo 74593, situación que es perfectamente posible con un primo. Cuando esto ocurre, se detiene el cálculo (aunque el exponente aún no es impar) y se dice que 74593 es un primo probable fuerte (y, como resultado, un pseudoprimo fuerte) en base 3.

Definición formal[editar]

Un número compuesto impar n = d · 2^s + 1, donde d es impar, se llama pseudoprimo fuerte (de Fermat) respecto a la base exponencial a si:

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

o

${\displaystyle a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}\quad {\mbox{para algún valor }}0\leq r<s.}$

(Si un número n satisface una de las condiciones anteriores y aún no sabemos si es primo, es más preciso referirse a él como un probable primo fuerte en base a. Pero si sabemos que n no es primo, entonces podemos usar el término pseudoprimo fuerte.)

La definición se cumple trivialmente si a ≡ ±1 (mod n), por lo que estas bases triviales a menudo se excluyen.

Guy dio erróneamente una definición con solo la primera condición, que no todos los números primos cumplen.^[1]​

Propiedades de los pseudoprimos fuertes[editar]

Un pseudoprimo fuerte respecto a la base a es siempre un número pseudoprimo de Euler-Jacobi, un número pseudoprimo de Euler^[2]​ y un número pseudoprimo de Fermat respecto a esa base, pero no todos los pseudoprimos de Euler y Fermat son pseudoprimos fuertes. Los números de Carmichael pueden ser pseudoprimos fuertes para algunas bases, por ejemplo, 561 es un pseudoprimo fuerte para la base 50, pero no para todas las bases.

Un número compuesto n es un pseudoprimo fuerte para como máximo una cuarta parte de todas las bases por debajo de n;^[3]​^[4]​ y por lo tanto, no hay números de Carmichael fuertes, números que son pseudoprimos fuertes para todas las bases. Por lo tanto, dada una base aleatoria, la probabilidad de que un número sea un pseudoprimo fuerte para esa base es menor que 1/4, lo que forma la base del test de primalidad de Miller-Rabin ampliamente utilizado. La probabilidad real de un fallo es generalmente mucho menor. Paul Erdős y Carl Pomerance demostraron en 1986 que si un entero aleatorio n pasa la prueba de primalidad de Miller-Rabin respecto a una base aleatoria b, entonces n es casi seguramente un primo.^[5]​ Por ejemplo, de los primeros 25.000.000.000 de enteros positivos, hay 1.091.987.405 enteros que son primos probables de base 2, pero solo 21.853 de ellos son pseudoprimos, y aún menos son pseudoprimos fuertes, ya que el último es un subconjunto del primero.^[6]​ Sin embargo, Arnault^[7]​ halló un número de Carmichael de 397 dígitos que es un pseudoprimo fuerte para cada base menor que 307.

Una forma de reducir la posibilidad de que dicho número se declare incorrectamente como probablemente primo es combinar una prueba de primo probable fuerte con una prueba de primo probable de Lucas, como en el test de primalidad de Baillie-PSW.

Hay infinitos pseudoprimos fuertes para cualquier base.^[2]​

Ejemplos[editar]

Los primeros pseudoprimos fuertes respecto a la base exponencial 2 son:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ... (sucesión A001262 en OEIS).

Los primeros respecto a la base exponencial 3 son:

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ... (sucesión A020229 en OEIS).

Los primeros respecto a la base exponencial 5 son:

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (sucesión A020231 en OEIS).

Para la base exponencial 4, consúltese (sucesión A020230 en OEIS), y para las bases exponenciales de 6 a 100, consúltese de (sucesión A020232 en OEIS) a (sucesión A020326 en OEIS).

Al probar las condiciones anteriores en varias bases, se obtienen pruebas de primalidad algo más potentes que al usar una sola base. Por ejemplo, solo hay 13 números menores que 25 · 10⁹ que son pseudoprimos fuertes en las bases 2, 3 y 5 simultáneamente. Se enumeran en la Tabla 7 de.^[2]​ El número más pequeño es 25326001. Esto significa que, si n es menor que 25326001 y n es un primo probable fuerte en las bases 2, 3 y 5, entonces n es primo.

Llevando esta idea más adelante, entonces 3825123056546413051 es el número más pequeño que es un pseudoprimo fuerte de las 9 bases exponenciales 2, 3, 5, 7, 11, 13, 17, 19 y 23.^[8]​ ^[9]​

Por lo tanto, si n es menor que 3825123056546413051 y n es un primo fuerte probable de estas 9 bases, entonces n es primo.

Mediante la elección juiciosa de bases que no son necesariamente primas, se pueden construir pruebas aún mejores. Por ejemplo, no hay ningún compuesto ${\displaystyle <2^{64}}$ que sea un pseudoprimo fuerte para las siete bases 2, 325, 9375, 28178, 450775, 9780504 y 1795265022.^[10]​

Pseudoprimo fuerte más pequeño respecto a la base exponencial a[editar]

Referencias[editar]