¡Saludo a los ciudadanos de Habrovsk! Hoy continuamos compartiendo material útil, una traducción de la cual fue preparada especÃficamente para estudiantes del curso "Algoritmos para desarrolladores" .
Dado un número
n , ¿cómo entender que este número es primo? Supongamos que
n inicialmente extraño, porque de lo contrario la tarea es bastante simple.
La idea más obvia serÃa buscar todos los divisores de
n , sin embargo, hasta ahora el problema principal es encontrar un algoritmo eficiente.
Prueba de granja
Según el
teorema de Fermat , si
n es primo, entonces, para cualquier a, se cumple la siguiente igualdad:
a n−1 =1 (mod n) . A partir de aquÃ, podemos derivar la regla de prueba de Fermat para verificar la simplicidad de un número: tome al azar a
a ∈ {1, ..., n−1} y verifique si la igualdad
a n−1 =1 (mod n) es válida. Si no se respeta la igualdad, lo más probable es que
n sea ​​compuesto.
Sin embargo, la condición de igualdad puede cumplirse incluso si
n no es simple. Por ejemplo, tome
n = 561 = 3 × 11 × 17 . Según el
teorema del resto chino:
Z 561 = Z 3 × Z 11 × Z 17, donde cada a ∈ Z
∗ 561 corresponde a lo siguiente:
(x,y,z) ∈ Z ∗ 3 ×Z ∗ 11 11×Z ∗ 17 .Según el teorema de Fermat,
x 2 =1 ,
y 10 =1 z 16 =1 . Dado que 2, 10 y 16 son 560 divisores, esto significa que
(x,y,z) 560 = (1, 1, 1) , en otras palabras,
a 560 = 1 para cualquier
a ∈ Z ∗ 561 .
No importa cuál elija, 561 siempre pasará la prueba de Fermat, a pesar de que es compuesta, siempre que a sea mutuamente simple con
n . Dichos números se llaman números de Carmichael y resulta que hay un número infinito de ellos.
Si
a no
a coprimo con
n , entonces no pasa la prueba de Fermat, pero en este caso podemos rechazar las pruebas y continuar buscando los divisores de
n , calculando el MCD (
a, n ).
Prueba de Miller-Rabin
Podemos mejorar la prueba diciendo que
n es primo si y solo si las soluciones
x 2 = 1 (mod n) son x = ±1 .
Por lo tanto, si n pasa la prueba de Fermat, es decir,
a n−1 = 1 , también verificamos que
a (n−1)/2 = ±1 , ya que
a (n−1)/2 es la raÃz cuadrada de 1.
Desafortunadamente, números como, por ejemplo, 1729, el tercer número de Carmichael todavÃa puede engañar a esta prueba mejorada. ¿Qué pasa si iteramos? Es decir, hasta que esto sea posible, reduciremos el exponente a la mitad, hasta que alcancemos un número distinto de 1. Si al final obtenemos algo distinto de -1, entonces
n será compuesto.
Más formalmente, sea 2
S la mayor potencia de 2, divisible por n-1, es decir,
n−1=2 S q para algún número impar
q . Cada número de la secuencia
a n−1 = a (2^S)q ,
a (2^S-1)q , ...,
aq .
Esta es la raÃz cuadrada del miembro anterior de la secuencia.
Entonces, si
n es un número primo, entonces la secuencia debe comenzar con 1 y cada número subsiguiente también debe ser 1, o el primer miembro de la secuencia puede no ser igual a 1, pero entonces es -1.
La prueba de Miller-Rabin toma un a random
a∈ Z n aleatorio. Si la secuencia anterior no comienza con 1, o si el primer miembro de la secuencia no es 1 o -1, entonces
n no es simple.
Resulta que para cualquier
n compuesto, incluidos los números de Carmichael, la probabilidad de pasar la prueba de Miller-Rabin es aproximadamente 1/4. (En promedio, mucho menos.) Por lo tanto, la probabilidad de que
n pase varias pruebas disminuye exponencialmente.
Si
n no pasa la prueba de Miller-Rabin con una secuencia que comienza con 1, entonces tenemos una raÃz cuadrada no trivial de 1 módulo
n , y podemos
encontrar eficientemente los divisores de n . Por lo tanto, los números de Carmichael siempre son convenientes para factorizar.
Cuando la prueba se aplica a números de la forma
pq , donde
p y
q son números primos grandes, no pasan la prueba de Miller-Rabin en casi todos los casos, ya que la secuencia no comienza con 1. Por lo tanto, no podremos romper el RSA.
En la práctica, la prueba de Miller-Rabin se implementa de la siguiente manera:
- Dado
n , necesitamos encontrar s tal que n – 1 = 2 S q para alguna q impar. - Tomar al azar
a ∈ {1,...,n−1} - Si a q = 1, entonces
n pasa la prueba y detenemos la ejecución. - Para
i= 0, ... , s−1 verifique la igualdad a (2^i)q = −1 . Si la igualdad se mantiene, entonces n pasa la prueba (detener la ejecución). - Si no se cumple ninguna de las condiciones anteriores, entonces
n es compuesto.
Antes de realizar la prueba de Miller-Rabin, vale la pena realizar algunas divisiones más triviales en pequeños números primos.
Estrictamente hablando, estas pruebas son pruebas de si un número se considera compuesto, ya que no prueban de hecho que el número que se está comprobando es primo, pero definitivamente prueban que puede ser compuesto.
TodavÃa hay algoritmos deterministas que funcionan en tiempo polinómico para determinar la simplicidad (Agrawal, Kayal y
Saxena ), pero hoy se consideran poco prácticos.