En la teoría de números , un primo probable (PRP) es un número entero que satisface una condición específica que cumplen todos los números primos , pero que no cumplen la mayoría de los números compuestos . Los diferentes tipos de primos probables tienen diferentes condiciones específicas. Si bien puede haber primos probables que sean compuestos (llamados pseudoprimos ), la condición generalmente se elige para que tales excepciones sean raras.
La prueba de composición de Fermat, que se basa en el pequeño teorema de Fermat , funciona de la siguiente manera: dado un número entero n , elija algún número entero a que no sea un múltiplo de n ; (típicamente, elegimos a en el rango 1 < a < n − 1 ). Calcular un norte - 1 módulo norte . Si el resultado no es 1, entonces n es compuesto. Si el resultado es 1, es probable que n sea primo; n se llama entonces un primo probable para basar a . Un primo probable débil para basar unes un número entero que es un primo probable en base a , pero que no es un primo probable fuerte en base a (ver más abajo).
Para una base fija a , es inusual que un número compuesto sea un primo probable (es decir, un pseudoprimo) para esa base. Por ejemplo, hasta 25 × 10 9 , hay 11 408 012 595 números compuestos impares, pero solo 21 853 pseudoprimos base 2. [1] : 1005 El número de primos impares en el mismo intervalo es 1 091 987 404.
La primalidad probable es una base para los algoritmos de prueba de primalidad eficientes , que encuentran aplicación en la criptografía . Estos algoritmos suelen ser de naturaleza probabilística . La idea es que si bien hay primos probables compuestos para basar a para cualquier a fijo , podemos esperar que exista algún P <1 fijo tal que para cualquier n compuesto dado , si elegimos a al azar, entonces la probabilidad de que n sea pseudoprimo a la base a es como máximo P . Si repetimos esta prueba k veces, eligiendo una nueva acada vez, la probabilidad de que n sea pseudoprimo para todos los a s probados es, por lo tanto, como máximo P k , y como esto disminuye exponencialmente, solo se requiere k moderado para que esta probabilidad sea insignificantemente pequeña (en comparación, por ejemplo, con la probabilidad de que la computadora error de hardware).
Desafortunadamente, esto es falso para los primos probables débiles, porque existen números de Carmichael ; pero es cierto para nociones más refinadas de primalidad probable, como primos probables fuertes ( P = 1/4, algoritmo de Miller-Rabin ), o primos probables de Euler ( P = 1/2, algoritmo de Solovay-Strassen ).
Incluso cuando se requiere una prueba de primalidad determinista, un primer paso útil es probar la primalidad probable. Esto puede eliminar rápidamente (con certeza) la mayoría de los composites.