Método de factorización de Dixon

En teoría de números , el método de factorización de Dixon (también llamado método de cuadrados aleatorios de Dixon ^[1] o algoritmo de Dixon ) es un algoritmo de factorización de números enteros de propósito general ; es el método de base factorial prototípico . A diferencia de otros métodos de base factorial, su límite de tiempo de ejecución viene con una prueba rigurosa que no depende de conjeturas sobre las propiedades de suavidad de los valores tomados por un polinomio.

El algoritmo fue diseñado por John D. Dixon, matemático de la Universidad de Carleton , y se publicó en 1981. ^[2]

Idea básica

El método de Dixon se basa en hallar una congruencia de cuadrados módulo el entero N que se pretende factorizar. El método de factorización de Fermat halla dicha congruencia seleccionando valores x aleatorios o pseudoaleatorios y esperando que el entero x ²  mod N sea un cuadrado perfecto (en los enteros):

${\displaystyle x^{2}\equiv y^{2}\quad ({\hbox{mod }}N),\qquad x\not \equiv \pm y\quad ({\hbox{mod }}N).}$

Por ejemplo, si N = 84923 , (comenzando en 292, el primer número mayor que √ N y contando hacia arriba) el 505 ² mod 84923 es 256, el cuadrado de 16. Entonces (505 − 16)(505 + 16) = 0 mod 84923 . Calcular el máximo común divisor de 505 − 16 y N usando el algoritmo de Euclides da 163, que es un factor de N .

En la práctica, seleccionar valores x aleatorios tomará un tiempo imprácticamente largo para encontrar una congruencia de cuadrados, ya que solo hay √ N cuadrados menores que N.

El método de Dixon reemplaza la condición "es el cuadrado de un entero" por otra mucho más débil: "sólo tiene factores primos pequeños"; por ejemplo, hay 292 cuadrados menores que 84923; 662 números menores que 84923 cuyos factores primos son sólo 2, 3, 5 o 7; y 4767 cuyos factores primos son todos menores que 30. (Estos números se denominan B-suaves con respecto a algún límite B ).

Si hay muchos números cuyos cuadrados se pueden factorizar como para un conjunto fijo de primos pequeños, el álgebra lineal módulo 2 sobre la matriz dará un subconjunto de los cuales sus cuadrados se combinan para dar un producto de primos pequeños elevado a una potencia par, es decir, un subconjunto de los cuyos cuadrados se multiplican al cuadrado de un número (con suerte diferente) módulo N. ${\displaystyle a_{1}\ldots a_{n}}$ ${\displaystyle a_{i}^{2}\mod N=\prod _{j=1}^{m}b_{j}^{e_{ij}}}$ ${\displaystyle b_{1}\ldots b_{m}}$ ${\displaystyle e_{ij}}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}}$

Método

Supongamos que se está factorizando el número compuesto N. Se elige el límite B y se identifica el factor base (que se llama P ), el conjunto de todos los primos menores o iguales a B . A continuación, se buscan los enteros positivos z tales que z ²  mod  N sea B -suave. Por lo tanto, podemos escribir, para exponentes adecuados a _i ,

${\displaystyle z^{2}{\text{ mod }}N=\prod _{p_{i}\in P}p_{i}^{a_{i}}}$

Cuando se han generado suficientes de estas relaciones (generalmente es suficiente que el número de relaciones sea unas pocas más que el tamaño de P ), se pueden utilizar los métodos del álgebra lineal , como la eliminación gaussiana , para multiplicar juntas estas diversas relaciones de tal manera que los exponentes de los primos en el lado derecho sean todos pares:

${\displaystyle {z_{1}^{2}z_{2}^{2}\cdots z_{k}^{2}\equiv \prod _{p_{i}\in P}p_{i}^{a_{i,1}+a_{i,2}+\cdots +a_{i,k}}\ {\pmod {N}}\quad ({\text{where }}a_{i,1}+a_{i,2}+\cdots +a_{i,k}\equiv 0{\pmod {2}})}}$

Esto produce una congruencia de cuadrados de la forma a ² ≡ b ² (mod N ), que puede convertirse en una factorización de N , N = mcd ( a + b , N ) × ( N / mcd ( a + b , N )). Esta factorización podría resultar trivial (es decir, N = N × 1 ), lo que solo puede suceder si a ≡ ± b (mod N ), en cuyo caso se debe hacer otro intento con una combinación diferente de relaciones; pero si se alcanza un par de factores no triviales de N , el algoritmo termina.

Pseudocódigo

entrada: entero positivo salida: factor no trivial de ${\textstyle N}$ ${\textstyle N}$Elija el límite
Sea todos los primos ${\textstyle B}$ ${\textstyle P:=\{p_{1},p_{2},\ldots ,p_{k}\}}$ ${\textstyle \leq B}$repetir  para  hacer Elija tal que sea -suave ${\textstyle i=1}$   ${\textstyle k+1}$  ${\textstyle 0<z_{i}<N}$ ${\textstyle z_{i}^{2}{\text{ mod }}N}$ ${\textstyle B}$Que tal fin sea para ${\textstyle a_{i}:=\{a_{i1},a_{i2},\ldots ,a_{ik}\}}$ ${\textstyle z_{i}^{2}{\text{ mod }}N=\prod _{p_{j}\in P}p_{j}^{a_{ij}}}$  Encuentra un no vacío tal que sea mientras ${\textstyle T\subseteq \{1,2,\ldots ,k+1\}}$ ${\textstyle \sum _{i\in T}a_{i}\equiv {\vec {0}}{\pmod {2}}}$ ${\textstyle x:=\left(\prod _{i\in T}z_{i}\right){\text{ mod }}N}$  ${\textstyle y:=\left(\prod _{p_{j}\in P}p_{j}^{\left(\sum _{i\in T}a_{ij}\right)/2}\right){\text{ mod }}N}$  ${\textstyle x\equiv \pm y{\pmod {N}}}$ devolver  ${\textstyle \gcd(x+y,N)}$

Ejemplo

En este ejemplo se intentará factorizar N  = 84923 utilizando el límite B  = 7. La base del factor es entonces P  = {2, 3, 5, 7}. Se puede realizar una búsqueda de números enteros entre y N cuyos cuadrados módulo N sean B -suaves . Supongamos que dos de los números encontrados son 513 y 537: ${\displaystyle \left\lceil {\sqrt {84923}}\right\rceil =292}$

${\displaystyle 513^{2}\mod 84923=8400=2^{4}\cdot 3\cdot 5^{2}\cdot 7}$

${\displaystyle 537^{2}\mod 84923=33600=2^{6}\cdot 3\cdot 5^{2}\cdot 7}$

Entonces

${\displaystyle (513\cdot 537)^{2}\mod 84923=2^{10}\cdot 3^{2}\cdot 5^{4}\cdot 7^{2}\mod 84923}$

Entonces

${\displaystyle {\begin{aligned}&{}(513\cdot 537)^{2}\mod 84923\\&=(275481)^{2}\mod 84923\\&=(84923\cdot 3+20712)^{2}\mod 84923\\&=(84923\cdot 3)^{2}+2\cdot (84923\cdot 3\cdot 20712)+20712^{2}\mod 84923\\&=0+0+20712^{2}\mod 84923\end{aligned}}}$

Eso es, ${\displaystyle 20712^{2}\mod 84923=(2^{5}\cdot 3\cdot 5^{2}\cdot 7)^{2}\mod 84923=16800^{2}\mod 84923.}$

La factorización resultante es 84923 = mcd(20712 − 16800, 84923) × mcd(20712 + 16800, 84923) = 163 × 521.

Optimizaciones

La criba cuadrática es una optimización del método de Dixon. Selecciona valores de x cercanos a la raíz cuadrada de N de modo que x ² módulo N sea pequeño, lo que aumenta considerablemente la posibilidad de obtener un número uniforme.

Otras formas de optimizar el método de Dixon incluyen el uso de un mejor algoritmo para resolver la ecuación matricial, aprovechando la escasez de la matriz: un número z no puede tener más de factores, por lo que cada fila de la matriz está formada casi en su totalidad por ceros. En la práctica, se suele utilizar el algoritmo de Lanczos en bloques . Además, el tamaño de la base de factores debe elegirse con cuidado: si es demasiado pequeña, será difícil encontrar números que factoricen completamente sobre ella, y si es demasiado grande, habrá que recopilar más relaciones. ${\displaystyle \log _{2}z}$

Un análisis más sofisticado, que utiliza la aproximación de que un número tiene todos sus factores primos menores que con probabilidad de 0 (una aproximación a la función de Dickman-de Bruijn ), indica que elegir una base de factores demasiado pequeña es mucho peor que una demasiado grande, y que el tamaño ideal de la base de factores es alguna potencia de . ${\displaystyle N^{1/a}}$ ${\displaystyle a^{-a}}$ ${\displaystyle \exp \left({\sqrt {\log N\log \log N}}\right)}$

La complejidad óptima del método de Dixon es

${\displaystyle O\left(\exp \left(2{\sqrt {2}}{\sqrt {\log n\log \log n}}\right)\right)}$

en notación O grande , o

${\displaystyle L_{n}[1/2,2{\sqrt {2}}]}$

en notación L.

Referencias

1. Kleinjung, Thorsten; et al. (2010). "Factorización de un módulo RSA de 768 bits". Avances en criptología – CRYPTO 2010. Apuntes de clase en informática. Vol. 6223. págs. 333–350. doi :10.1007/978-3-642-14623-7_18. ISBN 978-3-642-14622-0.S2CID11556080  .​
2. Dixon, JD (1981). "Factorización asintóticamente rápida de números enteros". Math. Comp. 36 (153): 255–260. doi : 10.1090/S0025-5718-1981-0595059-1 . JSTOR  2007743.