Factorizacion de enteros

Factorizaci´n de enteros o
Mendoza Garc´ Leo Joaquin Rodrigo, Vergara Delgado Victor Manuel ıa November 3, 2011

Resumen La descomposici´n de n´meros en sus factores primos, podr´ parecer una tarea trivial, o u ıa pero el costo computacional de hacerlo por m´todos de fuerza bruta es muy alto; Para llevar e a cabo esta tarea en un tiempo de ejecuci´n razonable, es necesario estudiar conceptostanto o de aritm´tica b´sica como aritm´tica modular. Bas´ndose en estos conceptos, John Pollard, e a e a un matem´tico brit´nico, desarroll´ el algoritmo conocido como Pollard-rho en 1975. Este a a o algoritmo especialmente efic´z cuando se descomponen n´meros cuyos factores no son muy a u grandes.

Contenido
1 Introducci´n o 2 Com´ n divisor y gcd (m´ximo u a 2.1 Com´n Divisor . . . . . . . . u2.2 GCD . . . . . . . . . . . . . . 2.2.1 Propiedades de GCD . 2.2.2 Teorema de GCD . . . 2.2.3 Algoritmo de GCD . . com´ n divisor). u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 1 2 3 4 4 4 6 6 6 7 9

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. .. . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3 Factorizaci´n de enteros o 3.1 Enteros relativamente primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Factorizaci´n unica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o ´ 4 Pollard Rho 4.1 Algoritmo de Pollard Rho . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 4.2 Funcionamiento del Algoritmo de Pollard Rho . . . . . . . . . . . . . . . . . . . . 4.3 Implementaci´n del Algoritmo de Pollard Rho en C . . . . . . . . . . . . . . . . o 5 Conclusi´n o

i

1

Introducci´n o

Para tener mejor comprensi´n del funcionamiento de la factorizaci´n de enteros es necesario o o conocer algunas definiciones y teoremas dearitm´tica. 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 o u ´ 1 y a , cualquier otro n´mero entero es denominado n´mero compuesto; el 1 es considerado como u u unidad, esto quiere decir que no es ni primo nicompuesto, de igual manera el 0 y los enteros negativos no son considerados como primos o compuestos.

2
2.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 a y tambien es divisor de b, entonces o u d es un comun divisor de a y b. Para cualquier par de enteros y, x se cumple que: si d|a y d|b entonces d|(a + b) yd|(a − b) (a) De manera mas general tenemos que si: d|a y d|b entonces d|(ax + by) (b) para cualquier entero x y y. a|b, entonces ya sea |a| 0, y b > 0 entonces gcd(a, b) es el elemento positivo de menor valor del conjunto ax + by : x, y ∈ Z de combinaciones lineales de a y b. Demostraci´n 2.1 Sea s el elemento positivo de menor valor de la combinaci´n lineal de a y o o b, y sea s = ax + by paraalg´n x, y Z. Sea q = [a/s] . Dada la ecuaci´n (3), se tiene que: u o a mod s = a − qs a mod s = a − q(ax + by) a mod s = a(1 − qx) + b(−qy) y as´ a mod s es una combinaci´n lineal de a y tambi´n de b. Como 0 = s. la ecuaci´n (b) indica que u o gcd(a, b)|s, dado que gcd(a, b) divide a y b, y s es una combinaci´n lineal de a y b. o Gcd(a, b)|s y s > 0 entonces gcd(a, b) = s y gcd(a, b) b1 (los otroscasos ser´ ıan parecidos). Dividamos ambos productos por 2b1 . A la izquierda queda el factor 2a1 − b1 mientras que a la derecha 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 consiguiente no divide el producto, seg´n el teorema de Euclides). u u Esto es absurdo porque ambos t´rminos son...