Pseudoprimo de Fermat

Número compuesto que pasa la prueba de primalidad probable de Fermat

En teoría de números , los pseudoprimos de Fermat constituyen la clase más importante de pseudoprimos que provienen del pequeño teorema de Fermat .

Definición

El pequeño teorema de Fermat establece que si p es primo y a es coprimo con p , entonces a ^{p −1}  − 1 es divisible por p . Para un entero positivo a , si un entero compuesto x divide a ^{x −1}  − 1, entonces x se llama pseudoprimo de Fermat en base a . ^{[1] : Def. 3.32} En otras palabras, un entero compuesto es un pseudoprimo de Fermat en base a si pasa con éxito la prueba de primalidad de Fermat para la base a . ^[2] La afirmación falsa de que todos los números que pasan la prueba de primalidad de Fermat para la base 2 son primos se llama hipótesis china .

El pseudoprimo de Fermat en base 2 más pequeño es 341. No es un primo, ya que es igual a 11·31, pero satisface el pequeño teorema de Fermat: 2 ^{· 340} ≡ 1 (mod 341) y, por lo tanto, pasa la prueba de primalidad de Fermat para la base 2.

Los pseudoprimos en base 2 a veces se denominan números de Sarrus , en honor a PF Sarrus , quien descubrió que 341 tiene esta propiedad, números de Poulet , en honor a P. Poulet , quien hizo una tabla de dichos números, o fermatianos (secuencia A001567 en la OEIS ).

A un pseudoprimo de Fermat se le suele llamar pseudoprimo , sobreentendiéndose por tal el modificador Fermat .

Un número entero x que es un pseudoprimo de Fermat para todos los valores de a que son coprimos con x se llama número de Carmichael . ^{[2] [1] : Def. 3.34}

Propiedades

Distribución

Hay infinitos pseudoprimos para cualquier base dada a > 1. En 1904, Cipolla mostró cómo producir un número infinito de pseudoprimos para base a > 1: sea A = ( a ^p - 1)/( a - 1) y sea B = ( a ^p + 1)/( a + 1), donde p es un número primo que no divide a ( a ² - 1). Entonces n = AB es compuesto, y es un pseudoprimo para base a . ^{[3] [4]} Por ejemplo, si a = 2 y p = 5, entonces A = 31, B = 11, y n = 341 es un pseudoprimo para base 2.

De hecho, hay infinitos pseudoprimos fuertes en cualquier base mayor que 1 (ver Teorema 1 de ^[5] ) y infinitos números de Carmichael, ^[6] pero son comparativamente raros. Hay tres pseudoprimos en base 2 menores de 1000, 245 menores de un millón y 21853 menores de 25·10 ⁹ . Hay 4842 pseudoprimos fuertes en base 2 y 2163 números de Carmichael menores de este límite (ver Tabla 1 de ^[5] ).

A partir de 17·257, el producto de números de Fermat consecutivos es un pseudoprimo de base 2, y también lo son todos los números compuestos de Fermat y de Mersenne .

La probabilidad de que un número compuesto n pase la prueba de Fermat se acerca a cero para . Específicamente, Kim y Pomerance demostraron lo siguiente: La probabilidad de que un número impar aleatorio n ≤ x sea un pseudoprimo de Fermat en base aleatoria es menor que 2,77·10 ^-8 para x= 10 ¹⁰⁰ , y es como máximo (log x) ^-197 <10 ^{-10 000} para x≥10 ^{100 000} . ^[7] ${\displaystyle n\to \infty }$ ${\displaystyle 1<b<n-1}$

Factorizaciones

Las factorizaciones de los 60 números de Poulet hasta 60787, incluidos 13 números de Carmichael (en negrita), se encuentran en la siguiente tabla.

(secuencia A001567 en la OEIS )

Un número de Poulet cuyos divisores d dividen a 2 ^d − 2 se denomina supernúmero de Poulet . Hay una cantidad infinita de números de Poulet que no son supernúmeros de Poulet. ^[8]

Pseudoprimos de Fermat más pequeños

El pseudoprimo más pequeño para cada base a ≤ 200 se da en la siguiente tabla; los colores marcan el número de factores primos. A diferencia de la definición al principio del artículo, los pseudoprimos inferiores a a están excluidos de la tabla. (Para permitir pseudoprimos inferiores a a , consulte OEIS : A090086 )

(secuencia A007535 en la OEIS )

Lista de pseudoprimos de Fermat en base fijanorte

Para obtener más información (base 31 a 100), consulte OEIS : A020159 a OEIS : A020228 , y para todas las bases hasta 150, consulte la tabla de pseudoprimos de Fermat (texto en alemán), esta página no define n es un pseudoprimo con una base congruente con 1 o -1 (mod n )

BasesbPara cualnortees un pseudoprimo de Fermat

Si el compuesto es par, entonces es un pseudoprimo de Fermat en base trivial . Si el compuesto es impar, entonces es un pseudoprimo de Fermat en base trivial . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle b\equiv 1{\pmod {n}}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle b\equiv \pm 1{\pmod {n}}}$

Para cualquier compuesto , el número de bases distintas módulo , para el cual es una base pseudoprima de Fermat , es ^{[9] : Teoría 1, pág. 1392} ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle b}$

${\displaystyle \prod _{i=1}^{k}\gcd(p_{i}-1,n-1)}$

¿Dónde están los factores primos distintos de ? Esto incluye las bases triviales. ${\displaystyle p_{1},\dots ,p_{k}}$ ${\displaystyle n}$

Por ejemplo, para , este producto es . Para , la base no trivial más pequeña es . ${\displaystyle n=341=11\cdot 31}$ ${\displaystyle \gcd(10,340)\cdot \gcd(30,340)=100}$ ${\displaystyle n=341}$ ${\displaystyle b=2}$

Todo compuesto impar es un pseudoprimo de Fermat hasta al menos dos bases no triviales módulo a menos que sea una potencia de 3. ^{[9] : Cor. 1, p. 1393} ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Para un número compuesto n < 200, la siguiente es una tabla de todas las bases b < n donde n es un pseudoprimo de Fermat. Si un número compuesto n no está en la tabla (o n está en la secuencia A209211), entonces n es un pseudoprimo solo en la base trivial 1 módulo n .

Para más información ( n = 201 a 5000), véase ^[10] esta página no define n como un pseudoprimo con una base congruente con 1 o -1 (mod n ). Cuando p es un primo, p ² es un pseudoprimo de Fermat con base b si y solo si p es un primo de Wieferich con base b . Por ejemplo, 1093 ² = 1194649 es un pseudoprimo de Fermat con base 2, y 11 ² = 121 es un pseudoprimo de Fermat con base 3.

El número de valores de b para n es (Para n primo, el número de valores de b debe ser n - 1, ya que todos los b satisfacen el pequeño teorema de Fermat )

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, ... (secuencia A063994 en la OEIS )

Los números de base b > 1 cuyo número n es un pseudoprimo de base b (o número primo) son

2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, ... (secuencia A105222 en la OEIS )

El número de valores de b para n debe dividir ( n ), o A000010( n ) = 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, ... (El cociente puede ser cualquier número natural, y el cociente = 1 si y solo si n es primo). o un número de Carmichael (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997), el cociente = 2 si y solo si n está en la secuencia: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... A191311) ${\displaystyle \varphi }$

El menor número con n valores de b son (o 0 si no existe tal número)

1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, 0, 286, 17, 1854, 19, 3820, 891, 2752, 23, 1128, 595, 2046, 0, 532, 29, 1770, 31, 9952, 425, 1288, 0, 2486, 37, 8474, 0, 742, 41, 3486, 43, 7612, 5589, 2356, 47, 13584, 325, 9850, 0, ... (secuencia A064234 en la OEIS ) ( si y solo si n es par y no total de un número libre de cuadrados , entonces el término n de esta secuencia es 0)

Pseudoprimos débiles

Un número compuesto n que satisface que se llama pseudoprimo débil en base b . Un pseudoprimo en base a (según la definición habitual) satisface esta condición. Por el contrario, un pseudoprimo débil que es coprimo con la base es un pseudoprimo en el sentido habitual, de lo contrario este puede ser el caso o no. ^[11] Los pseudoprimos menos débiles en base b = 1, 2, ... son: ${\displaystyle b^{n}\equiv b{\pmod {n}}}$

4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 4, 4, 6, 4, 4, 6, 46, 4, 4, 10, ... (secuencia A000790 en la OEIS )

Todos los términos son menores o iguales que el número de Carmichael más pequeño, 561. A excepción de 561, solo los semiprimos pueden ocurrir en la secuencia anterior, pero no todos los semiprimos menores de 561 ocurren, un semiprimo pq ( p ≤ q ) menor que 561 ocurre en las secuencias anteriores si y solo si p − 1 divide a q − 1. (ver OEIS : A108574 ) Además, el pseudoprimo más pequeño en base n (tampoco necesariamente mayor que n ) ( OEIS : A090086 ) también es usualmente semiprimo, el primer contraejemplo es A090086(648) = 385 = 5 × 7 × 11.

Si requerimos que n > b , son (para b = 1, 2, ...)

4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51, ... (secuencia A239293 en la OEIS )

Los números de Carmichael son pseudoprimos débiles para todas las bases.

El pseudoprimo más pequeño, incluso débil, en base 2 es 161038 (ver OEIS : A006935 ).

Pseudoprimos de Euler-Jacobi

Otro enfoque es utilizar nociones más refinadas de pseudoprimalidad, por ejemplo, pseudoprimos fuertes o pseudoprimos de Euler-Jacobi , para los cuales no existen análogos de los números de Carmichael . Esto conduce a algoritmos probabilísticos como la prueba de primalidad de Solovay-Strassen , la prueba de primalidad de Baillie-PSW y la prueba de primalidad de Miller-Rabin , que producen lo que se conoce como primos de grado industrial . Los primos de grado industrial son números enteros para los cuales la primalidad no ha sido "certificada" (es decir, rigurosamente probada), pero han sido sometidos a una prueba como la prueba de Miller-Rabin que tiene una probabilidad de falla distinta de cero, pero arbitrariamente baja.

Aplicaciones

La rareza de estos pseudoprimos tiene importantes implicaciones prácticas. Por ejemplo, los algoritmos de criptografía de clave pública como RSA requieren la capacidad de encontrar rápidamente primos grandes. El algoritmo habitual para generar números primos es generar números impares aleatorios y probar su primalidad. Sin embargo, las pruebas de primalidad deterministas son lentas. Si el usuario está dispuesto a tolerar una probabilidad arbitrariamente pequeña de que el número encontrado no sea un número primo sino un pseudoprimo, es posible utilizar la prueba de primalidad de Fermat, mucho más rápida y sencilla .

Referencias

1. Samuel S. Wagstaff Jr. (2013). El placer de factorizar. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3.
2. Desmedt, Yvo (2010). "Esquemas de cifrado". En Atallah, Mikhail J. ; Blanton, Marina (eds.). Manual de algoritmos y teoría de la computación: temas y técnicas especiales . CRC Press. págs. 10–23. ISBN 978-1-58488-820-8.
3. Paulo Ribenboim (1996). El nuevo libro de registros de números primos . Nueva York: Springer-Verlag . pág. 108. ISBN. 0-387-94457-5.
4. Hamahata, Yoshinori; Kokubun, Y. (2007). «Cipolla Pseudoprimos» (PDF) . Diario de secuencias enteras . 10 (8).
5. Pomerance, Carl ; Selfridge, John L. ; Wagstaff, Samuel S. 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 . Archivado (PDF) desde el original el 4 de marzo de 2005.
6. 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. Archivado (PDF) desde el original el 4 de marzo de 2005.
7. Kim, Su Hee; Pomerance, Carl (1989). "La probabilidad de que un primo aleatorio probable sea compuesto". Matemáticas de la computación . 53 (188): 721–741. doi :10.2307/2008733. JSTOR  2008733.
8. Sierpinski, W. (15 de febrero de 1988), "Capítulo V.7", en Ed. A. Schinzel (ed.), Teoría elemental de números , Biblioteca matemática de Holanda Septentrional (2.ª subedición), Ámsterdam: Holanda Septentrional, pág. 232, ISBN 9780444866622
9. Robert Baillie; Samuel S. Wagstaff Jr. (octubre de 1980). "Lucas Pseudoprimes" (PDF) . Matemáticas de la computación . 35 (152): 1391–1417. doi : 10.1090/S0025-5718-1980-0583518-6 . MR  0583518. Archivado (PDF) desde el original el 6 de septiembre de 2006.
10. "Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) - Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher". de.m.wikibooks.org . Consultado el 21 de abril de 2018 .
11. Michon, Gerard. "Pseudoprimos, pseudoprimos débiles, pseudoprimos fuertes, primalidad - Numericana". www.numericana.com . Consultado el 21 de abril de 2018 .

Enlaces externos

• WF Galway y Jan Feitsma, Tablas de pseudoprimos en base 2 y datos relacionados (lista completa de todos los pseudoprimos en base 2 por debajo de 2 ⁶⁴ , incluida la factorización, los pseudoprimos fuertes y los números de Carmichael)
• Una investigación sobre pseudoprime