Un pseudoprime es un primo probable (un número entero que comparte una propiedad común a todos los números primos ) que no es realmente primo. Los pseudoprimos se clasifican según la propiedad de los primos que satisfacen.
Algunas fuentes usan el término pseudoprime para describir todos los números primos probables, tanto números compuestos como números primos reales.
Los pseudoprimes son de importancia primordial en la criptografía de clave pública , que hace uso de la dificultad de factorizar grandes números en sus factores primos. Carl Pomerance estimó en 1988 que costaría $ 10 millones factorizar un número con 144 dígitos y $ 100 mil millones factorizar un número de 200 dígitos (el costo hoy es dramáticamente más bajo pero aún prohibitivamente alto). [1] [2] Pero encontrar dos números primos grandes según sea necesario para este uso también es costoso, por lo que se utilizan varias pruebas probabilísticas de primalidad , algunas de las cuales, en casos raros, entregan números compuestos en lugar de primos de manera inapropiada. Por otro lado, las pruebas de primalidad deterministas, como la prueba de primalidad AKS , no danfalsos positivos ; no hay pseudoprimes con respecto a ellos.
El pequeño teorema de Fermat establece que si p es primo y una es primos entre sí a p , entonces un 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 pseudoprime de Fermat a la base a . De ello se deduce que si x es un pseudoprimo de Fermat a la base a , entonces x es coprimo a a. Algunas fuentes usan variaciones de esta definición, por ejemplo, para permitir que solo los números impares sean pseudoprimes. [3]
Un entero x que es un pseudoprimo de Fermat para todos los valores de a que son coprimos ax se llama número de Carmichael .
Mathematics portal