Primo probable

En teoría de números , un primo probable ( PPR ) 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 distintos tipos de primos probables tienen condiciones específicas diferentes. Si bien puede haber primos probables compuestos (llamados pseudoprimos ), la condición generalmente se elige para que tales excepciones sean poco frecuentes.

La prueba de Fermat para determinar la composición, basada en el pequeño teorema de Fermat , funciona de la siguiente manera: dado un entero n , se elige un entero a que no sea múltiplo de n (normalmente, se elige a en el rango 1 < a < n − 1 ). Se calcula 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; a n se le llama 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 (véase 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 mil millones, hay 11.408.012.595 números compuestos impares, pero solo 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 la base de algoritmos eficientes de prueba de primalidad , que encuentran aplicación en criptografía . Estos algoritmos suelen ser de naturaleza probabilística . La idea es que, si bien existen primos probables compuestos para la base 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 para la 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 a probados es, por lo tanto, como máximo P ^k , y como esto disminuye exponencialmente, solo se requiere un k moderado para que esta probabilidad sea insignificante (en comparación con, por ejemplo, la probabilidad de un 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 de primalidad determinista, un primer paso útil es comprobar la primalidad probable. Esto permite descartar rápidamente (con certeza) la mayoría de los compuestos.

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

Variaciones

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

La prueba de Fermat puede mejorarse alternativamente utilizando el hecho de que las únicas raíces cuadradas de 1 módulo un primo son 1 y −1 ^. Escribimos n = d · 2s + 1, donde d es impar. El número n es un primo probable fuerte ( SPRP ) en base a si:

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

o

a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ para algún }}0\leq r\leq s-1.\,

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

También existen los primos probables de Lucas , que se basan en secuencias de Lucas . Una prueba de primos probables de Lucas puede utilizarse de forma independiente. La prueba de primalidad de Baillie-PSW combina una prueba de Lucas con una prueba de primos probables fuertes.

Ejemplo de prueba para un número primo probable fuerte

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

Paso 1: Encontrar $d$ $d$ y $s$ $s$ para qué $96=d\cdot 2^{s}$ $96=d\cdot 2^{s}$ , dónde $d$ $d$ es extraño
- A partir de $s=0$ , $d$ sería $96$
- Creciente $s$ , vemos que $d=3$ y $s=5$ , desde $96=3\cdot 2^{5}$
Paso 2: Elegir $a$ , $1<a<97-1$ Elegiremos $a=2$ .
Paso 3: Calcular $a^{d}{\bmod {n}}$ , es decir $2^{3}{\bmod {9}}7$ . Dado que no es congruente con $1$ Continuamos probando la siguiente condición.
Paso 4: Calcular $2^{3\cdot 2^{r}}{\bmod {9}}7$ $2^{3\cdot 2^{r}}{\bmod {9}}7$ para $0\leq r<s$ $0\leq r<s$ . Si es congruente con $96$ $96$ , $97$ $97$ es probablemente el punto óptimo. De lo contrario, $97$ $97$ es un primo
- $r=0:2^{3}\equiv 8{\pmod {97}}$
- $r=1:2^{6}\equiv 64{\pmod {97}}$
- $r=2:2^{12}\equiv 22{\pmod {97}}$
- $r=3:2^{24}\equiv 96{\pmod {97}}$
Por lo tanto, $97$ es un primo probable fuerte en base 2 (y por lo tanto es un primo probable en base 2), y de hecho es primo.

Véase también

Enlaces externos

El glosario principal – Primo probable
Los 10000 números primos probables más grandes conocidos (PRP Top 10000) , última actualización: 2009.
Lista de probables números primos de Mersenne ( Gran Búsqueda en Internet de Números Primos de Mersenne ), algunos de los cuales posteriormente se confirmaron como primos. Incluye números mayores que los de la lista de los 10 000 primeros.

Referencias

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

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

[ 1 ]