Algoritmo rho de Pollard

Ro-algorithm ( -algorithm ) es un algoritmo propuesto por John Pollard en 1975 para factorizar (factorizar) números enteros. Este algoritmo se basa en el algoritmo de Floyd para encontrar la duración del ciclo en una secuencia y algunas consecuencias de la paradoja del cumpleaños . El algoritmo es más eficiente cuando factoriza números compuestos con factores suficientemente pequeños en la expansión. La complejidad del algoritmo se estima como [1] . $\rho$ $O(N^{1/4})$

El algoritmo ρ de Pollard construye una secuencia numérica , cuyos elementos forman un ciclo, a partir de algún número n , que puede ilustrarse mediante la disposición de los números en forma de la letra griega ρ , que era el nombre de la familia de algoritmos [2 ] [3] .

Historia del algoritmo

A finales de los años 60 del siglo XX, Robert Floyd ideó un método bastante efectivo para resolver el problema de encontrar ciclos , también conocido como el algoritmo de la “tortuga y la liebre” [4] . John Pollard , Donald Knuth y otros matemáticos han analizado el comportamiento de caso promedio de este algoritmo. Se han propuesto varias modificaciones y mejoras al algoritmo [5] .

En 1975, Pollard publicó un artículo [6] en el que, basándose en el algoritmo de detección del ciclo de Floyd, esbozaba la idea de un algoritmo de factorización de números que se ejecuta en el tiempo proporcional a [6] [1] . El autor del algoritmo lo llamó el método de factorización de Monte Carlo, que refleja la aparente aleatoriedad de los números generados durante el cálculo. Sin embargo, más tarde, el método aún recibió su nombre moderno: el algoritmo ρ de Pollard [7] . $N^{1/4}$

En 1981, Richard Brent y John Pollard utilizaron un algoritmo para encontrar los divisores más pequeños de los números de Fermat en [8] . La velocidad del algoritmo depende en gran medida solo del valor del divisor más pequeño del número original, pero no del número en sí. Entonces, encontrar el divisor más pequeño del séptimo número de Fermat - , lleva mucho más tiempo que encontrar el divisor del duodécimo número de Fermat (porque su divisor 114689 es mucho más pequeño, aunque el número en sí consta de más de 1200 dígitos decimales). $F_{n}=2^{2^{n}}+1$ $5\leq n\leq 13$ ${\begin{array}{lll}F_{7}=340282366920938463463374607431768211457=59\,649\,589\,127\,497\,217\cdot 5\,704\,689\,200\,685 \,129\,054\,721;\end{matriz}}$

Como parte del proyecto Cunningham , el algoritmo de Pollard ayudó a encontrar un divisor de 19 dígitos de largo . También se podían encontrar grandes divisores, pero el descubrimiento del método de factorización de la curva elíptica hizo que el algoritmo de Pollard no fuera competitivo [9] . $2^{2386}+1$

Descripción del algoritmo

Versión original

Consideramos una sucesión de enteros , tal que y , donde es el número a factorizar . El algoritmo original se ve así [10] [6] : ${x_{n}}$ $x_{0}=2$ $x_{i+1}=(x_{i}^{2}-1\,)(\mathrm {mod} \,N)$ $norte$

1. Se calculan los triples de números

(x_{i},x_{2i},Q_{i}),i=1,2,...

, donde .

Q_{i}\equiv \prod_{j=1}^{i}(x_{2j}-x_{j})\,(\mathrm {mod} \,N)

Además, cada uno de esos triples se obtiene del anterior. 2. Cada vez que un número es un múltiplo de otro número (por ejemplo, ), calcula el máximo común divisor mediante cualquier método conocido.

i

metro

metro=100

d_{i}=\mathrm {MCD} (Q_{i},N)

3. Si , entonces se encuentra una descomposición parcial del número , y .

1<d_{i}<N

norte

N=d_{i}\veces (N/d_{i})

El divisor encontrado puede ser compuesto, por lo que también debe factorizarse. Si el número es compuesto, continuamos el algoritmo con módulo .

d_{i}

n/d_{i}

N'=N/d_{i}

4. Los cálculos se repiten una vez. Si al mismo tiempo no se factorizó completamente el número, por ejemplo, se elige otro número inicial .

S

x_{{0}}

Versión moderna

Sea un entero positivo compuesto que desea factorizar. El algoritmo se ve así [11] : $norte$

Se selecciona aleatoriamente un pequeño número [12] y se construye una secuencia , definiendo cada siguiente como . $x_{{0}}$ $\{x_{n}\},n=0,1,2,...$ $x_{n+1}=F(x_{n})\,(\mathrm {mod} \,\,N)$
Simultáneamente, en cada i -ésimo paso, se calcula para algunos , tal que , por ejemplo, . $d=\mathrm {MCD} (N,|x_{i}-x_{j}|)$ $i$ $j$ $j<yo$ $yo=2j$
Si , entonces el cálculo finaliza y el número encontrado en el paso anterior es un divisor de . Si no es un número primo, entonces se continúa con el procedimiento de búsqueda del divisor, tomando como número . $d>1$ $d$ $norte$ $Dakota del Norte$ $norte$ $N'=N/d$

En la práctica, la función se elige no demasiado difícil de calcular (pero al mismo tiempo no es un polinomio lineal), siempre que no genere un mapeo uno a uno. Por lo general , las funciones [12] o [13] se seleccionan como . Sin embargo, las funciones y no encajan [10] . $F(x)$ $F(x)$ $F(x)=x^{2}\pm 1(\mathrm {mod} \,N)$ $F(x)=x^{2}\pm a(\mathrm {mod} \,N)$ $x^{2}-2$ $x^{2}$

Si se sabe que el divisor de un número es válido para algunos , entonces tiene sentido usar [10] . $pags$ $norte$ $p\equiv 1\,(\mathrm {mod} \,k)$ $k>2$ $F(x)=x^{k}+b$

Una desventaja significativa del algoritmo en esta implementación es la necesidad de almacenar una gran cantidad de valores anteriores . $x_{j}$

Mejoras en el algoritmo

La versión original del algoritmo tiene una serie de inconvenientes. Por el momento, hay varios enfoques para mejorar el algoritmo original.

deja _ Entonces, si , entonces , por lo tanto, si un par da una solución, entonces cualquier par dará una solución . $F(x)=(x^{2}-1)\mathrm {mod} \,N$ $(x_{j}-x_{i})\equiv 0(\mathrm {mod} \,p)$ $(f(x_{j})-f(x_{i}))\equiv 0(\mathrm {mod} \,p)$ $(x_{i},x_{j})$ $(x_{i+k},x_{j+k})$

Por lo tanto, no hay necesidad de verificar todos los pares , pero podemos restringirnos a pares de la forma , donde , y recorre el conjunto de valores consecutivos 1, 2, 3, ..., y toma valores de el intervalo Por ejemplo, , y [11] . $(x_{i},x_{j})$ $(x_{i},x_{j})$ $j=2^{k}$ $k$ $i$ $[2^{k}+1;2^{k+1}]$ $k=3$ $j=2^{3}=8$ $yo\en[9;16]$

Esta idea fue propuesta por Richard Brent en 1980 [14] y reduce el número de operaciones realizadas en aproximadamente un 25% [15] .

Floyd desarrolló otra variación del algoritmo ρ de Pollard . Según Floyd, el valor se actualiza en cada paso de acuerdo con la fórmula , por lo que los valores , se obtendrán en el paso y el GCD en este paso se calcula para y [11] . $y$ $y=F^{2}(y)=F(F(y))$ $i$ $x_{i}=F^{i}(x_{0})$ $y_{i}=x_{2i}=F^{2i}(x_{0})$ $norte$ $yx$

Un ejemplo de factorización de un número

Este ejemplo demuestra claramente el algoritmo ρ de factorización (versión del algoritmo, con la mejora de Floyd ), para el número N = 8051:

Tabla: factorización del número 8051

n = 8051, F ( x ) = ( x 2 + 1) mod n , x 0 = y 0 = 2
i	x yo = F ( x yo -1 )	y yo = F ( F ( y yo -1 ))	MCD(\| x yo − y yo \|, 8051)
una	5	26	una
2	26	7474	una
3	677	871	97

Usando otras variantes del polinomio , también se puede obtener un divisor de 83: $F(x)$

Tabla: factorización del número 8051

n = 8051, F ( x ) = ( x 2 + 3) mod n , x 0 = y 0 = 2
i	x yo = F ( x yo -1 )	y yo = F ( F ( y yo -1 ))	MCD(\| x yo − y yo \|, 8051)
una	7	52	una
2	52	1442	una
3	2707	778	una
cuatro	1442	3932	83

Por lo tanto, d 1 \u003d 97, d 2 \u003d 83 son divisores no triviales del número 8051.

Después de encontrar el divisor del número, en el algoritmo ρ se propone continuar con los cálculos y buscar los divisores del número si no es primo. En este ejemplo simple, este paso no era necesario [11] . $Dakota del Norte$ $Dakota del Norte$

Justificación del algoritmo ρ de Pollard

El algoritmo se basa en la conocida paradoja del cumpleaños .

La paradoja del cumpleaños, brevemente:
Vamos . Para una muestra aleatoria de elementos cada uno menor que , donde , la probabilidad de que dos elementos sean iguales . $\lambda>0$ $l+1$ $q$ $l={\raíz cuadrada {2\lambda q}}$ $p>1-e^{-\lambda}$

Cabe señalar que la probabilidad en la paradoja del cumpleaños se alcanza en . $p=0,5$ $\lambda \aprox. 0,69$

Deje que la secuencia consista en diferencias , verificadas durante el algoritmo. Se determina una nueva sucesión , donde , es el menor de los divisores del número . $\{Naciones Unidas}\}$ $x_{i}-x_{j}$ $\{z_{n}\}$ $z_{n}=u_{n}\,\mathrm {mod} \,q$ $q$ $norte$

Todos los miembros de la secuencia son menores que . Si la consideramos como una secuencia aleatoria de enteros menores que , entonces, según la paradoja del cumpleaños, la probabilidad de que entre sus miembros caigan dos iguales será mayor cuando , entonces debe ser al menos . $\{z_{n}\}$ ${\ sqrt {N}}$ $q$ $l+1$ $1/2$ $\lambda \aprox. 0,69$ $yo$ ${\sqrt {2\lambda q}}\aprox. {\sqrt {1,4q}}\aprox. 1,18{\sqrt {q}}$

Si , entonces , es decir, para algún número entero . Si , que se cumple con alta probabilidad, entonces el divisor deseado del número se encontrará como . Dado que , entonces con una probabilidad superior a , el divisor se encontrará en iteraciones [11] . $z_{i}=z_{j}$ $x_{i}-x_{j}\equiv 0\,\mathrm {mod} \,q$ $x_{i}-x_{j}=kq$ $k$ $x_{i}\neq x_{j}$ $q$ $norte$ $\mathrm {MCD} (N,|x_{i}-x_{j}|)$ ${\sqrt {q}}\leq n^{1/4}$ $1/2$ $norte$ $1,18\veces N^{1/4}$

Complejidad del algoritmo

Para estimar la complejidad del algoritmo , la secuencia construida en el curso de los cálculos se considera aleatoria (por supuesto, no se puede hablar de ningún rigor en este caso). Para factorizar completamente un número de bits de longitud , basta encontrar todos sus divisores que no excedan de , lo que requiere un máximo del orden de las operaciones aritméticas, u operaciones de bits. $norte$ $\beta$ ${\ sqrt {N}}$ ${\ sqrt {N}}$ $N^{1/4}\beta^{2}=2^{\beta /4}\beta^{2}$

Por lo tanto, la complejidad del algoritmo se estima como [16] . Sin embargo, esta estimación no tiene en cuenta la sobrecarga de calcular el máximo común divisor . La complejidad del algoritmo obtenida, aunque no exacta, está en buen acuerdo con la práctica. $O(N^{1/4})$

La siguiente afirmación es verdadera: sea un número compuesto . Entonces existe una constante tal que, para cualquier número positivo, la probabilidad del evento de que el algoritmo ρ de Pollard no encuentre un divisor no trivial en el tiempo no exceda de . Esta afirmación se deriva de la paradoja de los cumpleaños [17] . $norte$ $C$ $\lambda$ $norte$ $C{\sqrt {\lambda {\sqrt {N))))(\log N)^{2}$ $e^{-\lambda}$

Funciones de implementación

La cantidad de memoria utilizada por el algoritmo se puede reducir significativamente.

int Rho-Pollard ( int N) { int x = aleatorio (1, N-2); int y = 1; int i = 0; etapa int = 2; while (N.O.D.(N, abs (x - y)) == 1) { si (i == etapa){ y=x; etapa = etapa*2; } x = (x*x + 1) (módulo N); yo = yo + 1; } devuelve NOD (N, abs (xy)); }

En esta versión, el cálculo requiere almacenar solo tres variables , y , lo que distingue al algoritmo en tal implementación de otros métodos de factorización de números [11] . $norte$ $X$ $y$

Paralelización de algoritmos

El algoritmo de Pollard permite la paralelización utilizando tanto sistemas de memoria compartida como sistemas de memoria distribuida ( mensaje de paso ), pero el segundo caso es el más interesante desde un punto de vista práctico [18] .

Sistema de memoria distribuida

El método de paralelización existente radica en que cada nodo de cómputo ejecuta el mismo algoritmo secuencial , sin embargo, el número y/o polinomio original se toma de manera diferente. Para simplificar la paralelización, se propone recibirlos de un generador de números aleatorios. Sin embargo, tal implementación paralela no proporciona una aceleración lineal [19] . $x_{{0}}$ $F(x)$

Supongamos que hay artistas idénticos. Si usamos diferentes secuencias (es decir, diferentes polinomios ), entonces la probabilidad de que los primeros números en estas secuencias sean de diferente módulo será aproximadamente igual a . Por lo tanto, la aceleración máxima se puede estimar como [9] . $PAGS$ $PAGS$ $F(x)$ $k$ $pags$ $\exp({-k^{2}P}/{2p})$ $P^{1/2}$

Richard Crandall sugirió que se puede lograr la aceleración , pero esta afirmación aún no se ha verificado [20] . $O(P/(registro{P})^{2})$

Sistema de memoria compartida

El método anterior obviamente puede usarse en sistemas con memoria compartida, sin embargo, es mucho más razonable usar un solo generador [21] . $F(x)$

Notas

↑ 1 2 Pollard, 1974 , p. 521–528.
↑ Christensen, 2009 , 3.3.3.0.
↑ Chatterjee, 2008 , 5.2.2.
↑ Floyd, 1967 , pág. 636–644.
↑ Brent, 1980 , Un algoritmo de factorización Monte Carlo mejorado, p. 176.
↑ 1 2 3 Pollard, 1975 , Un método Monte Carlo para la factorización, p. 176.
↑ Koshy, 2007 , Teoría elemental de números con aplicaciones.
↑ Childs, 2009 , Una introducción concreta al álgebra superior.
↑ 1 2 Brent, 1999 , Algunos algoritmos paralelos para la factorización de enteros.
↑ 1 2 3 Pollard, 1975 , Un método de Monte Carlo para la factorización.
↑ 1 2 3 4 5 6 Ishmukhametov, 2011 , pág. 64.
↑ 1 2 Mollin, 2006 , pág. 215-216.
↑ Zolotykh N. Yu. Conferencias sobre álgebra informática. Tema 11. Método ρ de Pollard. Archivado el 30 de octubre de 2014 en Wayback Machine .
↑ Brent, 1980 , Un algoritmo de factorización Monte Carlo mejorado, p. 176-184.
↑ Reisel, 2012 , Áreas seleccionadas en criptografía. Números primos y métodos informáticos de factorización. 2ª ed..
↑ Cormen, 2001 , Introducción a los algoritmos. Sección 31.9. Factorización de enteros. Heurística rho de Pollard.
↑ Ishmukhametov, 2011 , pág. 63.
↑ Kosyakov, 2014 , pág. 12
↑ Kuhn, 2001 , Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logarithms, p. 212-229.
↑ Crandall, 1999 , Paralelización de la factorización de Polldar-rho.
↑ Kosyakov, 2014 , pág. 19

Literatura

Vasilenko O. N. Algoritmos teóricos de números en criptografía . - M. : MTSNMO , 2003. - 328 p. — ISBN 5-94057-103-4 . Archivado el 27 de enero de 2007 en Wayback Machine .
Ishmukhametov Sh. T. Métodos de factorización para números naturales: Libro de texto / Zakharov V.M. - Kazan: Universidad de Kazan, 2011. - P. 61-64. — 190 págs. — ISBN 978-3-659-17639-5 .
Kosyakov MS Introducción a la computación distribuida / NRU ITMO. - San Petersburgo. , 2014. - 155 págs.
German O.N., Nesterenko A.Yu. Métodos de Teoría de Números en Criptografía . - M. , 2012. - 300 p.
Solovyov Yu. P., Sadovnichy V. A. , Shavgulidze E. T. , Belokurov V. V. Curvas elípticas y algoritmos modernos de teoría de números. - M . : In-t computadora. isled., 2003. - 192 p. — ISBN ISBN 5-939722-27-X .
Brent RP = Algunos algoritmos paralelos para la factorización de enteros . - 1999. - S. 7 . -doi : 10.1017/ S0305004100049252 .
Brent RP Un algoritmo de factorización Monte Carlo mejorado // BIT Numerical Mathematics. - 1980. - 1 de junio ( vol. 20 , ns. 2 ). - pág. 176-184 . — ISSN 1572-9125 . -doi : 10.1007/ BF01933190 .
Chatterjee S., Sarkar P. Introducción // Cifrado basado en identidad. - Boston: Springer EE. UU., 2008. - ISBN 978-1-59693-238-8 .
Childs, Lindsay N. Congruences // Introducción concreta al álgebra superior . - 3ra ed. - EE.UU.: Springer, 2009. - S. 471-473. - 603 pág. — ISBN 978-0-387-74725-5 .
Chris Christensen. Revisión de Criptoanálisis moderno: técnicas para descifrar códigos avanzados por Christopher Swenson // Cryptologia. - 2009. - 27 de enero ( vol. 33 , número 1 ). — ISSN 0161-1194 . -doi : 10.1080/ 01611190802293397 .
Cormen TH, Leiserson CE, Rivest RL, Stein C. Algoritmos: construcción y análisis = Introducción a los algoritmos. - 2ª ed. - EE.UU.: MIT Press, 2001. - S. 897-907. — 1180 pág. — ISBN 9780262032933 .
Crandall RE = Paralelización de la factorización Polldar -rho . - 1999. Archivado el 6 de julio de 2010.
Koshy T. Congruencias // Teoría elemental de números con aplicaciones. - 2ª ed. - EE.UU.: Academic Press, 2007. - S. 238. - 771 p. — ISBN 9780123724878 .
Kuhn F., Struik R. Random Walks Revisited: Extensiones del algoritmo Rho de Pollard para calcular múltiples logaritmos discretos // Áreas seleccionadas en criptografía / Serge Vaudenay, Amr M.. - Springer Berlin Heidelberg, 2001. - P. 212 -229 . - ISBN 978-3-540-43066-7 , 978-3-540-45537-0 . -doi : 10.1007 / 3-540-45537-x_17 .
Mollin RA Introducción a la criptografía / Rosen KH. - 2. - Londres: Chapman and Hall, 2006. - 413 p. — ISBN 9781584886181 .
Pollard JM Un método Monte Carlo para la factorización // BIT Numerical Mathematics. - 1975. - vol. 15, núm. 3 . - Pág. 331-334.
Pollard JM Teoremas sobre factorización y pruebas de primalidad // Procedimientos matemáticos de la Sociedad Filosófica de Cambridge. - 1974. - T. 76 , núm. 03 . — S. 521–528 . — ISSN 1469-8064 . -doi : 10.1017/ S0305004100049252 .
Pollard JM Métodos de factorización y pruebas de primalidad. (Inglés) = Teoremas sobre factorización y pruebas de primalidad. // Procedimientos matemáticos de la Sociedad Filosófica de Cambridge. - 1974. - T. 76 , N º 3 . - art. 521 . -doi : 10.1017/ S0305004100049252 .
Reisel, H. Números primos y métodos informáticos para la factorización. - 2ª ed. - EE.UU.: Springer, 2012. - S. 183. - 464 p. - ISBN 978-0-8176-8297-2 .
Robert W. Floyd. Algoritmos no deterministas // J. ACM. - 1967. - T. 14 , núm. 4 . — S. 636–644 . — ISSN 0004-5411 . -doi : 10.1145/ 321420.321422 .

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin