criptografía - algoritmos criptográficos

 factorización con fracciones continuas (CFRAC del inglés Continued Fraction Factorization Method ) es un algoritmo de factorización de enteros. Es un algoritmo de propósito general, lo que significa que es apropiado para factorizar cualquier entero n, no dependiente de una forma espacial o de propiedades. Fue descrito por D. H. Lehmer y R. E. Powers en 1931,¹ y desarrollado como un algoritmo de computadora por Michael A. Morrison y John Brillhart en 1975.²

El método de fracciones continuas está basado sobre el método de factorización de Dixon. Este usa convergentes en las expansiones de fracciones continuas regulares de

.

Puesto que es un irracional cuadrático, la fracción continua debe de ser periódica (a no ser que n sea un cuadrado, en cuyo caso la factorización es obvia).

Este tiene un tiempo de complejidad , en las notaciones O y L repectivamente.

donde a₀ es un entero y todos los demás números a_i son enteros positivos, para i= 0, 1, 2,...n,....Los números a₀, a₁, a₂,..., a_s se llaman elementos o cocientes incompletos.³ Si se permite que los numeradores o los denominadores parciales tomen valores arbitrarios, que podrían ser funciones en algún contexto, la expresión resultante es una fracción continua generalizada. Cuando fuera necesario distinguir la forma típica de arriba de una generalizada aquella se denominará fracción continua regular o simple.

El motivo del estudio de las fracciones continuas es el deseo de dar una representación «matemáticamente pura» de los números reales. Estamos familiarizados con larepresentación decimal:

donde a₀ puede ser cualquier entero y los otros a_i pertenecen a {0, 1, 2, …, 9}. Así el número , por ejemplo, se representa con la sucesión (3, 1, 4, 1, 5, 9, 2, …).

Esta representación tiene algunos problemas. Por ejemplo, la constante 10 se usa porque los cálculos se hacen en el sistema decimal; bien podría usarse el octal o el binario. Otro problema es que muchos racionales no tienen representación finita; por ejemplo, 1/3 lo hace con la sucesión infinita (0, 3, 3, …).

La representación en fracción continua de los números reales evita ambos problemas. Por ejemplo, consideremos el número 415/93, que vale aproximadamente 4.4624. Esto es aproximadamente 4, pero es algo mayor que 4, sobre 4+1/2. Pero el denominador 2 no es correcto; lo sería uno algo mayor, sobre 2+1/6, ya que 415/93 es aproximadamente 4+1/(2+1/6). Pero el denominador 6 no es correcto; lo sería uno algo mayor, sobre 4+1/(2+1/(6+1/7)). Esto es exacto. Quitando las partes redundantes de la expresión 4+1/(2+1/(6+1/7)), se obtiene su notación abreviada [4; 2, 6, 7].

Así, puede representarse en fracción continua cualquier número real, y se cumplen estas cómodas propiedades:

• La representación en fracción continua de un número real es finita si y solo si ese número es racional.
• La representación en fracción continua de un racional «simple» es generalmente corta.
• La representación en fracción continua de un racional es única siempre que no acabe en 1. (de hecho: [a₀; a₁,... a_n, 1] = [a₀; a₁,... a_n + 1].)
• Los términos de una fracción continua se repetirán si y solo si representa a un irracional cuadrático, es decir, si es solución de una ecuación cuadrática con coeficientes enteros. Por ejemplo, la fracción continua [1; 1, 1,... ] representa al número áureo y [1; 2, 2, 2, … ] a .
• El truncado de la representación en fracción continua de un número x da una aproximación racional que es, en cierto sentido, la «mejor posible» (véanse los teoremas 6 y 7, más abajo, para una formalización de este aserto).

La última propiedad, falsa si empleáramos la representación convencional, es muy importante. Si truncamos una representación decimal, obtenemos una aproximación racional, pero habitualmente no la mejor. Por ejemplo, truncando 1/7=0.142857… en varios sitios obtendremos aproximaciones como 142/1000, 14/100 o 1/10. Pero es claro que el mejor racional que aproxima a 1/7 es el propio 1/7. Si truncamos la representación decimal de π obtendremos aproximaciones como 31415/10000 o 314/100. La representación en fracción continua de π comienza con [3; 7, 15, 1, 292,.. ]. Si truncamos esta representación obtendremos las excelentes aproximaciones: 3, 22/7, 333/106, 355/113, 103993/33102, … Los denominadores de 314/100 y 333/106 son casi iguales pero el error en la aproximación de 314/100 es nueve veces mayor que el de 333/106, así como la aproximación a π con [3; 7, 15, 1] es 100 veces más precisa que 3.1416.

factorización de curva elíptica de Lenstra o método de factorización de curva elíptica ( del inglés elliptic curve factorization method, ECM) es un rápido algoritmo detiempo de ejecución sub-exponencial para la factorización de enteros que emplea curvas elípticas. Para una factorización de propósito general, ECM es el tercer método más rápido conocido de factorización. El segundo más rápido es la criba cuadrática de múltiples polinomios y el más rápido es la criba general del cuerpo de números. La factorización de curva elíptica de Lenstra es llamada así en honor a Hendrik Lenstra.

Prácticamente hablando, ECM es considerado un algoritmo de factorización de propósito especial así como el más adecuado para encontrar factores pequeños. A fecha de 2012, es todavía el mejor algoritmo para divisores que no superen los 20 a 25 dígitos decimales (64 a 83 bits respectivamente), así como su tiempo de ejecución está dominado por el tamaño del factor más pequeño p en lugar de por el tamaño del número n a ser factorizado. Frecuentemente, ECM se usa para eliminar factores pequeños de un entero muy grande con muchos factores; si el entero resultante todavía es compuesto, entonces solo tiene factores grandes y es factorizado mediante el uso de técnicas de propósito general. El factor más grande encontrado usando ECM cuenta con 75 dígitos y fue descubierto el 2 de agosto de 2012 por Samuel Wagstaff.¹ Incrementando el número de curvas probadas se mejoran las posibilidades de encontrar un factor, pero no son lineales con el incremento en el número de dígitos.