Pseudoprima 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 de p, entonces a^p−1 − 1 es divisible por p. Para un entero a > 1, si un entero compuesto x divide a a^x−1 − 1, entonces x se denomina pseudoprimo de Fermat a base a. En otras palabras, un número 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. 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³⁴⁰ ≡ 1 (mod 341) y así pasa el Prueba de primalidad de Fermat para la base 2.

Los pseudoprimos en base 2 a veces se llaman números de Sarrus, en honor a P. F. 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 el OEIS).

Un pseudoprimo de Fermat a menudo se denomina pseudoprimo, entendiéndose 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 denomina número de Carmichael.

Propiedades

Distribución

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

De hecho, hay infinitos pseudoprimos fuertes en cualquier base mayor que 1 (ver Teorema 1 de ) e infinitamente muchos números de Carmichael, 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 de base 2 y 2163 números de Carmichael por debajo de este límite (ver Tabla 1 de).

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.

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

Un número de Poulet cuyos divisores d dividen a 2^d − 2 se denomina supernúmero de Poulet. Hay infinitos números de Poulet que no son supernúmeros de Poulet.

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 comienzo del artículo, los pseudoprimos debajo de a están excluidos de la tabla. (Para permitir pseudoprimos por debajo de a, consulte OEIS: A090086)

(secuencia A007535 en el OEIS)

Lista de pseudoprimos de Fermat en base fija n

Para obtener más información (base 31 a 100), consulte 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 forman n un pseudoprimo de Fermat?

Si compuesto n{displaystyle n} es incluso, entonces n{displaystyle n} es un Fermat pseudoprime a la base trivial b↑ ↑ 1()modn){displaystyle bequiv 1{pmod {n}}. Si compuesto n{displaystyle n} es extraño, entonces n{displaystyle n} es un Fermat pseudoprime a las bases triviales b↑ ↑ ± ± 1()modn){displaystyle bequiv pm 1{pmod {n}}.

Para cualquier compuesto n{displaystyle n}, el Número de bases distintas b{displaystyle b} modulo n{displaystyle n}, por el cual n{displaystyle n} es una base de Fermat pseudoprime b{displaystyle b}, es

∏ ∏ i=1kgcd()pi− − 1,n− − 1){displaystyle prod _{i=1}gcd(p_{i}-1,n-1)}

Donde p1,...... ,pk{displaystyle P_{1},dotsp_{k} son los factores principales distintos n{displaystyle n}. Esto incluye las bases triviales.

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

Cada compositor extraño n{displaystyle n} es un fermat pseudoprime al menos dos bases notriviales modulo n{displaystyle n} a) n{displaystyle n} es un poder de 3.

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

Para obtener más información (n = 201 a 5000), consulte, esta página no define n es un pseudoprimo a una base congruente con 1 o -1 (mod n). Cuando p es un primo, p² es un pseudoprimo de Fermat en base b si y solo 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 los valores de b para n son (Para n primo, el número de los valores de b debe ser n - 1, ya que todas las 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,... A063994 en el OEIS)

La menor base b > 1 que n es un pseudoprimo a 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... A105222 en el OEIS)

El número de valores b para n debe dividirse φ φ {displaystyle varphi }()n), o A000010(n) = 1, 2, 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, 16, 16, 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 número primo o 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)

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, A064234 en el OEIS n es incluso y no totiente de número libre de cuadrados, entonces el nt término de esta secuencia es 0)

Pseudoprimos débiles

Un número compuesto n que satisfacen bn↑ ↑ b()modn){displaystyle b^{n}equiv B{pmod {n}} se llama débil pseudoprime a base b. Un pseudoprime para basar un (bajo la definición habitual) satisface esta condición. Por el contrario, un pseudoprime débil que es coprime con la base es un pseudoprime en el sentido habitual, de lo contrario esto puede o no ser el caso. El pseudoprime menos débil a base b = 1, 2,... son:

4, 341, 6, 4, 4, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 6, 6, 4, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 6, 6, 4, 4, 4, 6, 4, 6, 6, 46, 4, 4, 4, 10... A000790 en el OEIS)

Todos los términos son menores o iguales al número de Carmichael más pequeño, 561. Excepto por 561, solo pueden aparecer semiprimos en la secuencia anterior, pero no todos los semiprimos menores que 561 ocurren, un semiprimo pq (p ≤ q) menos de 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 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 (por b = 1, 2,...)

4, 341, 6, 10, 10, 14, 9, 12, 15, 15, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 28, 27, 39, 36, 35, 49, 33, 44, 35, 45, 45, 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 usar nociones más refinadas de pseudoprimalidad, p. 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 números primos de grado industrial. Los primos de grado industrial son números enteros para los que la primalidad no ha sido "certificada" (es decir, rigurosamente probado), pero 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 números primos grandes rápidamente. El algoritmo habitual para generar números primos es generar números impares aleatorios y probar su primalidad. Sin embargo, las pruebas de primalidad determinista 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.