Probable prima

En 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 la 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 , se elige algún número entero a que no sea múltiplo de n ; (normalmente, elegimos a en el rango 1 < a < n − 1 ). Calcular un ^{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; Entonces n se llama primo probable con base a . Un primo probable débil con base a es un número entero que es un primo probable con base a , pero que no es un primo probable fuerte con 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) de esa base. Por ejemplo, hasta 25 × 10 ⁹ , hay 11.408.012.595 números compuestos impares, pero sólo 21.853 pseudoprimos de 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 suelen ser de naturaleza probabilística . La idea es que si bien existen primos compuestos probables 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 base a es como máximo P . Si repetimos esta prueba k veces, eligiendo una nueva a cada vez, la probabilidad de que n sea pseudoprimo para todas las ^a s probadas es, por lo tanto, como máximo Pk , y como esto disminuye exponencialmente, solo se requiere una k moderada para que esta probabilidad sea insignificante. pequeño (en comparación, por ejemplo, con la probabilidad de que se produzca un error en el hardware del ordenador).

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 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.

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

Variaciones

Un primo probable de Euler con base a es un número entero que se indica como primo mediante el teorema algo más fuerte de que para cualquier primo p , a ^{( p −1)/2} es igual al módulo  p , donde está 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 primo son 1 y −1. Escribe n  =  d  · 2 ^s  + 1, donde d es impar. El número n es un primo probable fuerte (SPRP) para basar 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 con base a se denomina pseudoprimo fuerte con base a . Todo primo probable fuerte con base a es también un primo probable de Euler con la misma base, pero no al revés.

El pseudoprime 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 hay números primos probables de Lucas , que se basan en secuencias de Lucas . Una prueba principal probable de Lucas se puede utilizar sola. La prueba de primalidad de Baillie-PSW combina una prueba de Lucas con una fuerte prueba de prima probable.

Ejemplo de prueba para un primo probablemente fuerte

Para probar si 97 es una base prima probable fuerte 2:

• Paso 1: Encuentra y para cuál , dónde es impar ${\displaystyle d}$ ${\displaystyle s}$ ${\displaystyle 96=d\cdot 2^{s}}$ ${\displaystyle d}$
  • Empezando por , sería ${\displaystyle s=0}$ ${\displaystyle d}$ ${\displaystyle 96}$
  • Cada vez más , vemos que y , desde ${\displaystyle s}$ ${\displaystyle d=3}$ ${\displaystyle s=5}$ ${\displaystyle 96=3\cdot 2^{5}}$
• Paso 2 : Elige ,. Nosotros 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, es definitivamente 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 una base prima probable fuerte 2 (y, por lo tanto, es una base prima probable 2). ${\displaystyle 97}$

Ver también

• primo demostrable
• Prueba de primalidad de Baillie-PSW
• Pseudoprimo de Euler-Jacobi
• número de carmichael
• Lucas pseudoprime
• Prueba de primalidad de Miller-Rabin

enlaces externos

• El glosario principal – Probable prime
• El PRP Top 10000 (los primos probables más grandes conocidos)

Referencias

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