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 usan el término pseudoprimo para describir todos los primos probables, tanto números compuestos como primos reales.
Los pseudoprimos son de primordial importancia en la criptografía de clave pública , que aprovecha la dificultad de factorizar grandes números en sus factores primos. Carl Pomerance estimó en 1988 que costaría 10 millones de dólares factorizar un número de 144 dígitos y 100 000 millones de dólares factorizar un número de 200 dígitos (el coste actual es mucho más bajo, pero sigue siendo prohibitivamente alto). [1] [2] Pero encontrar dos números primos grandes necesarios para este uso también es costoso, por lo que se utilizan varias pruebas de primalidad probabilística , algunas de las cuales, en casos excepcionales, entregan de manera inapropiada números compuestos en lugar de números primos. Por otro lado, las pruebas de primalidad deterministas, como la prueba de primalidad AKS , no danfalsos positivos ; no hay pseudoprimos con respecto a ellos.
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 x −1 − 1, entonces x se llama pseudoprimo de Fermat para basar a . De ello se deduce que si x es un pseudoprimo de Fermat en base a , entonces x es coprimo en a. Algunas fuentes usan 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 .