Algoritmo rho de Pollard

Algoritmo de factorización de enteros

El algoritmo rho de Pollard es un algoritmo para la factorización de enteros . Fue inventado por John Pollard en 1975. ^[1] Utiliza sólo 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 factoriza.

Ideas centrales

El algoritmo se utiliza para factorizar un número , donde es un factor no trivial. Un módulo polinómico , llamado (p. ej., ), se utiliza para generar una secuencia pseudoaleatoria . Es importante señalar 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 . Como no se conoce de antemano, esta secuencia no se puede calcular explícitamente en el algoritmo. Sin embargo, en ello 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}$

Debido a que el número de valores posibles para estas secuencias es finito, tanto la secuencia, que es mod como la secuencia, eventualmente se repetirán, 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, es probable que la secuencia se repita mucho antes que la secuencia . Cuando se ha encontrado tal que pero , el número es múltiplo de , así se ha encontrado. ${\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}$ ${\displaystyle p}$

Una vez que una secuencia tiene un valor repetido, la secuencia realizará un ciclo, porque cada valor depende sólo del anterior. Esta estructura de ciclo 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 gráfico dirigido . ${\displaystyle x_{1}{\bmod {p}}}$ ${\displaystyle x_{2}{\bmod {p}}}$

Diagrama de ciclo que se asemeja a la letra griega  ρ

Esto lo detecta el algoritmo de búsqueda de ciclos de Floyd : se mantienen dos nodos y (es decir, y ). En cada paso, uno avanza al siguiente nodo de la secuencia y el otro avanza dos nodos. Después de eso, se comprueba 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 resultante divisor (MCD) es un divisor distinto de 1. Este puede ser él mismo, ya que las dos secuencias pueden repetirse al mismo tiempo. En este caso (poco común), el algoritmo falla y se puede repetir 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 entrada n , el número entero que se va a factorizar; y , un polinomio en x calculado módulo n . En el algoritmo original, pero hoy en día es más común utilizar . El resultado es un factor no trivial de n o un fallo. ${\displaystyle g(x)}$ ${\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 re ← 1 mientras d = 1: x ← g(x) y ← gramo(gramo(y)) d ← mcd(|x - y|, n) si d = n: retorno fallido  ; de lo contrario : retorno d

Aquí x e y corresponden a y en la sección anterior. Tenga en cuenta que este algoritmo puede no encontrar un factor no trivial incluso cuando n es compuesto. En ese caso, el método se puede intentar nuevamente, usando un valor inicial de x distinto de 2 ( ) o un , , diferente con . ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\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

Deja 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. Los valores iniciales distintos de x = y = 2 pueden dar el cofactor (83) en lugar de 97. Arriba se muestra una iteración adicional para dejar claro que y se mueve dos veces más rápido que x . Tenga en cuenta 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. Usó las mismas ideas centrales que Pollard pero un método diferente de detección de ciclos, reemplazando el algoritmo de búsqueda de ciclos de Floyd con el método de búsqueda de ciclos relacionado de Brent . ^[3]

Pollard y Brent lograron una mejora adicional. Observaron que si , entonces también para cualquier número entero positivo . En particular, en lugar de calcular en cada paso, basta con definirlo como el producto de 100 términos consecutivos módulo y luego calcular un único . Se produce una importante aceleración ya que los pasos de 100 mcd se reemplazan con un módulo de 99 multiplicaciones y un solo mcd . Ocasionalmente, puede provocar que el algoritmo falle al introducir un factor repetido, por ejemplo, cuando es un cuadrado . Pero entonces basta con volver al término mcd anterior , donde , y utilizar el algoritmo ρ regular a partir de ahí. ${\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 los casos en 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: factorizar n = 10403 = 101 · 103

La siguiente tabla muestra los números producidos por el algoritmo, comenzando y usando 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}$

El primer módulo de repetición 101 es 97, que ocurre 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 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 permanece abierto. ^[5] ${\displaystyle x=g(x)}$ ${\displaystyle O({\sqrt {p}})\leq O(n^{1/4})}$

Ver también

• Algoritmo rho de Pollard para logaritmos
• Algoritmo canguro de Pollard

Referencias

1. Pollard, JM (1975). "Un método de Monte Carlo para la factorización". BIT Matemáticas Numéricas . 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 números enteros". Introducción a los algoritmos (tercera ed.). 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". POCO . 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. Prensa de la Universidad de Cambridge. págs. 272-273. ISBN 9781107013926..

Otras lecturas

• 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 . El Simposio de Teoría de Australasia (CATS2008). Wollongong. págs. 125-131. Describe las mejoras disponibles de 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 . Prensa CRC.
• Samuel S. Wagstaff, Jr. (2013). El placer del factoraje. Providence, RI: Sociedad Estadounidense de Matemáticas. págs. 135-138. ISBN 978-1-4704-1048-3.

enlaces externos

• Artículo completo sobre el algoritmo Rho de Pollard dirigido a una audiencia de nivel introductorio
• Weisstein, Eric W. "Método de factorización Pollard rho". MundoMatemático .
• Implementación de Java
• Acerca de Pollard rho