Fermat pseudoprime

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 de p , entonces a ^{p −1} − 1 es divisible por p . Para un número entero a > 1, 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 para la 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 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³⁴⁰ ≡ 1 (mod 341) y, por lo tanto, pasa la prueba de primalidad de Fermat para la base 2.

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

Un pseudoprime de Fermat a menudo se denomina pseudoprime , entendiéndose el modificador Fermat .

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

Propiedades

Distribución

Hay infinitos pseudoprimos con cualquier base a > 1. En 1904, Cipolla mostró cómo producir un número infinito de pseudoprimos con base a > 1: Sea A = ( a ^p - 1)/( a - 1) y sea B = ( a ^p + 1)/( a + 1), donde p es cualquier primo impar. Entonces n = AB es compuesto y es un pseudoprimo de la base a . ^[3] Por ejemplo, si a = 2 y p = 5, entonces A = 31, B = 11 y n = 341 son pseudoprimos en base 2.

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

A partir de 17·257, el producto de números de Fermat consecutivos es un pseudoprimo de base 2, al igual que todos los compuestos de Fermat y Mersenne .

La probabilidad de que un número compuesto n pase la prueba de Fermat se aproxima 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 para una 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 . ^[6] $n\to \infty$ $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 2 ^d − 2 se llama número superPoulet . Hay infinitos números de Poulet que no son números superPoulet. ^[7]

Los pseudoprimos de Fermat más pequeños

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

(secuencia A007535 en la OEIS )

Lista de pseudoprimos de Fermat en base fija n

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

¿Qué bases b hacen que n sea un pseudoprimo de Fermat?

Si el compuesto es par, entonces es un pseudoprimo de Fermat con respecto a la base trivial . Si el compuesto es impar, entonces es un pseudoprimo de Fermat para las bases triviales . $n$ $n$ $b\equiv 1{\pmod {n}}$ $n$ $n$ $b\equiv \pm 1{\pmod {n}}$

Para cualquier compuesto , el número de bases distintas módulo , para las cuales es una base pseudoprime de Fermat , es ^[8]^{: Thm. 1, pág. 1392} $n$ $b$ $n$ $n$ $b$

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

donde están los distintos factores primos de . Esto incluye las bases triviales. $p_{1},\dots,p_{k}$ $n$

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

Todo compuesto impar es un pseudoprimo de Fermat con al menos dos bases no triviales , a menos que sea una potencia de 3. ^[8]^{: Cor. 1, pág. 1393} $n$ $n$ $n$

Para 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 pseudoprimo solo para la base trivial 1 módulo n .

Para obtener más información ( n = 201 a 5000), consulte ^[9] esta página no define n es un pseudoprimo a una base congruente con 1 o -1 (mod n ). Cuando p es primo, p ² es un pseudoprimo de Fermat en base b si y sólo si p es un primo de Wieferich en base b . Por ejemplo, 1093 ² = 1194649 es un pseudoprimo de Fermat en base 2, y 11 ² = 121 es un pseudoprimo de Fermat en 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 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 )

La base mínima b > 1 en la que n es un pseudoprimo de la base b (o número primo) es

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 el OEIS )

El número de valores de b para n debe dividirse ( 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 sólo si n es un primo o un número de Carmichael (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997), el cociente = 2 si y sólo si n está en la secuencia: 4, 6, 15, 91, 703, 1891 , 2701, 11305, 12403, 13981, 18721, ... A191311) $\varphi$

El menor número con n valores de b es (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 el OEIS ) ( si y solo si n es par y no tociente de un número libre de cuadrados , entonces el n- ésimo término de esta secuencia es 0)

Pseudoprimos débiles

Un número compuesto n que satisface eso se llama pseudoprimo débil en base b . Un pseudoprimo con 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. ^[10] Los pseudoprimos menos débiles en base b = 1, 2, ... son: $b^{n}\equiv b{\pmod {n}}$

4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 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. Excepto 561, solo los semiprimos pueden ocurrir en la secuencia anterior, pero no todos los semiprimos menores que 561 ocurren, un semiprimo pq ( p ≤ q ) menor que 561 ocurre en las secuencias anteriores si y solo si p − 1 divide q − 1. (ver OEIS : A108574 ) Además, el pseudoprimo más pequeño de la base n (tampoco es necesario exceder n ) ( OEIS : A090086 ) también suele ser semiprimo, el primer contraejemplo es A090086(648) = 385 = 5 × 7 × 11.

Si requerimos 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 el 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 cuya primalidad no ha sido "certificada" (es decir, rigurosamente probada), pero que se han sometido 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 números primos grandes. El algoritmo habitual para generar números primos es generar números impares aleatorios y probar su primalidad. Sin embargo, las pruebas deterministas de primalidad son lentas. Si el usuario está dispuesto a tolerar una posibilidad 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

^ ab Samuel S. Wagstaff Jr. (2013). El placer del factoraje. Providence, RI: Sociedad Estadounidense de Matemáticas. ISBN 978-1-4704-1048-3.
^ ab 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 . Prensa CRC. págs. 10-23. ISBN 978-1-58488-820-8.
^ Paulo Ribenboim (1996). El nuevo libro de registros de números primos . Nueva York: Springer-Verlag . pag. 108.ISBN _ 0-387-94457-5.
^ ab Pomerancia, Carl ; Selfridge, John L .; Wagstaff, Samuel S. Jr. (julio de 1980). "Los pseudoprimos a 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.
^ Alford, WR ; Granville, Andrés ; Pomerancia, 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.
^ Kim, Su Hee; Pomerancia, Carl (1989). "La probabilidad de que un número primo aleatorio sea compuesto". Matemáticas de la Computación . 53 (188): 721–741. doi :10.2307/2008733. JSTOR 2008733.
^ Sierpinski, W. (15 de febrero de 1988), "Capítulo V.7", en Ed. A. Schinzel (ed.), Teoría elemental de los números , Biblioteca de Matemáticas de Holanda Septentrional (2 subed.), Ámsterdam: Holanda Septentrional, p. 232, ISBN 9780444866622
^ ab Robert Baillie; Samuel S. Wagstaff Jr. (octubre de 1980). «Lucas Pseudoprimos» (PDF) . Matemáticas de la Computación . 35 (152): 1391-1417. doi : 10.1090/S0025-5718-1980-0583518-6 . SEÑOR 0583518. Archivado (PDF) desde el original el 6 de septiembre de 2006.
^ "Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) - Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher". de.m.wikibooks.org . Consultado el 21 de abril de 2018 .
^ Michón, 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 para pseudoprime