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

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

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

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

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

a	Menor SPSP	a	Menor SPSP	a	Menor SPSP	a	Menor SPSP
1	9	33	545	65	33	97	49
2	2047	34	33	66	65	98	9
3	121	35	9	67	33	99	25
4	341	36	35	68	25	100	9
5	781	37	9	69	35	101	25
6	217	38	39	70	69	102	133
7	25	39	133	71	9	103	51
8	9	40	39	72	85	104	15
9	91	41	21	73	9	105	451
10	9	42	451	74	15	106	15
11	133	43	21	75	91	107	9
12	91	44	9	76	15	108	91
13	85	45	481	77	39	109	9
14	15	46	9	78	77	110	111
15	1687	47	65	79	39	111	55
16	15	48	49	80	9	112	65
17	9	49	25	81	91	113	57
18	25	50	49	82	9	114	115
19	9	51	25	83	21	115	57
20	21	52	51	84	85	116	9
21	221	53	9	85	21	117	49
22	21	54	55	86	85	118	9
23	169	55	9	87	247	119	15
24	25	56	55	88	87	120	91
25	217	57	25	89	9	121	15
26	9	58	57	90	91	122	65
27	121	59	15	91	9	123	85
28	9	60	481	92	91	124	25
29	15	61	15	93	25	125	9
30	49	62	9	94	93	126	25
31	15	63	529	95	1891	127	9
32	25	64	9	96	95	128	49

Referencias

1. Guy, Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes. §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.
2. Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff Jr. (July 1980). «The pseudoprimes to 25·10⁹». Mathematics of Computation 35 (151): 1003-1026. doi:10.1090/S0025-5718-1980-0572872-7. 
3. Louis Monier (1980). «Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms». Theoretical Computer Science 12: 97-108. doi:10.1016/0304-3975(80)90007-9. 
4. Rabin, Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12 pp. 128-138, 1980.
5. «Probable primes: How probable?». Consultado el 23 de octubre de 2020. 
6. «The Prime Glossary: probable prime». 
7. F. Arnault (August 1995). «Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases». Journal of Symbolic Computation 20 (2): 151-161. doi:10.1006/jsco.1995.1042. 
8. Zhenxiang Zhang; Min Tang (2003). «Finding Strong Pseudoprimes to Several Bases. II». Mathematics of Computation 72 (244): 2085-2097. doi:10.1090/S0025-5718-03-01545-X. 
9. Jiang, Yupeng; Deng, Yingpu (2012). «Strong pseudoprimes to the first 9 prime bases». arXiv:1207.0063v1  [math.NT]. 
10. «SPRP Records». Consultado el 3 de junio de 2015.