Algoritmos

algoritmos de factorización de enteros

criba cuadrática (QS del inglés quadratic sieve), es un algoritmo de factorización de enteros y, en la práctica, el segundo método más rápido conocido (después de la criba general del cuerpo de números). Es todavía el más rápido para enteros que tienen 100 o menos dígitos decimales, y es considerado mucho más sencillo que la criba de cuerpos numéricos. Es un algoritmo de factorización de propósito general, lo que significa que su tiempo de ejecución únicamente depende el tamaño del entero a ser factorizado, y no sobre una estructura especial o propiedades. Fue inventado por Carl Pomerance en 1981 como una mejora a la criba lineal de Schroeppel.

Tabla 1: factorización usando la criba cuadrática 


Año	nº de dígitos decimales	cuántas veces más difícil
	factorizados	factorizar un número de 512 bits
1983	71	> 20 millones
1985	80	< 2 millones
1988	90	250.000
1989	100	30.000
1993	120	500
1994	129	100

Estos números son algo escalofriantes. Hoy no es raro ver números de 512 bits usados en sistemas operacionales. Factorizarlos, y por tanto comprometer su seguridad, está bien dentro del rango de posibilidades: un gusano durante un fin de semana en Internet podría hacerlo.

La potencia de computación se mide habitualmente en mips-año: un ordenador de un millón de instrucciones por segundo, funcionando durante un año, o unas 3*10^13 instrucciones. Por convención, una máquina de 1 mips es equivalente al DEC VAX 11/780. Por tanto, un mips-año es un VAX 11/780 funcionando durante un año, o su equivalente

La factorización de un número de 71 dígitos requirió 0.1 mips-años; la factorización de un número de 129 dígitos en 1994 requirió 5000. Este incremento dramático en potencia de cómputo resultó fundamentalmente de la introducción de cómputo distribuido, usando el tiempo inerte de una red de estaciones de trabajo. La factorización de 1983 usó 9.5 horas de CPU en un único Cray X-MP; la factorización de 1994 usó el tiempo muerto de 1600 ordenadores a lo largo del mundo durante unos ocho meses. Los métodos modernos de factorización se prestan a esta clase de implementación distribuida.

El cuadro se hace aún peor. Un nuevo algoritmo de factorización ha tomado el relevo de la criba cuadrática: la criba general de campo numérico. En 1989 los matemáticos te hubiesen dicho que la criba general de campo numérico nunca sería práctica. En 1992 te hubiesen dicho que era práctica, pero sólo más rápida que la criba cuadrática para números mayores que unos 130-150 dígitos. Hoy se sabe que es más ráipda que la criba cuadrática para números bien por debajo de 116 dígitos. La criba general de campo numérico puede factorizar un número de 512 bits más de 10 veces más rápido que la criba cuadrática. El algoritmo necesitaría menos de un año en un Intel Paragon de 1800 nodos. La Tabla 2 da el número de mips-año necesarios para factorizar números de diferentes tamaños, dadas las implementaciones actuales de la criba general de campo numérico.

Tabla 2: Factorización usando la criba general de campo numérico 


Nº de bits	mips-año necesarios
512	30.000
768	2*10^8
1024	3*10^11
1280	1*10^14
1536	3*10^16
2048	3*10^20

Y la criba general de campo numérico aún se está haciendo más veloz. Los matemáticos siguen saliendo con nuevos trucos, nuevas optimizaciones, nuevas técnicas. No hay razón para pensar que esta tendencia no continuará. Un algoritmo relacionado, la criba especial de campo numérico, ya puede factorizar números de una cierta forma - números no usados habitualmente en criptografía - mucho más rápidamente que la criba general de campo numérico para números del mismo tamaño. No es irrazonable suponer que la criba general de campo numérico pueda ser optimizada para correr igual de rápido; es posible que la NSA [Agencia de Seguridad Nacional] ya sepa hacerlo. La Tabla 3 da el número de mips-año requeridos para que esta criba especial de campo numérico factorice números de distintas longitudes.

Tabla 3: Factorización usando la criba especial de campo numérico 


Nº de bits	mips-año necesarios
512	< 200
768	100.000
1024	3*10^7
1280	3*10^9
1536	2*10^11
2048	4*10^14

En un "workshop" [reunión de trabajo] del Instituto Europeo de Seguridad en Sistemas, en 1992, los participantes estuvieron de acuerdo en que un módulo de 1024 bits sería suficiente para seguridad a largo plazo hasta el 2002. Sin embargo, advirtieron: "Aunque los participantes de esta reunión se sienten cualificados en sus áreas respectivas, esta declaración (respecto a la seguridad duradera) debe tomarse con precaución." Este es un buen consejo.

El criptógrafo sabio es ultraconservador cuando elige longitudes de claves públicas. Para determinar durante qué longitud de clave necesita, se mira tanto a la seguridad y vida útil pretendida para la clave como al estado de la tecnología de la factorización. Hoy se necesita un número de 1024 bits para obtener el nivel de seguridad que se tenía con una clave de 512 bits a principios de los ochenta. Si quieres que tus claves permanezcan seguras durante 20 años, 1024 bits es probablemente demasiado poco.

Incluso si tus secretos particulares no valen el esfuerzo necesario para factorizar tu módulo, puedes estar en peligro. Imagina un sistema de banca automatizado que use RSA para su seguridad. Mallory puede aparecer en el juicio y decir: "¿Leyó vd. en el periódico, en 1994, que se rompió RSA-129, y que los números de 512 bits pueden ser factorizados por cualquier organización que pueda gastarse unos cuantos millones de dólares y esperar unos meses? Mi banco usa números de 512 bits para su seguridad, y por cierto, yo no hice esas siete transferencias." Incluso si Mallory miente, el juez probablemente exigirá que el banco lo demuestre.

Antes, dije que hacer predicciones era una tontería. Ahora voy a hacer algunas. La Tabla 3 da mis recomendaciones para longitudes de claves públicas, dependiendo de durante cuánto tiempo necesitas que sea segura. Hay tres longitudes de clave para cada año: una segura contra un individuo, una segura contra una gran corporación, y la tercera segura contra un gran gobierno.

He aquí algunas de las suposiciones de los matemáticos que factorizaron RSA-129:

Creemos que podríamos obtener cien mil máquinas sin esfuerzos superhumanos o no éticos. Esto es, no liberaríamos un gusano o virus por Internet para encontrar recursos para nosotros. Muchas organizaciones tienen varios millares de máquinas cada una en la red. Hacer uso de sus instalaciones requeriría una sabia diplomacia, pero no debería ser imposible. Suponiendo potencia media de 5 mips y un año de tiempo, no es demasiado irrazonable embarcarse en un proyecto que requiere medio millón de mips-año.

El proyecto para factorizar el número de 129 dígitos reunió un total estimado del 0.03% del poder total de computación de Internet, y ni siquiera lo intentaron seriamente. No es descabellado suponer que un proyecto con publicidad pudiese reunir 0.1% de la potencia computacional del mundo durante un año.

Supongamos que un criptoanalista dedicado pudiese echar mano a 10.000 mips-año, una gran empresa pudiese conseguir 10^7 mips-año y que un gran gobierno tuviese 10^9 mips-año. Supongamos asimismo que la potencia de computación crecerá en un factor de diez cada cinco años. Y, finalmente, supongamos que los avances en matemáticas de factorización nos permitiesen factorizar números ordinarios a la velocidad de la criba especial de campo numérico. La Tabla 4 recomienda diferentes longitudes de clave para seguridad a lo largo de diferentes años.

Tabla 4: Tamaño recomendado de claves públicas (en bits). 


Año	contra I	contra C	contra G
1995	768	1280	1536
2000	1024	1280	1536
2005	1280	1536	2048
2010	1280	1536	2048
2015	1536	2048	2048

Recuerde tener en cuenta el valor de la clave. Las claves públicas se usan frecuentemente para asegurar cosas de gran valor durante mucho tiempo: la clave maestra del banco para un sistema de dinero digital, la clave que el gobierno usa para certificar su pasaporte, la clave de firma digital de un notario. Probablemente no vale la pena pasar meses de tiempo de computación para romper la clave privada de un individuo, pero si puedes imprimir tu propio dinero con una clave rota la idea se hace más atractiva. Una clave de 1024 bits es lo bastante grande como para firmar algo que será verificado en una semana, o mes, o incluso unos cuantos años. Pero no te gustaría estar en un juicio dentro de veinte años con un documento firmado digitalmente, y que el contrario demuestre cómo falsificar documentos con la misma firma.

Hacer predicciones más allá del futuro próximo es aún más tonto. ¿Quién sabe qué clases de avances en computación, interconexión y matemáticas sucederán hacha el 2020? No obstante, si miras al cuadro global, en cada década se pueden factorizar números el doble de largos que en la década pasada. Esto nos lleva a la Tabla 5

Tabla 5: Predicciones de factorización a largo plazo.  Tamaño recomendado de claves públicas (en bits). 


Año	Longitud de clave (en bits)
1995	1024
2005	2048
2015	4096
2025	8192
2035	16384
2045	32768

No todo el mundo está de acuerdo con mis recomendaciones. La NSA manda claves de 512 a 1024 bits para su Digital Signature Standard [Estándar de Firma Digital], bastante menos de lo que yo recomiendo para seguridad a largo plazo. PGP tiene una clave RSA de longitud máxima de 1280 bits. Lenstra, el factorizador más exitoso del mundo, rehúsa hacer predicciones a más de diez años vista. Y la Tabla 6 da las recomendaciones de Ron Rivest, originalmente hechas en 1990, que yo considero demasiado optimistas. Aunque su análisis parece bueno sobre el papel, la historia reciente ilustra que las sorpresas son cosa habitual. Tiene sentido elegir las claves para que sean resistentes contra futuras sorpresas.

criba especial del cuerpo de números (en inglés special number field sieve, SNFS) es un algoritmo especializado de factorización de números enteros. La criba (general) del cuerpo de números (GNFS) es una versión generalizada de este algoritmo que trata con números de todo tipo.

Su tiempo de ejecución y complejidad en notación de Landau parece ser:^1 2

${\displaystyle \Theta \left(\exp \left(\left({\frac {32}{9}}n\right)^{\frac {1}{3}}(\log n)^{\frac {2}{3}}\right)\right).}$

La criba especial de cuerpo de números es eficaz para los números de la forma ${\displaystyle re\pm s}$, donde ${\displaystyle r}$ y ${\displaystyle s}$ son pequeños. Se recomienda pues especialmente para descomponer en factores los números de Fermat y los números de Mersenne. NFSNET utilizó la SNFS mucho y de otros para descomponer en factores los números del proyecto de Cunningham.

la criba general de campo numérico, también llamado algoritmo tamiz campo se basa en la aritmética modular para el producto de factores primos algoritmos clásicos más eficientes. Utiliza los pasos para factorizar un número entero n. Se deriva de la campo de número de tamiz especial. Cuando se utiliza la frase "número tamiz campo" sin calificación, se refiere a la criba general de campo numérico.

Esto es una mejora de la criba cuadrática, que factorizar n mediante la búsqueda de números tales que ki ki-ri = n factorizados por completo en un conjunto fijo de pequeños números primos. Luego, con suficientes tales ri - que se llaman regular con respecto a la base elegida de los números primos, utilizando el método de eliminación de Gauss de álgebra lineal podemos elegir los siguientes expositores igual a 0 ó 1 tal que el producto ri es un cuadrado, dicen x. Por otro lado, si el producto ki en el mismo, entonces xy es divisible por n y con la probabilidad de que al menos la mitad da un factor de n encontrando el máximo común divisor de n y xy. En este método, la idea era elegir ki cerca de la raíz cuadrada de n - entonces ri es también el fin de la raíz cuadrada de n y hay suficientes valores normales.

Campo de número de pantalla general opera de la siguiente manera:

• Elegimos dos polinomios irreducibles fyg con una raíz común m mod n - que no sabemos cuál es la mejor manera de elegir los polinomios, pero por lo general esto ocurre mediante la adopción de un grado de un polinomio y teniendo en cuenta el desarrollo de la base de n m donde m es de orden n. El objetivo es obtener los coeficientes de f y g tan pequeño como sea posible - que será del orden de m, mientras que tener pequeños grados D y E de nuestros polinomios.

• Ahora consideramos campos de número de anillos Z y Z en donde R1 y R2 son las raíces de polinomios F y G, y examinar los valores de a y b tal que r = s = bf y bg son regulares en cuanto a los factores básicos elegido. Si ayb son pequeños, r y s serán demasiado, y tenemos una mejor oportunidad para que puedan ser programados al mismo tiempo.

• Al tener suficientes pares, utilizando el método de eliminación de Gauss, podemos obtener los productos de cierta r s y sus plazas correspondientes para que sean simultáneamente. Necesitamos una condición ligeramente más fuerte - si las normas plazas en nuestros números de cuerpo, sino que también podemos obtener esta condición por este método. Cada r es un estándar de a- y b r1, por lo tanto, tenemos que el producto de los factores correspondientes a-r1 b es un cuadrado en Z, con una "raíz cuadrada" que se puede determinar - por lo general se muestra como un número algebraico irracional. Del mismo modo, se obtiene que los factores de productos a- r2 b es un cuadrado en Z, con una "raíz cuadrada", que también puede ser calculada.

• Como m es una raíz de f y g mod n, existen morfismos de los anillos Z y Z en el anillo Z / nZ, que se aplican R1 y R2 m, y estos morfismos aplican cada "raíz cuadrada" en su la representación de la totalidad. Ahora los controladores de producto-mb mod n, podemos obtener un cuadrado de dos maneras - una para cada homomorfismo. Por lo tanto, tenemos dos números x e y con xy divisible por n y de nuevo con la probabilidad de que al menos un medio, se obtiene un factor de n encontrando el máximo común divisor de n y xy

El segundo mejor algoritmo clásico, conocido por factorización de enteros es el método de factoring Lenstra curva elíptica. Es mejor que el número de tamiz campo general cuando los factores son pequeñas, ya que funciona mediante la búsqueda de los valores regulares del orden del divisor primo más pequeño de n, su tiempo de ejecución depende del tamaño de la divisor.

 criba general del cuerpo de números (del inglés general number field sieve (GNFS) es el más eficiente algoritmo clásico conocido para factorizar enteros mayores de 100 dígitos. Heurísticamente, su complejidad para factorizar un entero n (consistente en log₂ n bits) es de la forma

${\displaystyle \exp \left(\left({\sqrt[{3}]{\frac {64}{9}}}+o(1)\right)(\ln n)^{\frac {1}{3}}(\ln \ln n)^{\frac {2}{3}}\right)=L_{n}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {64}{9}}}\right]}$

(en notación L), donde ln es el logaritmo en base e.¹ Es una generalización de la criba especial del cuerpo de números: mientras que el último puede factorizar únicamente números de una cierta forma especial, la criba general del cuerpo de números puede factorizar cualquier número aparte de potencias primas (que es trivial factorizar tomando raíces). Cuando el término en inglés number field sieve (NFS) es usado sin calificación, este se refiere a la criba general del cuerpo de números.

El principio de la criba del cuerpo de números (ambas, especial y general) se puede entender como una mejora de la más simple criba racional o criba cuadrática. Cuando se usan tales algoritmos para factorizar un número grande n, es necesaria la búsqueda de números lisos (i.e. números con factores primos pequeños) de orden n^1/2. El tamaño de esos valores es exponencial en el tamaño de n (véase después). La criba general del cuerpo de números, por otra parte, gestiona la búsqueda de números lisos que sean subexponenciales en el tamaño de n. Puesto que esos números son más pequeños, son más propensos a ser lisos que los números evaluados en los algoritmos anteriores. Esta es la clave de la eficiencia de la criba del cuerpo de números. Con el fin de lograr esta aceleración, la criba del cuerpo de números tiene que realizar los cálculos y factorizaciones en cuerpos numéricos. Esto resulta en muchos aspectos lo más complicado del algoritmo, si lo comparamos con la más simple criba racional.

Nótese que log₂ n es el número de bits en la representación binaria del n, que es el tamaño de la entrada para el algoritmo, así que cualquier elemento de orden n^c para una constante c es exponencial en log n. El tiempo de ejecución de la la criba del cuerpo de números es super-polinomial pero sub-exponencial en el tamaño de la entrada.