Primo probable

No confundir con Provable prime .

En la teoría de números , un número primo probable (PRP) es un número entero que satisface una condición específica que todos los números primos satisfacen , pero que la mayoría de los números compuestos no satisfacen . Los diferentes tipos de números primos probables tienen diferentes condiciones específicas. Si bien puede haber números primos probables que sean compuestos (llamados pseudoprimos ), la condición generalmente se elige para que tales excepciones sean raras.

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 número entero n , elija un número entero a que no sea múltiplo de n ; (normalmente, elegimos a en el rango 1 < a < n - 1 ). Calcule un módulo n ^{n - 1} . 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 denomina primo probable de la base a . Un primo probable débil para basar unes un número entero que es un número primo probable de la base a , pero que no es un número primo probable fuerte de la base a (ver más abajo).

Para una base fija a , es inusual que un número compuesto sea un número primo probable (es decir, un pseudoprimo) de esa base. Por ejemplo, hasta 25 × 10 ⁹ , hay 11,408,012,595 números compuestos impares, pero solo 21,853 pseudoprimes base 2. ^{[1] : p. 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 la criptografía . Estos algoritmos suelen ser de naturaleza probabilística . La idea es que, mientras que hay probable primo compuestos para basar una para cualquier fijado una , podemos esperar existe algún fijo P <1 tal que para cualquier compuesto dado n , si elegimos una al azar, entonces la probabilidad de que n es pseudoprime a base de una es como máximo P . Si repetimos esta prueba k veces, eligiendo un nuevo acada vez, la probabilidad de que n sea ​​pseudoprime a todos los a s 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 insignificantemente pequeña (en comparación con, por ejemplo, la probabilidad de que la computadora error de hardware).

Desafortunadamente, esto es falso para los números primos probables débiles, porque existen números de Carmichael ; pero es cierto para nociones más refinadas de primalidad probable, como números primos probables fuertes ( P  = 1/4, algoritmo de Miller-Rabin ) o números primos probables de Euler ( P  = 1/2, algoritmo Solovay-Strassen ).

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

A veces, una prueba de PRP se combina con una tabla de pequeños pseudoprimes para establecer rápidamente la primacía de un número dado menor que algún umbral.

Variaciones

Un primo probable de Euler para la base a es un número entero que se indica como primo por 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 denomina pseudoprimo de Euler-Jacobi con base  a . La pseudoprima de Euler-Jacobi más pequeña en base 2 es 561. ^{[1] : 1004} Hay 11347 pseudoprimas 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 usando el hecho de que las únicas raíces cuadradas de 1 módulo a 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 para la base a es también un primo probable de Euler para la misma base, pero no al revés.

La base 2 pseudoprima fuerte más pequeña es 2047. ^{[1] : 1004} Hay 4842 pseudoprime base 2 fuerte 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 de cebado probable de Lucas se puede utilizar sola. La prueba de primalidad Baillie-PSW combina una prueba de Lucas con una prueba de primo probable fuerte.

Ejemplo de SPRP

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

• Paso 1: Encuentra y para cuál , dónde 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}$
  • Aumentando , lo vemos y , desde${\displaystyle s}$${\displaystyle d=3}$${\displaystyle s=5}$${\displaystyle 96=3\cdot 2^{5}}$
• Paso 2: Elija , . Nosotros elegiremos .${\displaystyle a}$${\displaystyle 1<a<97-1}$${\displaystyle a=2}$
• Paso 3: Calcular , es decir . Dado que 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 principal 2 probable fuerte (y, por lo tanto, es una base principal probable 2).${\displaystyle 97}$

Ver también

• Prueba de primalidad Baillie-PSW
• Euler-Jacobi pseudoprime
• Número de Carmichael
• Lucas pseudoprime
• Prueba de primaria de Miller-Rabin
• Prime demostrable

Enlaces externos

• El glosario principal - Probable prime
• El PRP Top 10000 (los números primos probables más grandes conocidos)

Referencias

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