El algoritmo rho de Pollard

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

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

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

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

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

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

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: devolver error; de lo contrario : devolver d

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

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

Ahora bien, 97 es un factor no trivial de 8051. Valores iniciales distintos de x = y = 2 pueden dar como resultado el cofactor (83) en lugar de 97. Arriba se muestra una iteración adicional para dejar 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 ser 1.

En 1980, Richard Brent publicó una variante más rápida del algoritmo rho. Utilizó 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 ]} CLRS (Cormen et Al. Introduction to Algorithms book) proporciona un análisis heurístico y condiciones de fallo (el divisor trivial${\displaystyle n}$se encuentra). ^{[ 2 ]}

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

El algoritmo es muy rápido para números con factores pequeños, pero más lento en casos donde 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 opción para F ₈ porque el factor primo p = 1238926361552897 es mucho menor que el otro factor. La factorización tardó 2 horas en una UNIVAC 1100/42 . ^{[ 4 ]}

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

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

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

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

• 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 Australasiano de Teoría (CATS2008). Wollongong. págs. 125-131 .  Describe las mejoras que se pueden obtener mediante diferentes funciones de iteración y algoritmos de detección 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. pp. 135–138 . ISBN  978-1-4704-1048-3.

• 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 en Java
• Acerca de Pollard rho