Primo probable

En teoría de números, un primo probable (PRP) es un número entero que satisface una condición específica que todos los números primos cumplen, 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, elige algún número entero a que no es múltiplo de n; (normalmente, elegimos a en el rango 1 < a < n − 1). Calcula a^{n − 1} módulo n. 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 a base a. Un primo probable débil a base a es un número entero que es un primo probable a base a, pero que no es un primo probable fuerte a 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 en base 2. El número de primos impares en el mismo intervalo es 1,091,987,404.

Propiedades

La primalidad probable es la base de 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 compuesto n dado, si elegimos a al azar, entonces la probabilidad de que n sea pseudoprimo en 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 para todos los as probado 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 con, por ejemplo, la probabilidad de error de hardware de la computadora).

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 Números 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.

Una prueba de PRP a veces se combina con una tabla de pequeños pseudoprimos para establecer rápidamente la primalidad de un número determinado más pequeño que cierto umbral.

Variaciones

An Euler probablemente primo a la base a es un entero que se indica primo por el teorema algo más fuerte que para cualquier primo p, a^()p−1)/2 iguales ()ap){displaystyle ({tfrac {}{p}}} modulop, donde ()ap){displaystyle ({tfrac {}{p}}} es el símbolo Jacobi. Un primo probable Euler que es composite se llama Euler-Jacobi pseudoprime a la basea. El más pequeño Euler-Jacobi pseudoprime a base 2 es 561. Hay 11347 Euler-Jacobi pseudoprimes base 2 que son menos de 25·10⁹.

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) a base a si:

ad↑ ↑ 1()modn),{displaystyle a^{d}equiv 1{pmod {n},;}

o

ad⋅ ⋅ 2r↑ ↑ − − 1()modn)para algunos0≤ ≤ r≤ ≤ s− − 1.{displaystyle a^{dcdot 2}equiv} - ¿Por qué?

Un primo probable fuerte compuesto con base a se llama 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.

La base 2 pseudoprima fuerte más pequeña es 2047. Hay 4842 base 2 pseudoprima fuerte que tienen menos de 25·10⁹.

También hay números primos probables de Lucas, que se basan en secuencias de Lucas. Una prueba de primos probables de Lucas se puede usar sola. La prueba de primalidad Baillie-PSW combina una prueba de Lucas con una prueba principal probable fuerte.

Ejemplo de SPRP

Para probar si 97 es una base 2 probable fuerte:

• Paso 1: Encontrar d{displaystyle d} y s{displaystyle s} para la cual 96=d⋅ ⋅ 2s{displaystyle 96=dcdot 2^{s}, donde d{displaystyle d} Es extraño.
  • Comienzo con s=0{displaystyle s=0}, d{displaystyle d} lo haría 96{displaystyle 96}
  • Aumento s{displaystyle s}, vemos que d=3{displaystyle d=3} y s=5{displaystyle s=5}, desde 96=3⋅ ⋅ 25{displaystyle 96=3cdot 2^{5}
• Paso 2: Elija a{displaystyle a}, <math alttext="{displaystyle 1<a1.a.97− − 1{displaystyle 1 se hizo realidad97-1}<img alt="{displaystyle 1<a. Vamos a elegir a=2{displaystyle a=2}.
• Paso 3: Calcular admodn{displaystyle a^{d} {bmod {n}}, es decir. 23mod97{displaystyle 2^{3}{bmod {9}7}. Ya que no es congruente con 1{displaystyle 1}, seguimos probando la siguiente condición
• Paso 4: Calcular 23⋅ ⋅ 2rmod97{displaystyle 2^{3cdot 2}{bmod {9}7} para <math alttext="{displaystyle 0leq r0≤ ≤ r.s{displaystyle 0leq r identificados}<img alt="0leq r. Si es congruente con 96{displaystyle 96}, 97{displaystyle 97} Probablemente sea la primera. De lo contrario, 97{displaystyle 97} definitivamente composite
  • r=0:23↑ ↑ 8()mod97){displaystyle ¿Qué?
  • r=1:26↑ ↑ 64()mod97){displaystyle r=1:2^{6}equiv 64{pmod {97}}
  • r=2:212↑ ↑ 22()mod97){displaystyle r=2:2^{12}equiv 22{pmod {97}}
  • r=3:224↑ ↑ 96()mod97){displaystyle r=3:2^{24}equiv 96{pmod {97}
• Por lo tanto, 97{displaystyle 97} es una base principal fuerte probable 2 (y por lo tanto es una base inicial probable 2).