Número pseudoprimo de Fermat

Un pseudoprimo de Fermat a menudo se denomina simplemente pseudoprimo, sobreentendiéndose el modificador de Fermat.Un 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.[2]​[1]​: Def.3.34 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: 2340 ≡ 1 (mod 341) y por lo tanto satisface el test de primalidad de Fermat para la base 2.Hay infinitos pseudoprimos para cualquier base dada a > 1.En 1904, Cipolla demostró cómo producir un número infinito de pseudoprimos base a > 1: Sea p cualquier primo impar que no divide a (a2 - 1).De hecho, hay infinitos número pseudoprimo fuerte en cualquier base mayor que 1 (véase el teorema 1 del libro The pseudoprimes to 25·109[4]​) e infinitamente muchos números de Carmichael,[5]​ pero son comparativamente raros.(sucesión A001567 en OEIS) Un número de Poulet cuyos divisores d dividen a (2d − 2) se llama supernúmero de Poulet.[6]​ El pseudoprimo (p-p) más pequeño para cada base a ≤ 200 se da en la siguiente tabla; los colores marcan el número de factores primos.La tabla siguiente está basada en la (sucesión A007535 en OEIS) Para obtener más información (base 31 a 100), consúltese (sucesión A020159 en OEIS) a (sucesión A020228 en OEIS), y para todas las bases hasta 150, consúltese la tabla de pseudoprimos de Fermat (texto en alemán), que no define n como pseudoprimo respecto con una base congruente con 1 o -1 (mod n).es un pseudoprimo de Fermat con al menos dos bases no triviales módulo[8]​ Esta página no define que n sea un pseudoprimo respecto a una base congruente con 1 o -1 (mod n).Cuando p es un primo, p2 es un pseudoprimo de Fermat respecto a la base b si y solo si p es un número primo de Wieferich respecto a la base b.(n), o (sucesión A000010 en OEIS) (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 un número primo o un número de Carmichael (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... (sucesión A002997 en OEIS)), el cociente = 2 si y solo si n está en la secuencia: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... (sucesión A191311 en OEIS)) Los menores números con n valores de b son (o 0 si no existe tal número): Un número compuesto n que satisface quese llama pseudoprimo débil en base b.Un pseudoprimo bajo la definición usual 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.[9]​ Los menores pseudoprimos débiles en base b = 1, 2, ... son: Todos los términos son menores o iguales al número de Carmichael más pequeño, 561.Un semiprimo pq (p ≤ q) menor que 561 aparece en las secuencias anteriores si y solo si (p − 1) divide a (q − 1) (véase (sucesión A108574 en OEIS)) Además, el pseudoprimo más pequeño respecto a la base n (también no es necesario exceder n) ((sucesión A090086 en OEIS)) también suele ser semiprimo, el primer contraejemplo es (sucesión A090086 en OEIS)(648) = 385 = 5 × 7 × 11.Si se requiere que n > b, son (para b = 1, 2, ...) 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 (véase (sucesión A006935 en OEIS)).La rareza de estos pseudoprimos tiene importantes implicaciones prácticas.Por ejemplo, los algoritmos de criptografía asimétrica como el 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 someter a prueba su primalidad.Sin embargo, las pruebas de primalidad determinísticas 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 el test de primalidad de Fermat, mucho más rápido y sencillo.