Métodos de factorización

La problemática que trasciende a esta actividad es el tiempo de solución del problema, lo deseable sería encontrar un método que ofreciese el resultado en tiempo polinómico, desafortunadamente ningún algoritmo conocido puede factorizar en tiempo O(b^k), para cualquier constante k. Los algoritmos más rápidos superan al tiempo polinomial y no llegan a ser exponenciales. En la actualidad (2.015), el menor tiempo de ejecución es el de la criba general de campos (cuerpo) númericos (CGCN) y General number field sieve (GNFS).

 

Estos métodos tienen una importancia extrema en la sociedad tecnológica actual, la más conocida es su aplicación en herramientas y sistemas de cifrado, por ejemplo en RSA. Tampoco debemos olvidar que se está investigando la capacidad de las redes neuronales artificiales (RNA) en un intento de resolver el problema, Boris Jansen y Kenji Nakayama publicaron un trabajo interesante a este respecto. También existen trabajos utilizando las FHNN (Fuzzy Hopfield Neural Networks) como generadoras de números seudo aleatorios que se podrían utilizar en el método Dixon o en cualquier otro.

 

Los métodos de factorización se dividen en dos grupos:

 

• De propósito específico. El tiempo de respuesta depende de las propiedades de los factores desconocidos: tamaño, forma especial, etc. Algunos de ellos son:
  • División por tentativa.
  • Atkin
  • Fermat
  • rho y p-1 de Pollard,
  • p+1 de Williams,
  • Curva elíptica de Lenstra, ECM
  • Euler
  • Criba especial de campos numéricos
• De propósito general. El tiempo de respuesta de estos algoritmos depende solamente del tamaño del entero, están basados en el método de congruencia de cuadrados. Algunos de estos algoritmos son:
  • Dixon
  • Fracciones continuas
  • Criba cuadrática
  • Criba general de campos numéricos
  • Formas cuadradas de Shanks. SQUFOF

 

División por tentativa o por divisiones sucesivas. Este es el algoritmo de factorización más sencillo y el más antiguo, se trata de dividir n entre todo número primo menor o igual a √n. Sí el algoritmo no encuentra ningún factor, es una prueba de que n es primo. El proceso es el siguiente:

 

• Tenemos un entero n. (5.940)
• Tomamos la sucesión de los valores primos (p).
• Realizamos la división de n entre la sucesión de primos (Comenzamos con el 2).
• Cada vez que se encuentra un primo p que divide a n (guardamos p), cambiamos n por n/p y volvemos a iniciar el proceso a partir de ese primo.
• Sí llegamos a √n y no se ha encontrado ningún primo que divida a n , n es un número primo y terminamos.
• Al llegar a 1 tenemos la factorización completada.

Siempre que n no sea primo es un método muy rápido, la inmensa mayoría de los enteros tienen un factor inferior a 1.000, esta propiedad hace que otros algoritmos comiencen utilizando este y después continúen con el suyo. Desde un punto de vista computacional es el más costoso. Es un método válido para n < ± 10⁷, a partir de este número decrece el rendimiento rápidamente y el tiempo de ejecución crece de forma exponencial, este incremento es la peor noticia.

 

 

Fermat. Lo desarrolló Pierre Fermat y después fue mejorado por Gauss. El número a factorizar debe cumplir unos requisitos previos. Se basa en la idea de factorizar un número n que es la diferencia de dos cuadrados donde uno de ellos es pequeño.

n = x² – y²

 

si n es la diferencia de cuadrados, también se puede expresar como el producto de la suma por la diferencia de esos números.

n = (x + y) (x – y) donde x ≥ y > 0

 

Ahora debemos encontrar un ejemplo x e y (proposición de Maurice Kraitchik).

 

1. De n = (x + y) (x – y) vemos que x es mayor que y, en caso contrario n sería negativo y no puede ser.
2. Por tanto, también que x es mayor que √n
3. Probamos los valores de x a partir de √n + 1 hasta que encontremos uno que cumpla con n – x² = y²

Como ejemplo tomamos el nº 1.585.361

 

Iniciamos x = (√1.585.361) + 1 = 1.260 (Tomamos sólo la parte entera de la raíz).

 

√(x² – n )

1.260 → 47,31807265728392
1.261 → 68,99275324264136
1.262 → 85,34049449118513
1.263 → 99,03534722511958
1.264 → 111,06304515904469
1.265 → 121,91800523302537

………

1.428 → 673,6638627683691
1.429 → 675,7810296242416
1.430 → 677,.8930594127661
1.431 → 680,0 encontrado n =1.431² – 680² = (1.431+ 680 ) × (1.431- 680) = 2.111 × 751 = 1.585.361

 

 

 

Atkin.  Es una versión optimizada de la criba de Eratóstenes que permite encontrar todos los números primos hasta un número entero dado. Fue desarrollado en 2.003 por Arthur O. L. Atkin y Daniel J. Bernstein. Fundamentalmente marca los múltiplos de cuadrados de números primos, mejorando de esta forma la complejidad asintótica teórica con complejidad de O(N/log log N).

 

 

 

Pollard. John M. Pollard desarrolla dos métodos en la década de 1.970, el primero denominado rho que es mejorado por R. P .Brent. Posteriormente, durante los años 1.974-5, desarrolla el método ρ, éste permite factorizar eficientemente números compuestos menores que 10¹² y se basa en el pequeño teorema de Fermat. Los dos tienen complejidad exponencial, un obstáculo para factorizar números relativamente grandes.

Tiempos teóricos de ejecución:

Para p-1 O ( q ), donde q es el factor primo más grande de p-1 y p es el factor primo más grande de n.

Para rho O (√ p ), donde p es el factor primo más grande de n.

 

Descripción de los algoritmos:

 

 

 

 

Factorización de Curva Elíptica. (ECM – Elliptic Curve Method-)

V. Miller en 1.985 y N. Koblitz en 1.987, propusieron de forma independiente, utilizar el problema del logaritmo discreto (PLD) en el grupo de puntos de una curva elíptica definida sobre un cuerpo finito en lugar de en el grupo multiplicativo de tal cuerpo. La toma de esta decisión es que tal grupo de puntos resulta inmune a ataques criptoanalíticos lo que permite una seguridad equivalente con longitudes de clave menores. Esta aplicación en la criptografía hizo que la idea se utilizase como un método de factorización por Hendrik W. Lenstra hijo (1.987) y como prueba para nº primos por A.O.L. Atkins y F. Morain, en 1.993, S. Goldwaser y J. Kilian en 1996 .

 

Este método en parte es similar al método p-1 de Pollard. Está considerado como un algoritmo adecuado para encontrar factores pequeños, su tiempo de ejecución depende del tamaño del factor más pequeño en lugar de por el tamaño del número factorizar, actualmente es el mejor algoritmo para divisores que no superen los 30 dígitos.

 

 

Fracciones continuas. (Continued Fraction Factoring Algorithm – CFRAC- ).

Este método fue descrito por Derrick Henry Lehmer y Ralph Ernest Powers en 1.931 basándose en los trabajos de Maurice Kraitchik en la década de 1.920. Fue desarrollado por Michael A. Morrison y John Brillhart en 1.970 y mejorado en 1.981 por John D. Dixon.

 

Morrison y Brillhart consiguieron con su método factorizar el séptimo número de Fermat en un computador IBM 360/91:

 

F7 = (a¹²⁸) + 1 = 59649589127497217 × 5704689200685129054721

 

En 1.987 Kathy J. McKurdy y Marvin C. Wunderlich utilizando sistemas de proceso paralelo masivo (MPP) con computadores VAX obtuvieron los siguientes resultados:

 

Número	Dígitos	Horas totales
2299 -1	60	10,9
2405 -1	60	11,5
5171 +1	62	14,5

 

Tiene una de complejidad de:

 

 

Dixon.

Escrito por John D. Dixon en 1.981 y basado en las ideas de Maurice Kraitchik. Es una versión modificada del método de Fermat para procesos computacionales en paralelo. Cada procesador puede trabajar con su propio número r aleatorio. Este algoritmo es probabilístico, no existe garantía de obtener un factor de n, pero es capaz de encontrar factores muy grandes en tiempo inferior al de otros. No es utilizado en la practica por su lentitud.

Recordando la idea de Fermat, n = x² – y², visto de otra forma x² = y² (mod n), desde ésta forma tenemos alta probabilidad de que el máximo común divisor mcd(X – Y, n) sea un divisor de n. La parte costosa de este método es conseguir los dos cuadrados

 

1. Elegimos un número al azar r, mejor de esta forma r = √n + k, para k = 1, 2, 3, …
2. Factorizamos para identificar si r es un cuadrado.
3. Si es cuadrado, su raíz cuadrada puede ser diferente de r² .
4. Si la raíz es diferente de r², tenemos dos números cuyos cuadrados son congruentes mod n.

Tiene una de complejidad de:

 

 

Formas cuadráticas. (Square Forme Factorization – SQUFOF-). Daniel Shanks “Dan”, alrededor de 1.975 desarrolla la factorización de formas cuadradas como una mejora del método de Fermat. La base matemática del algoritmo son las formas cuadráticas de Gauss, aunque también puede ser expresada como fracciones continuas.

 

Código SQUFOF en java, derivado de la publicación de Jason E. Gower y Samuel S. Wagstaff hijo en 2.007,

 

 

El algoritmo de Shanks expande la fracción continua de la raíz cuadrada de n, siendo el número factorizado, buscando entre los convergentes una forma cuadrática que es un cuadrado perfecto; en esto, difiere del algoritmo CFRAC, que combina múltiples convergentes para montar un cuadrado perfecto. Copiamos el algoritmo del papel de Jason Gower y Sam Wagstaff que proporciona la descripción estándar de SQUFOF: Tiene una de complejidad de: O ( ⁴√ n )

 

 

 

Criba cuadrática. ( Quadratic sieve – QS)

Actualmente es el algoritmo más rápido en factorizar números hasta ≈ 100 dígitos. Lo desarrolla Carl Pomerance en 1.981 basándose en la criba lineal de Richard Schroeppel y de las ideas de Dixon y Kraitchik. Su tiempo de ejecución depende del tamaño del número a factorizar.

La idea básica es la siguiente:

Si n es el número a factorizar, el algoritmo intenta encontrar dos números x e y tal que x² ≡ y² (mod n), esto es (x – y) × (x + y) ≡ 0 (mod n), por lo tanto x – y deberá de ser un factor de n

 

 

Criba general de campos numéricos (CGCN). 

Es creado por John M. Pollard en 1.988 y desarrollado en 1.994 por J.P. Buhler, H.W. Lenstra hijo y Carl Pomerance. Su principio se basa en una mejora de la criba cuadrática y en estos momentos es el algoritmo más eficiente para factorizar enteros mayores de 100 dígitos. Par entender cómo funciona se deberían tener conocimientos de campos de números algebraicos, la teoría de Galois, teoría grupal y otros que se mostrarán posteriormente.

 

Tiene una de complejidad de: