Probable primo

En teoría de números , un primo probable ( PRP ) es un número entero que satisface una condición específica que satisfacen todos los números primos , pero que no satisfacen 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 poco frecuentes.

La prueba de Fermat para la composición, que se basa en el pequeño teorema de Fermat , funciona de la siguiente manera: dado un entero n , elija un entero a que no sea múltiplo de n ; (normalmente, elegimos a en el rango 1 < a < n − 1 ). Calcule a ^{n − 1} módulo n . Si el resultado no es 1, entonces n es compuesto. Si el resultado es 1, entonces es probable que n sea primo; n se denomina entonces primo probable en base a . Un primo probable débil en base a es un 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 ⁹ , 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.

Propiedades

La primalidad probable es una base para algoritmos de prueba de primalidad eficientes , que encuentran aplicación en criptografía . Estos algoritmos son usualmente de naturaleza probabilística . La idea es que mientras que hay primos probables compuestos a base 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 base a es como máximo P. Si repetimos esta prueba k veces, eligiendo un nuevo a cada vez, la probabilidad de que n sea pseudoprimo a todos los a probados es por lo tanto como máximo P ^k , y como esto disminuye exponencialmente, solo se requiere un k moderado para hacer que esta probabilidad sea despreciablemente pequeña (comparada con, por ejemplo, la probabilidad de error de hardware de computadora).

Lamentablemente, 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 los primos probables fuertes ( P  = 1/4, algoritmo de Miller-Rabin ) o los primos probables de Euler ( P  = 1/2, algoritmo de Solovay-Strassen ).

Incluso cuando se requiere una prueba determinista de primalidad, un primer paso útil es probar la primalidad probable. Esto puede eliminar rápidamente (con certeza) la mayoría de los compuestos.

A veces, una prueba PRP se combina con una tabla de pequeños pseudoprimos para establecer rápidamente la primalidad de un número dado menor que un umbral determinado.

Variaciones

Un primo probable de Euler en base a es un entero que se indica primo por el teorema algo más fuerte de que para cualquier primo p , a ^{( p −1)/2} es igual a módulo  p , donde es el símbolo de Jacobi . Un primo probable de Euler que es compuesto se llama pseudoprimo de Euler-Jacobi en base  a . El pseudoprimo de Euler-Jacobi más pequeño en base 2 es 561. ^{[1] : 1004} Hay 11347 pseudoprimos de Euler-Jacobi en base 2 que son menores que 25·10 ⁹ . ^{[1] : 1005} ${\displaystyle ({\tfrac {a}{p}})}$ ${\displaystyle ({\tfrac {a}{p}})}$

Esta prueba se puede mejorar utilizando el hecho de que las únicas raíces cuadradas de 1 módulo un primo son 1 y −1. Escriba n  =  d  · 2 ^s  + 1, donde d es impar. El número n es un primo probable fuerte ( SPRP ) para la base a si:

${\displaystyle a^{d}\equiv 1{\pmod {n}},\;}$

o

${\displaystyle a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ for some }}0\leq r\leq s-1.\,}$

Un primo probable fuerte compuesto en base a se denomina pseudoprimo fuerte en base a . Todo primo probable fuerte en base a es también un primo probable de Euler en base a, pero no al revés.

El pseudoprimo fuerte base 2 más pequeño es 2047. ^{[1] : 1004} Hay 4842 pseudoprimos fuertes base 2 que son menores que 25·10 ⁹ . ^{[1] : 1005}

También existen los primos probables de Lucas , que se basan en las secuencias de Lucas . Se puede utilizar una prueba de primos probables de Lucas sola. La prueba de primalidad de Baillie-PSW combina una prueba de Lucas con una prueba de primos probables fuerte.

Ejemplo de prueba para una probabilidad prima fuerte

Para comprobar si 97 es un número primo probable fuerte de base 2:

• Paso 1: Encuentra y para el cual , donde es impar ${\displaystyle d}$ ${\displaystyle s}$ ${\displaystyle 96=d\cdot 2^{s}}$ ${\displaystyle d}$
  • Comenzando con , sería ${\displaystyle s=0}$ ${\displaystyle d}$ ${\displaystyle 96}$
  • Al aumentar , vemos que y , dado que ${\displaystyle s}$ ${\displaystyle d=3}$ ${\displaystyle s=5}$ ${\displaystyle 96=3\cdot 2^{5}}$
• Paso 2: Elige , . Elegiremos . ${\displaystyle a}$ ${\displaystyle 1<a<97-1}$ ${\displaystyle a=2}$
• Paso 3: Calcular , es decir . Como no es congruente con , continuamos probando la siguiente condición ${\displaystyle a^{d}{\bmod {n}}}$ ${\displaystyle 2^{3}{\bmod {9}}7}$ ${\displaystyle 1}$
• Paso 4: Calcular para . Si es congruente con , probablemente sea primo. De lo contrario, definitivamente es compuesto. ${\displaystyle 2^{3\cdot 2^{r}}{\bmod {9}}7}$ ${\displaystyle 0\leq r<s}$ ${\displaystyle 96}$ ${\displaystyle 97}$ ${\displaystyle 97}$
  • ${\displaystyle r=0:2^{3}\equiv 8{\pmod {97}}}$
  • ${\displaystyle r=1:2^{6}\equiv 64{\pmod {97}}}$
  • ${\displaystyle r=2:2^{12}\equiv 22{\pmod {97}}}$
  • ${\displaystyle r=3:2^{24}\equiv 96{\pmod {97}}}$
• Por lo tanto, es un primo probable fuerte en base 2 (y es por lo tanto un primo probable en base 2). ${\displaystyle 97}$

Véase también

• Prima demostrable
• Prueba de primalidad de Baillie-PSW
• Pseudoprimo de Euler-Jacobi
• Lucas pseudoprime
• Prueba de primalidad de Miller-Rabin
• Prueba de primalidad de Perrin
• Número de Carmichael

Enlaces externos

• Glosario de números primos – Números primos probables
• Los 10000 mejores números primos probables conocidos (PRP)

Referencias

1. Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (julio de 1980). "Los pseudoprimos hasta 25·109" (PDF) . Matemáticas de la computación . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR  2006210.