Algoritmo rho de Pollard

Algoritmo de factorización de números enteros

El algoritmo rho de Pollard es un algoritmo de factorización de números enteros . Fue inventado por John Pollard en 1975. ^[1] Utiliza solo una pequeña cantidad de espacio y su tiempo de ejecución esperado es proporcional a la raíz cuadrada del factor primo más pequeño del número compuesto que se está factorizando.

Ideas centrales

El algoritmo se utiliza para factorizar un número , donde es un factor no trivial. Se utiliza un polinomio módulo , llamado (por ejemplo, ), para generar una secuencia pseudoaleatoria . Es importante tener en cuenta que debe ser un polinomio. Se elige un valor inicial, digamos 2, y la secuencia continúa como , , , etc. La secuencia está relacionada con otra secuencia . Dado que no se conoce de antemano, esta secuencia no se puede calcular explícitamente en el algoritmo. Sin embargo, en ella reside la idea central del algoritmo. ${\displaystyle n=pq}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle g(x)}$ ${\displaystyle g(x)=(x^{2}+1){\bmod {n}}}$ ${\displaystyle g(x)}$ ${\displaystyle x_{1}=g(2)}$ ${\displaystyle x_{2}=g(g(2))}$ ${\displaystyle x_{3}=g(g(g(2)))}$ ${\displaystyle \{x_{k}{\bmod {p}}\}}$ ${\displaystyle p}$

Como el número de valores posibles para estas secuencias es finito, tanto la secuencia, que es mod , como la secuencia se repetirán eventualmente, aunque estos valores sean desconocidos. Si las secuencias se comportaran como números aleatorios, la paradoja del cumpleaños implica que se esperaría que el número de antes de que ocurra una repetición fuera , donde es el número de valores posibles. Por lo tanto, la secuencia probablemente se repetirá mucho antes que la secuencia . Cuando se ha encontrado un tal que pero , el número es un múltiplo de , por lo que se ha encontrado un divisor no trivial. ^[2] ${\displaystyle \{x_{k}\}}$ ${\displaystyle n}$ ${\displaystyle \{x_{k}{\bmod {p}}\}}$ ${\displaystyle x_{k}}$ ${\displaystyle O({\sqrt {N}})}$ ${\displaystyle N}$ ${\displaystyle \{x_{k}{\bmod {p}}\}}$ ${\displaystyle \{x_{k}\}}$ ${\displaystyle k_{1},k_{2}}$ ${\displaystyle x_{k_{1}}\neq x_{k_{2}}}$ ${\displaystyle x_{k_{1}}\equiv x_{k_{2}}{\bmod {p}}}$ ${\displaystyle |x_{k_{1}}-x_{k_{2}}|}$ ${\displaystyle p}$

Una vez que una secuencia tiene un valor repetido, la secuencia se cíclica, porque cada valor depende únicamente del anterior. Esta estructura de ciclado eventual da lugar al nombre de "algoritmo rho", debido a la similitud con la forma de la letra griega ρ cuando los valores , , etc. se representan como nodos en un grafo dirigido . ${\displaystyle x_{1}{\bmod {p}}}$ ${\displaystyle x_{2}{\bmod {p}}}$

Diagrama de ciclo que se asemeja a la letra griega  ρ

Esto se detecta mediante el algoritmo de búsqueda de ciclos de Floyd : se mantienen dos nodos y (es decir, y ). En cada paso, uno se mueve al siguiente nodo en la secuencia y el otro avanza dos nodos. Después de eso, se verifica si . Si no es 1, entonces esto implica que hay una repetición en la secuencia (es decir . Esto funciona porque si es igual a , la diferencia entre y es necesariamente un múltiplo de . Aunque esto siempre sucede eventualmente, el máximo común divisor (MCD) resultante es un divisor de distinto de 1. Esto puede ser en sí mismo, ya que las dos secuencias podrían repetirse al mismo tiempo. En este caso (poco común) el algoritmo falla y puede repetirse con un parámetro diferente. ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle \gcd(x_{i}-x_{j},n)\neq 1}$ ${\displaystyle \{x_{k}{\bmod {p}}\}}$ ${\displaystyle x_{i}{\bmod {p}}=x_{j}{\bmod {p}})}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle n}$

Algoritmo

El algoritmo toma como entradas n , el entero a factorizar; y ⁠ ⁠ ${\displaystyle g(x)}$ , un polinomio en x calculado módulo n . En el algoritmo original, , pero hoy en día es más común utilizar . La salida es un factor no trivial de n o un fallo. ${\displaystyle g(x)=(x^{2}-1){\bmod {n}}}$ ${\displaystyle g(x)=(x^{2}+1){\bmod {n}}}$

Realiza los siguientes pasos: ^[2]

Pseudocódigo para el algoritmo rho de Pollard

 x ← 2 // valor inicial y ← x d ← 1 mientras d = 1: x ← g(x) y ← g(g(y)) d ← mcd(|x - y|, n) si d = n: devuelve fallo  de lo contrario : devuelve d

Aquí x e y corresponden a ⁠ ⁠ ${\displaystyle x_{i}}$ y ⁠ ⁠ ${\displaystyle x_{j}}$ en la sección anterior. Nótese que este algoritmo puede fallar en encontrar un factor no trivial incluso cuando n es compuesto. En ese caso, el método puede probarse nuevamente, utilizando un valor inicial de x distinto de 2 ( ) o un ⁠ ⁠ , , diferente con . ${\displaystyle 0\leq x<n}$ ${\displaystyle g(x)}$ ${\displaystyle g(x)=(x^{2}+b){\bmod {n}}}$ ${\displaystyle 1\leq b<n-2}$

Ejemplo de factorización

Sea y . ${\displaystyle n=8051}$ ${\displaystyle g(x)=(x^{2}+1){\bmod {8}}051}$

Ejemplo de factorización del algoritmo rho de Pollard para y , con valor inicial 2. El ejemplo utiliza el algoritmo de búsqueda de ciclos de Floyd . ${\displaystyle n=253}$ ${\displaystyle g(x)=x^{2}{\bmod {2}}53}$

Ahora 97 es un factor no trivial de 8051. Valores iniciales distintos de x = y = 2 pueden dar el cofactor (83) en lugar de 97. Se muestra una iteración adicional arriba para dejar en claro que y se mueve el doble de rápido que x . Nótese que incluso después de una repetición, el MCD puede volver a 1.

Variantes

En 1980, Richard Brent publicó una variante más rápida del algoritmo rho. Utilizó las mismas ideas básicas que Pollard pero un método diferente de detección de ciclos, reemplazando el algoritmo de búsqueda de ciclos de Floyd por el método de búsqueda de ciclos de Brent relacionado . ^[3] CLRS proporciona un análisis heurístico y condiciones de falla ( se encuentra el divisor trivial). ^[2] ${\displaystyle n}$

Pollard y Brent realizaron una mejora adicional. Observaron que si , entonces también para cualquier entero positivo ⁠ ⁠ . En particular, en lugar de calcular en cada paso, basta con definir ⁠ ⁠ como el producto de 100 términos consecutivos módulo ⁠ ⁠ , y luego calcular un solo . Se produce una aceleración importante ya que 100 pasos de mcd se reemplazan con 99 multiplicaciones módulo ⁠ ⁠ y un solo mcd . Ocasionalmente puede hacer que el algoritmo falle al introducir un factor repetido, por ejemplo cuando ⁠ ⁠ es un cuadrado . Pero entonces basta con volver al término de mcd anterior, donde , y usar el algoritmo ρ regular a partir de allí. ^{[nota 1]} ${\displaystyle \gcd(a,n)>1}$ ${\displaystyle \gcd(ab,n)>1}$ ${\displaystyle b}$ ${\displaystyle \gcd(|x-y|,n)}$ ${\displaystyle z}$ ${\displaystyle |x-y|}$ ${\displaystyle n}$ ${\displaystyle \gcd(z,n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \gcd(z,n)=1}$

Solicitud

El algoritmo es muy rápido para números con factores pequeños, pero más lento en casos en los que todos los factores son grandes. El éxito más notable del algoritmo ρ fue la factorización en 1980 del número de Fermat F ₈ = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321. ^[4] El algoritmo ρ fue una buena elección para F ₈ porque el factor primo p = 1238926361552897 es mucho más pequeño que el otro factor. La factorización tomó 2 horas en un UNIVAC 1100/42 . ^[4]

Ejemplo: factorizaciónnorte= 10403 = 101 · 103

La siguiente tabla muestra los números producidos por el algoritmo, comenzando con y utilizando el polinomio . La tercera y cuarta columnas de la tabla contienen información adicional que el algoritmo no conoce. Se incluyen para mostrar cómo funciona el algoritmo. ${\displaystyle x=2}$ ${\displaystyle g(x)=(x^{2}+1){\bmod {1}}0403}$

La primera repetición módulo 101 es 97, que se produce en el paso 17. La repetición no se detecta hasta el paso 23, cuando . Esto hace que sea , y se encuentra un factor. ${\displaystyle x\equiv y{\pmod {101}}}$ ${\displaystyle \gcd(x-y,n)=\gcd(2799-9970,n)}$ ${\displaystyle p=101}$

Complejidad

Si el número pseudoaleatorio que aparece en el algoritmo ρ de Pollard fuera un número aleatorio real, se deduciría que el éxito se lograría la mitad de las veces, mediante la paradoja del cumpleaños en las iteraciones. Se cree que el mismo análisis se aplica también al algoritmo rho real, pero se trata de una afirmación heurística y el análisis riguroso del algoritmo sigue abierto. ^[5] ${\displaystyle x=g(x)}$ ${\displaystyle O({\sqrt {p}})\leq O(n^{1/4})}$

Véase también

• Algoritmo rho de Pollard para logaritmos
• El algoritmo del canguro de Pollard

Notas

1. Ejercicio 31.9-4 en CLRS

Referencias

1. Pollard, JM (1975). "Un método de Monte Carlo para la factorización" (PDF) . BIT Numerical Mathematics . 15 (3): 331–334. doi :10.1007/bf01933667. S2CID  122775546.
2. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. y Stein, Clifford (2009). "Sección 31.9: Factorización de enteros". Introducción a los algoritmos (tercera edición). Cambridge, MA: MIT Press. págs. 975–980. ISBN 978-0-262-03384-8.(Esta sección analiza únicamente el algoritmo rho de Pollard).
3. Brent, Richard P. (1980). "Un algoritmo de factorización de Monte Carlo mejorado". BIT . 20 (2): 176–184. doi :10.1007/BF01933190. S2CID  17181286.
4. Brent, RP; Pollard, JM (1981). "Factorización del octavo número de Fermat". Matemáticas de la computación . 36 (154): 627–630. doi : 10.2307/2007666 . JSTOR  2007666.
5. Galbraith, Steven D. (2012). "14.2.5 Hacia un análisis riguroso de Pollard rho". Matemáticas de la criptografía de clave pública. Cambridge University Press. págs. 272-273. ISBN 9781107013926..

Lectura adicional

• Bai, Shi; Brent, Richard P. (enero de 2008). "Sobre la eficiencia del método Rho de Pollard para logaritmos discretos". Conferencias sobre investigación y práctica en tecnología de la información, vol. 77. Simposio de teoría de Australasia (CATS2008). Wollongong. págs. 125–131. Describe las mejoras disponibles en diferentes funciones de iteración y algoritmos de búsqueda de ciclos.
• Katz, Jonathan; Lindell, Yehuda (2007). "Capítulo 8". Introducción a la criptografía moderna . CRC Press.
• Samuel S. Wagstaff, Jr. (2013). El placer de factorizar. Providence, RI: American Mathematical Society. págs. 135–138. ISBN 978-1-4704-1048-3.

Enlaces externos

• Artículo completo sobre el algoritmo Rho de Pollard dirigido a un público de nivel introductorio
• Weisstein, Eric W. "Método de factorización rho de Pollard". MathWorld .
• Implementación de Java
• Acerca de Pollard rho