Factorizacion de enteros

Pollard Rho en Introducci’n o .. 4. 3 Implementaci ‘ n del Algoritmo de . . 05 Conclusi’no Para tener mejor comprensi’ n del funcionamiento de la factorizaci» n de enteros es necesario o o conocer algunas definiciones y teoremas de aritm ‘tlca. e Definici n 1. 1 (Factor) un factor de a es denominado como los divisores no triviales de a, o es decir, todos aquellos divisores distintos de 1 y a. Definici • n 1. 2 (N ‘ mero primo) Un entero a > 1, donde sus unicos divisores son unicamente ou ‘ 1 ya tro n mero entero es denominado n ‘ mero com s considerado como u u enteros negativos no son considerados como primos o compuestos. . 1 Com’ n divisor y gcd (m ‘ ximo com’ n divisor). u a u Com• n Divisor u Definici’n 2. 1 (Com» n Divisor) Si d es un divisor de ay tambien es divisor de b, entonces o u d es un comun divisor de ay b. Para cualquier par de enteros y, x se cumple que: si d lay dl b entonces dl(a + b) y d I (a — b) (a) De manera mas general tenemos que si: d la y d lb entonces dl(ax by) (b) para cualquier entero x y y. a lb, entonces ya sea lal O, y b > O entonces gcd(a, b) es el elemento positivo de menor valor del conjunto ax + by : x, y e Z de combinaciones lineales de ay b.

Demostraci n 2. 1 Sea s el elemento positivo de menor valor de la combinaci ‘n lineal de ayo o b, y sea s — ax + by para alg’nx,y Z. Sea q — [a/s] Dada la ecuaci’n (3), se tiene que: u oa mods = a – qs a mod s a — q(ax + by)a mod s a(l — qx) + y as» a mod s es una combinaci•n lineal de a y tambi ‘n de b. Como O = s. la ecuaci ‘n (b) indica que u o gcd(a, b)ls, dado que gcd(a, b) divide ay b, y s es una combinaci n lineal de ay b. o Gcd(a, b) Isy s > O entonces gcd(a, b) = sy gcd(a, b) bl (los otros casos ser’ lan parecidos).

Dividamos ambos productos por 2b1 . A la izquierda queda el factor 2a1 – bl mientras que a la derecha no queda ning’n 2; Ent 31_1f6 2b1 . A la izquierda queda el factor 2a1 — bl mientras que a la erecha no queda ning’ n 2; Entonces el u termino de izquierda es divisible por dos pero el de derecha no lo es (porque el primo 2 no divide ning- n otro primo y por consguiente no divide el producto, seg’n el teorema de Euclides). u u Esto es absurdo porque ambos t • rminos son iguales. e 4 4. 1 pollard Rho Algoritmo de Pollard Rho Algoritmo 4. 1 (Pollard Rho) . 1 2. XI 3. y- XI 4. e 2 5. while TRUE 6. I- • -i +1 7. xi x2 mod n i- 1 8. d gcd(y -xi , n) 9. ifd 1 andd n 10. printd 4. 2 Funcionamiento del Algoritmo de pollard Rho Las l’ Ineas 1 y 2 inicializan con un valor de 1 y XI con un alor aleatorio entre Oy n- 1, la l’ ‘nea 3 y 4 inicializan al valor aleatorio XI y k con un valor 2. En la I • Inea 5 el ciclo while realiza iteraciones infin- Itamente aumentando la i en la l’ Inea 6; la I Inea 7 busca la recurrencia para los valores de xi , en la l’ Inea 8 se calcula el m ‘ximo com’n divisor a u asign ‘ ndolo a d. En la l’ ‘nea 9, es condicionado el valor encontrado en la l» ‘nea antenor de la slguiente manera: SI el valor no es trivlal la linea 10 lo imprime. En la l’ Inea 11 se compara si el valor de es igual al de k, si es asi, la linea 12 asigna un nuevo valor a y, 1 se compara si el valor de i es igual al de k, si es asi, la linea 12 asigna un nuevo valor a y, entonces la l’ nea 13 duplica el valor que contiene k, este ultimo valor determina que ‘ n’ mero se va a guardar en y. A pesar de que el while dice iterar por siempre, el criterio de paro est» basado en un algoa ritmo de deteccion de ciclos, asi cuando detecte un ciclo (basado en las relaciones de equivalencia de la aritm ‘ tica modular) en la recurrencia este se detendra. e 6 4. 3 Implementaci’n del Algoritmo de Pollard Rho en C o Figura 1: Implementaci’ n de la funci’n GCD en Coo La figura 1 uestra la funci• n GCD, esta funci• n es necesaria para obtemer el m’ ximo o o a com’n divisor, recibe como par’ metros la pareja de n ‘ meros cuyo divisor quiere saber, en este u a u caso son de tipo long long int para soportar n’ meros grandes. 7 Figura 2: Implementaci ‘ n de la funci’n Pollard Rho o o La figura 2 muestra la implementacion de Pollard Rho en C, considera la factorizaci•n unica o validando si el residuo del n mero dado es 00 1, si el residuo es O entonces el algoritmo valida u nuevamete el residuo entre ny i (i = 2); si el residuo es 0 entonces divide el numero entre i e imprime el primer factor unico. La validacion se repite hasta que el residuo es 1, entonces aumenta imprime el primer factor unico. ‘ La validacion se repite hasta que el residuo es 1, entonces aumenta i en 1 y vuelve a validar, al terminar esto el programa termina.

Cuando n solo tiene factores triwales, s • lo divide n entre ese factor, imprimiendo el resultado o y terminando el programa rompiendo el ciclo while con break. En la implementacion no se usaron subindices de x ya que no fue necesario guardar los valores 8 generados. Figura 3: Ejecuci’n del algoritmo Pollard Rho o Conclusi ‘no Si bien el algoritmo de Pollard Rho es una buena opci n para levar a cabo la factorizaci’n de o o enteros, no deja de ser una heur’ Istica, por lo tanto, ni el ‘xito ni el tiempo de ejecuci’n estan e o garantzados para todos los casos.

El tiempo de corrida para n’ meros muy grandes puede ser u excesivo si se utiliza la factorizaci•n como parte de alg• n procedimiento. o u Bibliograf• la [1] Autor:L. A. Kaluzhnin Teorema fundamental de aritmetica Lecciones populares de matematicas . Rubinos-1860, 1994. [2] Autor:Cormen, Thomas H. Leiserson, Charles E. Rivest, Ronald Stein, Clifford Introduction to Algorithms. Cambridge, MA: MIT press, 2001. A Documento realizado en