Algoritmos

Algoritmos de factorización de enteros

factorización de enteros o factorización de primos consiste en descomponer un número compuesto (no primo) en divisores no triviales, que cuando se multiplican dan el número original.

Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un número de 200 dígitos (RSA-200) tardó 18 meses y consumió más de medio siglo de tiempo de cálculo. Su supuesta dificultad es el núcleo de ciertos algoritmos criptográficos, como el RSA. Muchas áreas de las matemáticas y de las ciencias de la computación, como la teoría algebraica de números, las curvas elípticas o la computación cuántica, están relacionadas con este problema.

Descomponer dos números de igual longitud no tiene por qué tener la misma complicación. Actualmente (2006) se considera que los casos más duros son aquellos para los que los factores son dos números primos, elegidos al azar, de aproximadamente el mismo tamaño.

Descomposición en factores primos

La imagen demuestra la descomposición en primos del número 864. Un método rápido de escribir el resultado en números primos es ${\displaystyle 2^{5}\times 3^{3}}$.

Por el teorema fundamental de la aritmética, cada entero positivo tiene una única descomposición en números primos (factores primos). La mayor parte de los algoritmos de factorización elementales son de propósito general, es decir, permiten descomponer cualquier número introducido, y solo se diferencian sustancialmente en el tiempo de ejecución.

${\displaystyle {\begin{array}{r|l}72&2\\36&2\\18&2\\9&3\\3&3\\1&\end{array}}}$

${\displaystyle 72=2^{3}\cdot 3^{2}\,}$

Factorización de enteros en tiempo polinómico

El problema de factorizar enteros en tiempo polinómico no ha sido aún resuelto en computación clásica. Si alguien lo consiguiera, esto tendría gran interés en el ámbito de la criptografía, ya que muchos criptosistemas dependen de su imposibilidad. En medios académicos, la existencia de tal avance sería una gran noticia; en otros círculos, sería un gran secreto, por razones obvias. Existe, sin embargo, un algoritmo para computación cuántica, propuesto por Peter Shor, capaz de encontrar la factorización de un entero en sus factores primos en tiempo polinomial con error acotado, es decir, de clase BQP. Este descubrimiento disparó el interés en la computación cuántica y ya se han construido algunos computadores cuánticos de unos pocos qubits, capaces de descomponer números pequeños. Se espera que con los tremendos avances de los últimos años, pronto estos sistemas sean capaces de descomponer números suficientemente grandes para quebrantar los múltiples sistemas criptográficos que se basan en esta dificultad de descomposición.

Aplicaciones prácticas

La dureza de este problema, se encuentra en el núcleo de varios sistemas criptográficos importantes. Un algoritmo veloz para la factorización de enteros significaría que el algoritmo de clave pública RSA es inseguro. Algunos sistemas criptográficos, como el algoritmo de clave pública Rabin y el generador de números pseudoaleatorios Blum Blum Shub garantizarían una mejora en su seguridad; cualquier método que logre quebrarlos puede ser utilizado para crear un algoritmo de factorización más veloz; si la factorización de enteros es veloz, éstos se vuelven más duros. En contraste, pueden existir ataques más eficientes al problema RSA, pero no se conoce ninguno.

Un problema duro similar con aplicaciones criptográficas es el problema del logaritmo discreto.

Estado actual

Un equipo en la Agencia Federal Alemana para Seguridad de Tecnología de Información (BSI) sostiene el récord por factorización de semiprimos en la serie propuesta por la Competición de factorización RSA, con patrocinio de RSA Security. El 9 de mayo de 2005, este equipo anunció la factorización de RSA-200, un número de 663 bits, usando la criba general del cuerpo de números.

El mismo equipo más tarde anunció la factorización de RSA-640, un número más pequeño, conteniendo 193 dígitos decimales (640 bits) el 4 de noviembre de 2005.

Ambas factorizaciones requirieron varios meses de tiempo de computadoras, utilizando el poder combinado de 80 CPUs Opteron AMD.

Dificultad y complejidad

Si un número grande, de b bits es el producto de dos primos de aproximadamente el mismo tamaño, no existe algoritmo conocido capaz de factorizarlo en tiempo polinómico. Esto significa que ningún algoritmo conocido puede factorizarlo en tiempo O(b^k), para cualquier constante k. Aunque, existen algoritmos que son más rápidos que O(a^b) para cualquier a mayor que 1. En otras palabras, los mejores algoritmos son súper-polinomiales, pero sub-exponenciales. En particular, el mejor tiempo asintótico de ejecución es el del algoritmo de criba general del cuerpo de números (CGCN), que para un número n es:

${\displaystyle O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}b\right)^{1 \over 3}(\log b)^{2 \over 3}\right)\right)}$

Para una computadora ordinaria, la CGCN es el mejor algoritmo conocido para números grandes. Para una computadora cuántica, en cambio, Peter Shor descubrió en 1994 un algoritmo que lo resuelve en tiempo polinómico. Esto tendría implicaciones importantes en la criptografía, si alguna vez se construyese una computadora cuántica. El algoritmo de Shor solo tarda un tiempo O((log n)³) y ocupa un espacio O(log n). En 2001, la primera computadora cuántica de 7 cubits fue la primera en correr el algoritmo de Shor. Factorizó el número 15.

No se conoce exactamente cuales clases de complejidad contienen el problema de factorización de enteros. Se sabe que su forma de decisión-problema ("¿Tiene N un factor menor que M?") tiene complejidad NP y co-NP. Esto es porque tanto respuestas SI y NO pueden ser comprobadas si se proveen los factores primos junto a sus certificados de primalidad. Se conoce que está en BQP gracias al algoritmo de Shor. Se sospecha que se encuentra fuera de las tres clases de complejidad (P, NP Completo, co-NP Completo). Si fuese posible probar que se encuentra en cualquiera de estas dos últimas, eso implicaría que NP = co-NP. Ese sería un resultado muy sorprendente, y por ello se sospecha ampliamente que la factorización de enteros se encuentra fuera de ambas. Mucha gente ha intentado encontrar algoritmos clásicos de tiempo polinomial para esta, y ha fallado; por esto se sospecha que se encuentra fuera de P. Otro problema en NP pero que no se cree que sea P o NP Completo es el problema de isomorfismo de grafo.

Interesantemente, el problema de decisión "¿es N un número compuesto?" (o lo que es igual: "¿es N un número primo?") parece ser mucho más sencillo que el problema de encontrar los factores enteros en los que se descompone N. En concreto, el primer problema puede ser resuelto en tiempo polinómico (sobre el número n de cifras de N), de acuerdo a un reciente artículo referenciado más adelante. Además, existen varios algoritmos aleatorios que pueden comprobar la primalidad de un número muy rápidamente, si se está dispuesto a aceptar una pequeña posibilidad de error. La facilidad de la prueba de primalidad es una parte crucial del algoritmo RSA, puesto que es necesaria para encontrar números primos grandes.

Algoritmos de factorización

De propósito general

El tiempo de ejecución de un algoritmo de factorización de propósito general depende solamente del tamaño del entero a factorizar. Éste es el tipo de algoritmo usado para factorizar números RSA. La mayoría de algoritmos de factorización de propósito general están basados en el método de congruencia de cuadrados. A continuación se listan algunos de los algoritmos de propósito general más conocidos:

• Algoritmo de Dixon
• Factorización con fracciones continuas
• Criba cuadrática
• Criba racional
• Algoritmo general de criba del cuerpo de números
• Factorización de formas cuadradas de Shanks

De propósito específico

El tiempo de ejecución de un algoritmo de factorización de propósito específico depende de las propiedades de sus factores desconocidos: tamaño, forma especial, etc. Dichos factores cambian de un algoritmo a otro.

• División por tentativa
• Algoritmo rho de Pollard
• Algoritmo p-1 de Pollard
• Algoritmo p+1 de Williams
• Factorización de curva elíptica de Lenstra
• Método de factorización de Fermat
• Método de factorización de Euler
• Algoritmo especial de criba del cuerpo de números

Cómo factorizar enteros gausianos

Un comcepto importante necesario para la factorización de enteros gausianos es la norma. Ésta se define como: N(a+bi) = a² + b².

El producto de la norma de dos enteros gausianos es igual a la norma del producto de estos números como se muestra a continuación:

N(a+bi) N(c+di) = (a² + b²) (c² + d²) = (ac)² + (bd)² + (ad)² + (bc)² = (ac)² - 2abcd + (bd)² + (ad)² + 2abcd + (bc)² = (ac-bd)² + (ad+bc)² = N((ac-bd)+(ad+bc)i) = N(a(c+di) + b(-d+ci)) = N(a(c+di) + bi(c+di)) = N((a+bi) (c+di))

En la penúltima expresión nos valemos de la propiedad i² = -1.

Esto significa que como primer paso para factorizar números gausianos, debemos hallar los factores primos de su norma, así obtenemos las normas de los factores del número original.

El segundo paso consiste en obtener los factores a partir de las normas halladas.

Existen tres casos:

1. El factor primo p de la norma es 2: en este caso los factores primos del entero gausiano pueden ser 1+i o 1-i (hay que probar cuál divide al número).
2. El factor primo p de la norma es múltiplo de 4 más 3: este valor no se puede expresar como suma de dos cuadrados, así que p no es una norma, pero p² sí lo es. Como p² = p² + 0², y no existe una norma prima que divida p², el número p + 0i es un primo gausiano, y deberemos descartar el factor repetido p.
3. El factor primo p de la norma es múltiplo de 4 más 1: este número se puede expresar como suma de dos cuadrados utilizando los métodos explicados en la página de suma de cuadrados. Si p = m² + n², entonces deberemos verificar si m + ni o m − ni son divisores del número gausiano original.

¿Por qué un número que es múltiplo de 4 más 3 no puede expresarse como suma de cuadrados? Esto se debe a que el cuadrado de un número par es múltiplo de 4 y el cuadrado de un número impar es múltiplo de 4 más 1. De esta manera obtenemos:

• par² + par² = múltiplo de 4
• par² + impar² = múltiplo de 4 más 1
• impar² + par² = múltiplo de 4 más 1
• impar² + impar² = múltiplo de 4 más 2

Así que bajo ninguna circunstancia una suma de dos cuadrados puede ser múltiplo de 4 más 3.

Por supuesto el primer paso es mucho más complicado que el segundo. Esto es porque no conocemos métodos eficientes de factorización de números enteros.

Ejemplo: factorizar el entero gausiano 440 − 55i

La norma es 440² + 55² = 196625 = 5 × 5 × 5 × 11 × 11 × 13

Tanto 5 como 13 son múltiplos de 4 más 1 mientras que 11 es múltiplo de 4 más 3. Podemos valernos de 5 = 2² + 1² y 13 = 3² + 2²

Como 11 es un primo gausiano, podemos dividir el número original por 11 y hallamos el cociente 44 − 5i.

Para los tres factores de la norma iguales a 5, deberemos dividir el resultado del paso anterior 44 − 5i por 2−i o 2+i. Obtenemos: 44 − 5i = (2+i)² × (2-i) × (3 − 2i)

Para el factor 13 deberemos dividir el resultado del paso antrerior 3 − 2i por 3 + 2i ó 3 − 2i. Por supuesto solo 3 − 2i divide a 3 − 2i.

La factorización completa es: 440 − 55i = 11 × (2 + i)² × (2 − i) × (3 − 2i).

Expresiones

Para ingresar la parte imaginaria de un entero gausiano podrá utilizar el símbolo i, como por ejemplo en 3+4i.

Además puede entrar expresiones que usen los siguientes operadores, funciones y paréntesis:

• + para suma.
• - para resta.
• * para multiplicación.
• / para división entera (el dividendo debe ser múltiplo del divisor).
• % para módulo (resto de la división).
• ^ para exponenciación (el exponente debe ser real y mayor o igual que cero).
• n!: factorial (n debe ser real y mayor o igual que cero).
• p#: primorial (producto de todos los primos menores o iguales que p).
• F(n): número de Fibonacci F_n.
• L(n): número de Lucas L_n = F_n-1 + F_n+1.
• P(n): particiones irrestrictas (cantidad de descomposiciones de n en sumas de numeros enteros sin tener en cuenta el orden).
• Re(n): parte real de n.
• Im(n): parte imaginaria de n.
• Norm(n): norma de n, equivale a Re(n)² + Im(n)².
• Gcd(m,n): máximo común divisor de estos dos enteros gausianos.
• Modinv(m,n): inverso del valor m módulo n, sólo válido si gcd(m,n)=1.
• Modexp(m,n,r): Calcula mⁿ módulo r (n debe ser real).

Puedes usar el prefijo 0x para números hexadecimales, por ejemplo 0x38 es igual a 56.