Un pseudoprimo es un primo probable (un número entero que comparte una propiedad común a todos los números primos ) que en realidad no es primo. Los pseudoprimos se clasifican según la propiedad de los primos que satisfacen.
Algunas fuentes utilizan el término pseudoprimo para describir todos los primos probables, tanto números compuestos como primos reales.
Los pseudoprimos son de importancia primordial en la criptografía de clave pública , que hace uso de la dificultad de factorizar números grandes en sus factores primos. Carl Pomerance estimó en 1988 que costaría 10 millones de dólares factorizar un número con 144 dígitos, y 100 mil millones de dólares factorizar un número de 200 dígitos (el coste hoy es drásticamente menor, pero sigue siendo prohibitivamente alto). [1] [2] Pero encontrar dos números primos grandes según se necesite para este uso también es caro, por lo que se utilizan varias pruebas de primalidad probabilísticas , algunas de las cuales en casos raros entregan de manera inapropiada números compuestos en lugar de primos. Por otro lado, las pruebas de primalidad deterministas, como la prueba de primalidad AKS , no dan falsos positivos ; debido a esto, no hay pseudoprimos con respecto a ellos.
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 a > 1 , si un entero compuesto x divide a x −1 − 1 , entonces x se denomina pseudoprimo de Fermat en base a . De ello se deduce que si x es un pseudoprimo de Fermat en base a , entonces x es coprimo con a . Algunas fuentes utilizan variaciones de esta definición, por ejemplo, para permitir que solo los números impares sean pseudoprimos. [3]
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 .