criptografía - algoritmos criptográficos

 factorización de formas cuadradas de Shanks es un método para factorizar enteros inventado por Daniel Shanks como una mejora del método de factorización de Fermat.

El éxito del método de depende de encontrar números enteros  e  tales que , donde  es el entero a ser factorizado. Una mejora (indicada por Kraitchik) es buscar enteros  e  tales que . Encontrando un par adecuado  no se garantiza una factorización de , pero esto implica que  es un factor de , y hay una buena posibilidad de que los divisores primos de  estén distribuidos entre esos dos factores, así que el cálculo del máximo común divisor de  y  dará un factor no trivial de .

Una algoritmo práctico para encontrar pares  que satisfagan  fue desarrollado por Shanks, que lo llamó Factorización de formas cuadradas (en inglés Square Forms Factorization o SQUFOF). El algoritmo puede ser expresado en términos de fracciones continuas, o en términos de formas cuadráticas.A pesar de que ahora existen métodos de factorización más eficientes disponibles, SQUFOF tiene la ventaja de que es lo suficientemente pequeño para ser implementado en una calculadora programable.

Descripción del Problema

Dado un número N determinar descomponer N en sus factores primos.

Detalles del Problema

La 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. 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.

Algoritmos que lo solucionan

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
• Criba general 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
• Criba especial del cuerpo de números

Análisis de tiempo de los algoritmos que lo solucionan

El problema de factorizar enteros en tiempo polinómico no ha sido aún resuelto. 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.

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:

método de factorización de Dixon (conocido también como método de los cuadrados aleatorios de Dixon¹ o algoritmo de Dixon) es unalgoritmo general de factorización de enteros; es el método prototípico de factor base, y el único método de factor base para el cual los límites de ejecución no se basan en conjeturas sobre las propiedades de suavidad de los valores de un polinomio conocido.

El algoritmo fue diseñado por John D. Dixon, un matemático de la universidad de Carleton, y fue publicado en 1981.

Con el fin de encontrar números enteros  y de tal manera que

(1)

(Una forma modificada del método de factorización de Fermat ), en cuyo caso existe una probabilidad del 50% que es un factor de de , elegir un azar entero  , calcular

(2)

y tratar de factorizar . Si no es fácilmente factorizable (hasta algún pequeño divisor juicio ), pruebe con otro . En la práctica, el juicio s se toman generalmente para ser , con , 2, ..., que permite la criba cuadrática método de factorización que se utilizará. Continuar la búsqueda y factoring s hasta que se encuentran, donde es la función de conteo prime . Ahora, para cada , escribir

(3)

y formar el vector exponente

(4)

Ahora bien, si son incluso para cualquier , entonces es un número cuadrado y hemos encontrado una solución a (◇). Si no, busca unacombinación lineal  de tal manera que los elementos son todos incluso, es decir,

(5)

(6)

Dado que este debe ser resuelto sólo mod 2, el problema se puede simplificar mediante la sustitución de la s con

(7)

Eliminación de Gauss se puede utilizar para resolver

(8)

para , donde es un vector igual a (mod 2). Una vez que se conoce, entonces tenemos

(9)

donde los productos se toman sobre todo para los que . Ambos lados son cuadrados perfectos , así que tenemos un 50% de probabilidades de que esto produce un factor trivial de . Si no lo hace, entonces se procede a una diferente y repita el procedimiento. No hay garantía de que este método dará lugar a un factor, pero en la práctica se produce factores más rápido que cualquier método que utiliza divisores de prueba. Es especialmente susceptibles de procesamiento en paralelo, ya que cada procesador puede trabajar en un valor diferente de .