sábado, 31 de octubre de 2015

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 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.
\begin{array}{r|l} 72 & 2 \\ 36 & 2 \\ 18 & 2 \\ 9 & 3 \\ 3 & 3 \\ 1 & \end{array}
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 pseudoaleatoriosBlum 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(bk), para cualquier constante k. Aunque, existen algoritmos que son más rápidos que O(ab) 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:
O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\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)3) 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 suscertificados 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, NPCompleto, 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 elproblema 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 algoritmoRSA, 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:

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.



La Factorización se fundamenta en el Teorema de Factorización Única, que afirma que todo entero positivo se puede representar de forma única como producto de factores primos.

Por ejemplo, 42 = 2 x 3 x 7, y no hay ninguna otra factorización de 42 en números primos, salvo en el orden de los factores, que no afecta en la multiplicación por tener la propiedad conmutativa. Por este motivo se enuncia el Teorema como de Factorización Única.
Para descomponer un número en producto de factores primos, procedemos de la siguiente manera:
  1. Escribimos el número a descomponer y a la derecha trazamos una línea vertical.
  2. Buscamos el menor número primo, (2, 3, 5, 7 ...), por el que sea divisible el número. (Aplicamos los criterios de divisibilidad para saber si la división será exacta o no).
  3. Dividimos el número por ese número primo.
  4. Colocamos el divisor (el número primo) en la parte superior derecha y el cociente debajo del primer número.
  5. Repetimos el proceso hasta que en la parte izquierda aparezca un 1, lo que nos indica que la descomposición ha terminado. (Recordar que el número 1 es especial y no se considera primo ni compuesto).

Veamos algunos ejemplos de descomposición factorial
Factorización de 2310Factorización de 3150
  
2310  23150  2
1155  31575  3
385  5525  3
77  7175  5
11  1135  5
1 7  7
1 
  
2310 = 2 x 3 x 5 x 7 x 113150 = 2 x 3 x 3 x 5 x 5 x 7
 3150 = 2 x 32 x 52 x 7












el algoritmo p + 1 de Williams es un algoritmo de factorización de enteros, uno de la familia dealgoritmos de factorización de grupos algebraicos. Fue inventado por Hugh C. Williams en 1982.
Este funciona bien si el número N a ser factorizado contiene uno o más factores primos p tales que
p + 1
es liso, i.e. p + 1 contiene únicamente factores pequeños. Este usa sucesiones de Lucas para realizar la exponenciación en un cuerpo cuadrático.







El algoritmo p − 1 de Pollard es un algoritmo de factorización de enteros en teoría de números, inventado por John Pollard en 1974. Es un algoritmo de propósito especial, lo que significa que es únicamente adecuado para enteros con factores de tipos específicos; es el ejemplo más simple de un algoritmo de factorización de grupos algebráicos.
Los factores que encuentra son aquellos para los que el número que precede el factor, p − 1, es potencia lisa; la observación esencial es que, trabajando en el grupo multiplicativo módulo un número compuesto N, también se trabaja en los grupos multiplicativos módulo todos los factores de N'. La existencia de este algoritmo permite también el concepto de primos fuertes, siendo primos para los cuales p − 1 tiene al menos un factor primo grande. Casi todos los números primos lo suficientemente grandes son fuertes; si un primo usado para propósitos criptográficos resultara ser no fuerte, es mucho más probable que fuera por malicia que a través de un error de generación de números aleatorios.







algoritmo rho de Pollard es un algoritmo especializado de factorización de números enteros. Fue inventado por John Pollard en 1975. Es especialmente efectivo a la hora de factorizar números compuestos que tengan factores pequeños.

Ideas principales

El algoritmo rho se basa en el algoritmo de la liebre y la tortuga y en la observación de que (como ocurre en el problema del cumpleaños) dos números x e y soncongruentes módulo p con probabilidad 0,5 tras haberse elegido aleatoriamente 1,177\sqrt{p} números. Si p es factor de n, el número que se quiere factorizar, entonces 1 < \operatorname{mcd} \left( |x-y|,n \right) \le n, ya que p divide tanto a \left|x-y\right| como a n.
El algoritmo rho emplea pues una función módulo n a modo de generador de una secuencia pseudoaleatoria. Hace funcionar una de las secuencias el doble de rápido que la otra, es decir, por cada iteración de una de las copias de la secuencia, la otra hace dos iteraciones. Sea x el estado actual de una secuencia e y el estado actual de la otra. En cada paso se toma el máximo común divisor (MCD) de |x − y| y n. Si este MCD llega a ser n, entonces finaliza el algoritmo con el resultado de fracaso, ya que esto significa que x = y y, por el algoritmo de la liebre y la tortuga, la secuencia ya ha completado su ciclo y seguir más allá sólo conseguiría repetir trabajo ya realizado.

El algoritmo

Entradas: n, el número que se desea factorizar; y f(x), una función pseudoaleatoria módulo n
Salidas: un factor no trivial de n, o bien un fracaso. (un factor trivial de n es n mismo o 1)
  1. x ← 2, y ← 2; d ← 1
  2. Mientras d = 1:
    1. x ← f(x)
    2. y ← f(f(y))
    3. d ← MCD(|x − y|, n)
  3. Si d = n, devuelve fracaso.
  4. De lo contrario, devuelve d.
Nótese que este algoritmo acabará en fracaso para todo n primo, pero también puede fallar para un n compuesto. En ese caso, se cambia la función f(x) y se intenta de nuevo.

Optimización

En 1980, Richard Brent publicó una versión del algoritmo más rápida. Empleó las mismas ideas fundamentales que Pollard pero un método distinto de detección de ciclos, reemplazando el algoritmo de la liebre y la tortuga por el algoritmo de Brent para la detección de ciclos.
Pollard y Brent introdujeron una mejora adicional. Observaron que si \operatorname{mcd} (a,n) >1, entonces también se cumple que \operatorname{mcd} (ab,n)>1 para cada entero positivo b. En particular, en lugar de computar \operatorname{mcd} (|x-y|,n) en cada paso, basta definir z como el producto de cien términos consecutivos de |x-y| módulo n, para luego computar un solo \operatorname{mcd} (z,n). Se obtiene un importante ahorro de tiempo, ya que se ven reemplazados 100 cálculos de un máximo común divisor por 99 multiplicaciones módulo n y un solo \operatorname{mcd}. A veces se da lugar a un error en el algoritmo al introducir un factor repetido, por ejemplo, cuando n es un cuadrado. Sin embargo, basta con volver atrás al cálculo anterior del \operatorname{mcd}, donde \operatorname{mcd}(z,n)=1, y a partir de ahí volver a usar el algoritmo rho original.

En la práctica

El algoritmo es muy rápido en la factorización de números que tienen factores pequeños. Por ejemplo, en un equipo de trabajo de 3 GHz, el algoritmo original halló el factor 274177 del sexto número de Fermat (18446744073709551617) en 26 milisegundos. Por contra, la variante de Richard Brent halló el mismo factor en sólo 5 milisegundos. Sin embargo, en el caso de un semiprimo del mismo número de cifras (10023859281455311421), el mismo equipo tardó 109 milisegundos en encontrar un factor con el algoritmo original, y 31 con la variante de Richard Brent.
Para f se elige un polinomio con coeficientes enteros. Los más comunes son de la forma
f(x)=x^2+c\hbox{ mod }n,\,c\neq0,-2.
El éxito más relevante del algoritmo rho ha sido la factorización del octavo número de Fermat, realizada por Pollard y Brent. Emplearon la variante de Brent, que halló un factor hasta entonces desconocido. La factorización completa de F8 tardó dos horas en un UNIVAC 1100/42.

Ejemplo

Sea n = 8051 y f(x) = x2 + 1 mód 8051.
ixiyixi − yi|, 8051)
15261
22674741
367787197
97 es un factor no trivial de 8051. Otros valores de c pueden dar lugar al cofactor (83) en lugar de 97.

Complejidad

El algoritmo ofrece un equilibrio entre su tiempo de ejecución y la probabilidad de encontrar un factor.
Si n es producto de dos primos distintos de tamaño similar, al ejecutar el algoritmo en O(n1/4 polylog(n)) iteraciones se obtiene un factor con probabilidad aproximadamente 0,5. (Nótese que ésta es una afirmación heurística, y que sigue abierto un análisis riguroso del algoritmo.)
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)