Método de factorización de Fermat

Método de factorización de Fermat

El método de factorización de Fermat se basa en la representación de un número natural impar como la diferencia de dos cuadrados:

n = a2b2.

Esa diferencia se puede factorizar algebraicamente como (a + b)(ab); si ninguno de esos factores es igual a 1, se trata de una factorización propia de n.

Todo número impar se puede representar de esta manera. En efecto, si n = cd es una factorización de n, entonces

n = \left(\frac{c+d}{2}\right)^2 - \left(\frac{c-d}{2}\right)^2

Como n es impar, c y d también son impares, por lo que su semisuma y semidiferencia son ambos enteros. (Un múltiplo de cuatro también es una diferencia de cuadrados: en ese caso se pueden plantear c y d como números pares.)

En su forma más simple, el método de Fermat puede ser incluso más lento que el de división por tentativa en el peor de los casos. Sin embargo, la combinación de división por tentativa y el método de Fermat es más efectivo que el uso exclusivo de uno de ellos.

Contenido

Método básico

Se van tomando varios valores de a, con la esperanza de que a2n = b2 sea un cuadrado.

Factor_Fermat(N): // N debería ser impar
A ← techo(raízcuad(N)) // "Techo" indica el entero inmediatamente superior al número que hay dentro.
Bcuad ← A*A - N
mientras Bcuad no sea un cuadrado:
A ← A + 1
Bcuad ← A*A - N // alternativamente: Bcuad ← Bcuad + 2*A + 1
fin_del_mientras
devuelve A - raízcuad(Bcuad) // o A + raízcuad(Bcuad)

Por ejemplo, para factorizar N = 5959, se procede así:

A: 78 79 80
Bcuad: 125 282 441

El tercer intento produce un cuadrado. A = 80, B = 21, y los factores son AB = 59 y A + B = 101.

Si n tiene más de dos factores primos, este procedimiento primero encuentra la factorización con el menor valor de a y b. Es decir, a + b es el menor factor mayor o igual que la raíz cuadrada de n. Por tanto, a-b = \frac{N}{a+b} es el mayor factor menor o igual que \sqrt{n}. Si el procedimiento devuelve n = 1 \cdot n, entonces n debe ser primo.

Para n = cd, sea c el mayor factor menor que la raíz. a = \frac{c+d}{2}, por tanto, el número de pasos requeridos es aproximadamente \frac{c+d}{2} - \sqrt n = \frac{\left(\sqrt d - \sqrt c\right)^2}{2} = \frac{(\sqrt n - c)^2}{2c}.

Si n es primo (es decir, c = 1), ¡hacen falta O(n) pasos! Esta es desde luego una mala forma de demostrar la primalidad de un número. Pero si n tiene un factor próximo a su raíz cuadrada, el método funciona rápidamente. Concretamente, si c difiere de \sqrt n en menos de {\left(4n\right)}^{1/4}, entonces el método sólo necesita un paso, y esto es independiente del tamaño de n.

Fermat y división por tentativa

Intentemos factorizar el número primo n=2345678917, pero también calcular b y a-b. Empezando por \sqrt{N} y subiendo desde ahí, quedan así tabulados los datos:

A: 48433 48434 48435 48436
Bcuad: 76572 173439 270308 367179
B: 276,7 416,5 519,9 605,9
A-B: 48156,3 48017,5 47915,1 47830,1

En la práctica, se puede ignorar la última fila hasta que b sea un número entero. Pero cabe observar que si n tuviera un factor menor que su raíz pero mayor que AB = 47830,1, el método de Fermat ya lo habría encontrado.

La división por tentativa normalmente tendría que seguir hasta el mayor primo menor que 48432; pero tras sólo cuatro pasos con el método de Fermat, basta intentarlo hasta 47830 para encontrar un factor o determinar la primalidad.

Esto sugiere la implementación de un método que combine los ya descritos. Basta tomar una cota c > \sqrt{n} y usar Fermat para los factores comprendidos entre \sqrt{n} y c. Esto deja una cota para la división por tentativa de c - \sqrt{c^2 - n}. En el ejemplo anterior, con c = 48436 la cota para la división por tentativa es 47830. Otra opción razonable sería c = 55000, que deja una cota de 28937.

Siguiendo con el método de Fermat, se obtiene un rendimiento cada vez menor. Así, normalmente uno pararía antes de llegar a este punto:

A: 60001 60002
Bcuad: 1254441084 1254561087
B: 35418,1 35419,8
A-B: 24582,9 24582,2

Mejorar la criba

No es necesario computar todas las raíces cuadradas de los a2n, ni siquiera todos los valores de a. Por ejemplo, aquí se presenta de nuevo la tabla para n = 2345678917:

A: 48433 48434 48435 48436
Bcuad: 76572 173439 270308 367179
B: 276,7 416,5 519,9 605,9

Se puede ver rápidamente que ninguno de estos valores de Bcuad es un cuadrado. Los cuadrados son congruentes con 0, 1, 4, 5, 9 ó 16 módulo 20. Los valores se repiten con cada aumento de a en 10 unidades. En este ejemplo, a2n produce 3, 4, 7, 8, 12 y 19 módulo 20 para estos valores. De ahí se deduce que sólo el 4 de esta lista puede corresponder a un cuadrado. Por tanto, a2 debe ser 1 mód 20, lo que implica que a es 1 ó 9 mód 10; esto dará lugar a un Bcuad congruente con 4 mód 20, y si Bcuad es cuadrado, b acabará en 2 u 8 mód 10.

Este proceso se puede realizar con cualquier módulo. Con el mismo n = 2345678917,

módulo 16: Los cuadrados son 0, 1, 4 ó 9
n mód 16 es 5
así que a2 sólo puede ser 9
y a debe ser 3 ó 5 módulo 16
módulo 9: Los cuadrados son 0, 1, 4 ó 7
n mód 9 es 7
así que a2 sólo puede ser 7
y a debe ser 4 ó 5 módulo 9

Generalmente se toma una potencia de un primo distinto para cada módulo.

Dada una sucesión de valores de a (inicial, final y el "paso") y un módulo, se puede proceder así:

Criba_Fermat(N, Aini, Afin, Apaso, Módulo)
A ← Aini
hacer Módulo veces:
Bcuad ← A*A - N
si Bcuad es cuadrado, módulo Módulo:
Criba_Fermat(N, A, Afin, Apaso * Módulo, Siguiente_Módulo)
fin si
A ← A + Apaso
fin hacer

Pero se puede detener la recursión cuando quedan pocos valores de a, es decir, cuando (Afin-Aini)/Apaso es pequeño. Además, como el tamaño del paso de a' es constante, se pueden computar los sucesivos Bcuad mediante sumas.

Mejoras por uso de multiplicador

El método de Fermat funciona de forma óptima cuando hay un factor cercano a la raíz cuadrada de n. A lo mejor se puede favorecer que así sea.

Si se conoce la razón aproximada de dos factores (\tfrac{d}{c}), entonces se puede escoger un número racional \tfrac{v}{u} próximo a ese valor. nuv = cv \cdot du, quedando dos factores próximos que el método de Fermat, aplicado a nuv, hallará rápidamente. Entonces mcd(n,cv) = c y mcd(n,du) = d. (A menos que c divida a u o d divida a v.)

En general, no se conoce esa razón, pero se puede probar con diversos valores \tfrac{u}{v}, y tratar de factorizar cada nuv que surja. R. Lehman ideó una forma sistemática de hacer esto, de forma que la combinación de Fermat y la división por tentativa factorice n en O(n1 / 3).[1]

Otras mejoras

La idea fundamental del método de Fermat es la base de la criba cuadrática y la criba generalizada sobre el cuerpo de los números (general number field sieve), los algoritmos mejor conocidos para la factorización de semiprimos grandes "en el peor de los casos". La principal mejora de la criba cuadrática sobre la factorización de Fermat es que, en lugar de buscar un cuadrado en la sucesión de a2n, lo que hace es hallar un subconjunto de elementos de esta sucesión cuyo producto es un cuadrado, y lo hace de forma muy eficiente. El resultado final es el mismo: una diferencia de cuadrados mód n que, si no es trivial, puede emplearse para factorizar n.[2]

Referencias

  1. Véase R. Lehman, "Factoring Large Integers", Mathematics of Computation, 28:637-646, 1974. (en inglés)
  2. Véase también J. McKee, "Speeding Fermat's factoring method", Mathematics of Computation, 68:1729-1737 (1999). (en inglés)

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Método de factorización de Euler — El método de factorización de Euler es un método de factorización basado en la representación de un entero positivo N como la suma de dos cuadrados de dos maneras distintas: N = a2 + b2 = c2 + d2 Aunque la factorización algebraica de números… …   Wikipedia Español

  • Factorización de enteros — Saltar a navegación, búsqueda En teoría de números, el problema de la factorización de enteros consiste en encontrar un divisor no trivial de un número compuesto; Por ejemplo dado el número 91, el reto es encontrar un número tal como el 7 que lo… …   Wikipedia Español

  • RSA — En criptografía, RSA (Rivest, Shamir y Adleman) es un sistema criptográfico de clave pública desarrollado en 1977. Es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente. La seguridad de… …   Wikipedia Español

  • Números compuestos — Saltar a navegación, búsqueda Todo número natural no primo, a excepción del 1, se denomina compuesto, es decir, tiene uno o más divisores distintos a 1 y a sí mismo. Los 20 primeros números compuestos son: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20,… …   Wikipedia Español

  • Número compuesto — Todo número natural no primo, a excepción del 1, se denomina compuesto, es decir, tiene uno o más divisores distintos a 1 y a sí mismo. También se utiliza el término divisible para referirse estos números. Los 20 primeros números compuestos son:… …   Wikipedia Español

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Teoría de números — Nuestra teoría de números se deriva de la antigua aritmética griega de Diofanto.[1] Portada de la aritmética de Diofanto traducida al latín por Bachet de Méziriac, edición con comentarios de Pierre de Fermat publicada en 1670 …   Wikipedia Español

  • Algoritmo rho de Pollard — Para otros usos de este término, véase algoritmo rho de Pollard para logaritmos discretos. El algoritmo rho de Pollard es un algoritmo especializado de factorización de números enteros. Fue inventado por John Pollard en 1975. Es especialmente… …   Wikipedia Español

  • Teorema fundamental de la aritmética — En matemática, y particularmente en la teoría de números, el teorema fundamental de la Aritmética o teorema de factorización única afirma que todo entero positivo se puede representar de forma única como producto de factores primos. Por ejemplo,… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”