El algoritmo rho de Pollard es un algoritmo para la factorización de 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 tamaño 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. , dónde es un factor no trivial. Un módulo polinomial, llamada (p.ej, ), se utiliza para generar una secuencia pseudoaleatoria : se elige un valor inicial, digamos 2, y la secuencia continúa como, , , etc. La secuencia está relacionada con otra secuencia . Desdeno se conoce de antemano, esta secuencia no se puede calcular explícitamente en el algoritmo. Sin embargo, en él radica la idea central del algoritmo.
Debido a que el número de valores posibles para estas secuencias es finito, tanto el secuencia, que es mod , y 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 antes de que ocurra una repetición, se esperaría que sea , dónde es el número de valores posibles. Entonces la secuencia probablemente se repita mucho antes que la secuencia . Una vez que una secuencia tiene un valor repetido, la secuencia circulará, porque cada valor depende solo del anterior. Esta estructura de ciclo eventual da lugar al nombre "algoritmo Rho", debido a la similitud con la forma del carácter griego ρ cuando los valores, , etc. se representan como nodos en un gráfico dirigido .
Esto es detectado por el algoritmo de búsqueda de ciclos de Floyd : dos nodos y (es decir, y ) se mantienen. En cada paso, uno se mueve al siguiente nodo de la secuencia y el otro avanza en dos nodos. Después de eso, se comprueba si. Si no es 1, esto implica que hay una repetición en el secuencia (es decir . Esto funciona porque si el es lo mismo que , 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 que no sea 1. Esto puede ser sí mismo, ya que las dos secuencias pueden repetirse al mismo tiempo. En este caso (poco común), el algoritmo falla y puede repetirse con un parámetro diferente.
Algoritmo
El algoritmo toma como entradas n , el número entero 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 usar . La salida es un factor no trivial de n , o falla. Realiza los siguientes pasos: [2]
x ← 2 y ← 2 d ← 1 mientras que d = 1: x ← g (x) y ← g (g (y)) d ← mcd (| x - y |, n) if d = n: return failure else : return d
Aquí x y Y corresponde a y en la sección sobre la idea central. 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 se puede intentar de nuevo, utilizando un valor inicial diferente de 2 o un valor diferente..
Ejemplo de factorización
Dejar y .
I | X | y | MCD (| x - y |, 8051) |
---|---|---|---|
1 | 5 | 26 | 1 |
2 | 26 | 7474 | 1 |
3 | 677 | 871 | 97 |
4 | 7474 | 1481 | 1 |
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. Una iteración adicional se muestra arriba para aclarar que y se mueve dos veces más rápido que x . Tenga en cuenta que incluso después de una repetición, el GCD 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 de Brent relacionado . [3]
Pollard y Brent realizaron una mejora adicional. Observaron que si, Después también para cualquier entero positivo . En particular, en lugar de computar a cada paso, basta con definir como el producto de 100 consecutivos términos modulo y luego calcular un solo . Se obtiene una mayor aceleración ya que los pasos de 100 gcd se reemplazan con el módulo de 99 multiplicacionesy un solo mcd . Ocasionalmente puede hacer que el algoritmo falle al introducir un factor repetido, por ejemplo cuandoes un cuadrado. Pero luego basta con volver al término anterior de gcd , donde, y use el algoritmo ρ regular a partir de ahí.
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 del número de Fermat F 8 = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321. [4] El algoritmo ρ fue una buena elección para F 8 porque el factor primo p = 1238926361552897 es. La factorización tomó 2 horas en un UNIVAC 1100/42 . [4]
El ejemplo n = 10403 = 101 · 103
En este ejemplo, solo se calcula una secuencia y el mcd se calcula dentro del bucle que detecta el ciclo.
Ejemplo de código C
El siguiente ejemplo de código encuentra el factor 101 de 10403 con un valor inicial de x = 2.
#include #include int gcd ( int a , int b ) { int resto ; while ( b ! = 0 ) { resto = a % b ; a = b ; b = resto ; } return a ; }int main ( int argc , char * argv []) { int numero = 10403 , loop = 1 , count ; int x_fixed = 2 , x = 2 , tamaño = 2 , factor ; do { printf ( "---- bucle% 4i ---- \ n " , bucle ); cuenta = tamaño ; hacer { x = ( x * x + 1 ) % número ; factor = mcd ( abs ( x - x_fixed ), número ); printf ( "recuento =% 4i x =% 6i factor =% i \ n " , tamaño - recuento + 1 , x , factor ); } while ( - contar && ( factor == 1 )); tamaño * = 2 ; x_fixed = x ; bucle = bucle + 1 ; } while ( factor == 1 ); printf ( "el factor es% i \ n " , factor ); factor de retorno == número ? EXIT_FAILURE : EXIT_SUCCESS ; }
El código anterior mostrará el progreso del algoritmo, así como los valores intermedios. La línea de salida final será "el factor es 101". El código solo funcionará para valores de prueba pequeños, ya que se producirá un desbordamiento en los tipos de datos enteros durante el cuadrado de x.
Muestra de código de Python
desde itertools import count desde math import gcd import sysnúmero , x = 10403 , 2para ciclo en recuento ( 1 ): y = x para i en rango ( 2 ** ciclo ): x = ( x * x + 1 ) % factor numérico = mcd ( x - y , número ) si factor > 1 : imprimir ( "factor es" , factor ) sys . salir ()
Los resultados
En la siguiente tabla, la tercera y cuarta columnas contienen información secreta que no conoce la persona que intenta factorizar pq = 10403. Se incluyen para mostrar cómo funciona el algoritmo. Comenzando con x = 2, el algoritmo produce los siguientes números:
paso | ||||
---|---|---|---|---|
2 | 2 | 2 | 2 | 0 |
5 | 2 | 5 | 2 | 1 |
26 | 2 | 26 | 2 | 2 |
677 | 26 | 71 | 26 | 3 |
598 | 26 | 93 | 26 | 4 |
3903 | 26 | sesenta y cinco | 26 | 5 |
3418 | 26 | 85 | 26 | 6 |
156 | 3418 | 55 | 85 | 7 |
3531 | 3418 | 97 | 85 | 8 |
5168 | 3418 | 17 | 85 | 9 |
3724 | 3418 | 88 | 85 | 10 |
978 | 3418 | 69 | 85 | 11 |
9812 | 3418 | 15 | 85 | 12 |
5983 | 3418 | 24 | 85 | 13 |
9970 | 3418 | 72 | 85 | 14 |
236 | 9970 | 34 | 72 | 15 |
3682 | 9970 | 46 | 72 | dieciséis |
2016 | 9970 | 97 | 72 | 17 |
7087 | 9970 | 17 | 72 | 18 |
10289 | 9970 | 88 | 72 | 19 |
2594 | 9970 | 69 | 72 | 20 |
8499 | 9970 | 15 | 72 | 21 |
4973 | 9970 | 24 | 72 | 22 |
2799 | 9970 | 72 | 72 | 23 |
El primer módulo de repetición 101 es 97 que se produce en el paso 17. La repetición no se detecta hasta el paso 23, cuando . Esto causa ser - estar y se encuentra un factor.
Complejidad
Si el número pseudoaleatorio que ocurren en el algoritmo Pollard ρ fueran un número aleatorio real, se seguiría que el éxito se lograría la mitad del tiempo, por la paradoja del cumpleaños eniteraciones. 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 permanece abierto. [5]
Ver también
Referencias
- ^ 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 .
- ^ 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 ed.). Cambridge, MA: MIT Press. págs. 975–980. ISBN 978-0-262-03384-8. (esta sección analiza solo el algoritmo rho de Pollard).
- ^ Brent, Richard P. (1980). "Un algoritmo de factorización de Monte Carlo mejorado" . BIT . 20 : 176-184. doi : 10.1007 / BF01933190 .
- ^ a b 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 .
- ^ 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
- Katz, Jonathan; Lindell, Yehuda (2007). "Capítulo 8". Introducción a la criptografía moderna . Prensa CRC.
- Samuel S. Wagstaff, Jr. (2013). La alegría de la factorización . Providence, RI: Sociedad Matemática Estadounidense. 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 de Pollard rho" . MathWorld .
- Implementación de Java
- Acerca de Pollard rho