Algoritmos de búsqueda de números primos

"El número primo más grande es 2 ^32582657 -1 . Y afirmo con orgullo que recordé todos sus números ... en forma binaria ".
Karl Pomerance

Un número natural se llama primo si solo tiene dos divisores diferentes: uno y él mismo. La tarea de encontrar números primos ha estado obsesionando a los matemáticos durante mucho tiempo. Durante mucho tiempo, este problema no tuvo una aplicación práctica directa, pero todo cambió con el advenimiento de la criptografía de clave pública. Este artículo analiza varias formas de buscar números primos, tanto de interés puramente académico como utilizados hoy en criptografía.

Tamiz de Eratóstenes

Tamiz de Eratóstenes : un algoritmo propuesto por el antiguo matemático griego Eratóstenes. Este método le permite encontrar todos los primos menores que un número dado n . La esencia del método es la siguiente. Toma un conjunto de números del 2 al n . Tache todos los números divisibles por 2, excepto 2. Del conjunto (eliminamos), pasamos al siguiente número "no eliminado" - 3, tache nuevamente todo lo que es divisible por 3. Pasamos al siguiente número restante - 5, y así sucesivamente hasta que llegamos a n . Después de realizar los pasos anteriores, solo los números primos permanecerán en la lista original.

El algoritmo puede ser ligeramente optimizado. Dado que uno de los divisores del número compuesto n es obligatorio $$$\ leqslant \ sqrt {n}$ , el algoritmo se puede detener después de eliminar los números divisibles por $$$\ sqrt {n}$ .

Ilustración del funcionamiento del algoritmo de Wikipedia:


La complejidad del algoritmo es $$$O (n \ log \ log n)$ al mismo tiempo, para almacenar información sobre qué números se tacharon, se requiere $$$O (n)$ memoria

Hay varias optimizaciones para reducir estos indicadores. Un truco llamado factorización de rueda es incluir en la lista inicial solo números que son primos con los primeros números primos (por ejemplo, menos de 30). En teoría, se propone tomar los primeros simples hasta aproximadamente $$$\ sqrt {\ log n}$ . Esto reduce la complejidad del algoritmo en $$$\ log \ log n$ tiempos Además, la llamada segmentación se usa para reducir el consumo de memoria. El conjunto inicial de números se divide en segmentos de tamaño. $$$\ leqslant \ sqrt {n}$ y para cada segmento, el tamiz de Eratóstenes se aplica por separado. El consumo de memoria se reduce a $$$O (\ sqrt {n})$ .

Tamiz Atkin

Atkin y Bershtein propusieron un mejor algoritmo para separar los números compuestos, y se llamó Atkin Sieve . Este método se basa en las siguientes tres propiedades de los primos.

Propiedad 1

Si n es un número positivo que no es un múltiplo del cuadrado de un número primo y tal que $$$n \ equiv 1 (\ mod 4)$ . Entonces n es primo si y solo si el número de raíces de la ecuación $$$4x ^ 2 + y ^ 2 = n$ extraño

Propiedad 2

Si n es un número positivo que no es un múltiplo del cuadrado de un número primo y tal que $$$n \ equiv 1 (\ mod 6)$ . Entonces n es primo si y solo si el número de raíces de la ecuación $$$3x ^ 2 + y ^ 2 = n$ extraño

Propiedad 3

Si n es un número positivo que no es un múltiplo del cuadrado de un número primo y tal que $$$n \ equiv 11 (\ mod 12)$ . Entonces n es primo si y solo si el número de raíces de la ecuación $$$3x ^ 2-y ^ 2 = n$ extraño

La evidencia de estas propiedades se proporciona en este artículo .

En la etapa inicial del algoritmo, el tamiz Atkin es una matriz A de tamaño n llena de ceros. Para determinar los números primos, todos $$$x, y <\ sqrt n$ . Para cada par se calcula $$$4x ^ 2 + y ^ 2$ , $$$3x ^ 2 + y ^ 2$ , $$$3x ^ 2 años ^ 2$ y el valor de los elementos de la matriz $$$A [4x ^ 2 + y ^ 2]$ , $$$A [3x ^ 2 + y ^ 2]$ , $$$A [3x ^ 2-y ^ 2]$ aumenta en uno. Al final del algoritmo, los índices de todos los elementos de la matriz que tienen valores impares son números primos o cuadrados de un número primo. En el último paso del algoritmo, los cuadrados de los números restantes en el conjunto se tachan.

De la descripción del algoritmo se deduce que la complejidad computacional del tamiz Atkin y el consumo de memoria son $$$O (n)$ . Cuando se utiliza la factorización y segmentación de la rueda, la estimación de la complejidad del algoritmo se reduce a $$$O (n / \ log \ log n)$ y consumo de memoria hasta $$$O (\ sqrt {n})$ .

Números de Mersenne y prueba de Luke-Lemer

Por supuesto, con tales indicadores de complejidad, incluso el tamiz optimizado de Atkin no puede usarse para buscar primos verdaderamente grandes. Afortunadamente, hay pruebas rápidas para verificar si un número dado es primo. A diferencia de los algoritmos de tamizado, tales pruebas no están diseñadas para buscar todos los números primos, solo pueden decir con cierta probabilidad si cierto número es primo.

Uno de esos métodos de prueba es la prueba de Luc-Lemer . Esta es una prueba determinista e incondicional de simplicidad. Esto significa que pasar la prueba garantiza la simplicidad del número. Desafortunadamente, la prueba está diseñada solo para números de un tipo especial $$$2 ^ p-1$ donde p es un número natural. Dichos números se llaman números de Mersenne.

La prueba de Luke-Lemer afirma que el número de Mersenne $$$M_p = 2 ^ p-1$ cebar si y solo si p es cebar y $$$M_p$ divide $$$(p-1)$ miembro de la secuencia $$$S_k$ conjunto recursivamente: $$$S_1 = 4, S_k = S_ {k-1} ^ 2-2$ para $$$k> 1$ .

Para el numero $$$M_p$ longitud de bits p la complejidad computacional del algoritmo es $$${\ displaystyle O (p ^ {3})}$ .

Debido a la simplicidad y el determinismo de la prueba, los números primos más grandes conocidos son los números de Mersenne. El número primo conocido más grande de hoy es $$$2 ^ {82,589,933} -1$ , su notación decimal consta de 24,862,048 dígitos. Puedes admirar esta belleza aquí .

Teorema de Fermat y prueba de Miller-Rabin

No se conocen muchos números primos de Mersenne, por lo que la criptografía de clave pública requiere una forma diferente de buscar números primos. Uno de estos métodos es la prueba de simplicidad de Fermat . Se basa en el pequeño teorema de Fermat, que establece que si n es primo, para cualquier a que no sea divisible por n , la igualdad $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ . La prueba del teorema se puede encontrar en Wikipedia .

La prueba de simplicidad de Fermat es una prueba probabilística, que consiste en enumerar varios valores de un si al menos uno de ellos satisface la desigualdad $$$a ^ {n-1} \ not \ equiv 1 \ pmod n$ , entonces el número n es compuesto. De lo contrario, n es probablemente primo. Cuantos más valores de a se usen en la prueba, mayor será la probabilidad de que n sea ​​primo.

Desafortunadamente, hay números compuestos n para los cuales la comparación $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ se cumple para todos un primo mutuo con n . Dichos números se llaman números de Carmichael . Los números compuestos que pasan con éxito la prueba de Fermat se llaman Fermat pseudo-simple. El número de Fermat pseudo-simple es infinito, por lo que la prueba de Fermat no es la forma más confiable de determinar números primos.

Prueba de Miller-Rabin

Se pueden lograr resultados más confiables combinando el pequeño teorema de Fermat y el hecho de que para un primer p no hay otras raíces de la ecuación $$$x ^ 2 \ equiv 1 \ pmod p$ excepto 1 y -1. La prueba de Miller-Rabin enumera varios valores de a y verifica que las siguientes condiciones sean verdaderas.

Deje que p sea ​​primo y $$$p-1 = 2 ^ sd$ , entonces para cualquiera de al menos una de las condiciones es verdadera:

1. $$$a ^ {d} \ equiv \ pm1 {\ pmod {p}}$
2. Hay un entero r <s tal que $$$a ^ {2 ^ {r} d} \ equiv -1 {\ pmod {p}}$

Por el teorema de Fermat $$$a ^ {p-1} \ equiv1 \ pmod p$ y desde $$$p-1 = 2 ^ sd$ de la propiedad de las raíces de la ecuación $$$x ^ 2 \ equiv 1 \ pmod p$ se deduce que si encontramos tal que una de las condiciones no se cumple, entonces p es un número compuesto. Si se cumple una de las condiciones, el número a se llama testigo de la simplicidad del número n según Miller, y el número n en sí es probablemente primo.

Cuantos más testigos de simplicidad se encuentren, mayor será la probabilidad de que n sea ​​primo. Según el teorema de Rabin, la probabilidad de que un número elegido al azar a sea ​​testigo de la simplicidad del número compuesto es aproximadamente $$$1/4$ .

Por lo tanto, si verificamos k números aleatorios a , entonces la probabilidad de tomar el número compuesto como primo $$$\ aprox (1/4) ^ k$ .

La complejidad del algoritmo. $$$O (k \ log ^ 3p)$ donde k es el número de cheques.

Debido a su velocidad y alta precisión, la prueba de Miller-Rabin se usa ampliamente en la búsqueda de números primos. Muchas bibliotecas criptográficas modernas usan solo esta prueba cuando se verifica la simplicidad de grandes números y, como Martin Albrecht demostró en su trabajo , esto no siempre es suficiente.

Pudo generar tales números compuestos que pasaron con éxito la prueba de simplicidad en las bibliotecas OpenSSL, CryptLib, JavaScript Big Number y muchos otros.

Luke Test y Baillie - Prueba PSW

Para evitar vulnerabilidades relacionadas con situaciones en las que un número compuesto generado por un atacante se presenta como primo, Martin Albrecht sugiere utilizar la prueba Baillie - PSW . A pesar de que la prueba Baillie - PSW es ​​probabilística, hasta la fecha, no se han encontrado números compuestos que pasen con éxito esta prueba. Para encontrar ese número en 1980, los autores del algoritmo prometieron una recompensa de $ 30. El premio aún no ha sido reclamado.

Varios investigadores verificaron todos los números hasta $$$2 ^ {64}$ y ni un solo número compuesto pasó la prueba Baillie - PSW. Por lo tanto, para números menos $$$2 ^ {64}$ La prueba se considera determinista.

La esencia de la prueba es verificar constantemente el número en un tiempo de inactividad mediante dos métodos diferentes. Uno de estos métodos es la prueba de Miller-Rabin ya descrita anteriormente. La segunda es la prueba de Luke para una fuerte pseudo-simplicidad .

Prueba de pseudo-simplicidad de Luke Strong

Las secuencias de Luke son pares de secuencias de recurrencia $$$\ {U_ {n} (P, Q) \}, \ {V_ {n} (P, Q) \}$ descrito por las expresiones:

$$

$${\ displaystyle U_ {0} (P, Q) = 0, \ quad U_ {1} (P, Q) = 1, \ quad U_ {n + 2} (P, Q) = P \ cdot U_ {n +1} (P, Q) -Q \ cdot U_ {n} (P, Q), \, n \ geq 0}$$

$$

$${\ displaystyle V_ {0} (P, Q) = 2, \ quad V_ {1} (P, Q) = P, \ quad V_ {n + 2} (P, Q) = P \ cdot V_ {n +1} (P, Q) -Q \ cdot V_ {n} (P, Q), \, n \ geq 0}$$

Dejar $$$U_n (P, Q)$ y $$$V_n (P, Q)$ Son secuencias de Lucas, donde los enteros P y Q satisfacen la condición $$${\ displaystyle D = P ^ {2} -4Q \ neq 0}$

Calculamos el símbolo de Jacobi : $$$\ left ({\ frac {D} {p}} \ right) = \ varepsilon$ .

Encuentre tales r, s para las cuales la igualdad $$$n-ε = 2 ^ rs$

Para prime n , se cumple una de las siguientes condiciones:

1. n divide $$$U_s$
2. n divide $$$V_ {2 ^ js}$ para algunos j <r

De lo contrario, n es compuesto.

La probabilidad de que un número compuesto n pase con éxito la prueba de Luc para un par dado de parámetros P, Q no supera 4/15. Por lo tanto, después de aplicar la prueba k veces, esta probabilidad es $$$(4/15) ^ k$ .

Las pruebas de Miller-Rabin y Luke producen conjuntos disjuntos de números pseudo-simples, respectivamente, si el número p pasó ambas pruebas, es simple. Es en esta propiedad en la que se basa la prueba Baillie - PSW.

Conclusión

Dependiendo de la tarea, se pueden usar varios métodos para encontrar números primos. Por ejemplo, cuando se buscan grandes números primos de Mersenne, primero, usando el tamiz de Eratóstenes o Atkin, se determina una lista de números primos hasta cierto límite, supongamos que hasta $$$10 ^ 8$ . Luego, para cada número p de la lista, usando la prueba de Luc-Lemer, se verifica su simplicidad $$$M_p = 2 ^ p-1$ .

Para generar un número primo grande con fines criptográficos, se selecciona un número aleatorio a y se verifica mediante la prueba de Miller-Rabin o el Baillie - PSW más confiable. De acuerdo con el teorema de distribución de números primos , para un número seleccionado al azar de 1 a n, la probabilidad de ser primo es aproximadamente igual $$${\ frac {1} {\ ln n}}$ . Por lo tanto, para encontrar un número primo de 1024 bits, es suficiente clasificar alrededor de mil opciones.

Fuentes de PS

La implementación de todos los algoritmos descritos en Go se puede ver en GitHub .