Método de factorización de Dixon

En teoría de números , el método de factorización de Dixon (también conocido como método de cuadrados aleatorios de Dixon ^{[ 1 ]} o algoritmo de Dixon ) es un algoritmo de factorización de enteros de propósito general ; es el método prototípico basado en factores . A diferencia de otros métodos basados ​​en factores, su límite de tiempo de ejecución viene con una demostración rigurosa que no se basa en conjeturas sobre las propiedades de suavidad de los valores que toma un polinomio.

El algoritmo fue diseñado por John D. Dixon , un matemático de la Universidad de Carleton , y fue publicado en 1981. ^{[ 2 ]}

El método de Dixon se basa en encontrar una congruencia de cuadrados módulo el entero N que se pretende factorizar. Aquí explicamos la idea básica describiendo primero el método de factorización de Fermat y luego cómo el método de Dixon procede de manera diferente.

El método de factorización de Fermat encuentra dicha congruencia seleccionando valores x aleatorios o pseudoaleatorios y esperando que el entero x² ^mod N sea un cuadrado perfecto no trivial (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 (empezando por 292, el primer número mayor que √N y contando hacia arriba), 505² mod 84923 es 256, el cuadrado de 16. Entonces (505 ⁻ 16 )(505 + 16) = 0 mod 84923. Calculando el máximo común divisor de 505 − 16 y N usando el algoritmo de Euclides se obtiene 163, que es un factor de N.

En la práctica, seleccionar valores x aleatorios llevará un tiempo impracticablemente 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 un cuadrado perfecto no trivial" por la mucho más débil "tiene solo factores primos pequeños"; por ejemplo, hay 292 cuadrados menores que 84923; 662 números menores que 84923 cuyos factores primos son solo 2, 3, 5 o 7; y 4767 cuyos factores primos son todos menores que 30. (Estos números se denominan 7-suaves y 30-suaves, respectivamente, ya que son B-suaves con respecto a algún límite B ).

Una vez que se encuentren suficientes de estos valores B -suaves, se puede utilizar el álgebra lineal para buscar cuadrados perfectos no triviales para el método de factorización de Fermat. Si hay muchos números${\displaystyle a_{1}\ldots a_{n}}$cuyos cuadrados pueden factorizarse como${\displaystyle a_{i}^{2}\mod N=\prod _{j=1}^{m}b_{j}^{e_{ij}}}$para un conjunto fijo${\displaystyle b_{1}\ldots b_{m}}$de primos pequeños, álgebra lineal módulo 2 en la matriz${\displaystyle e_{ij}}$dará un subconjunto de los${\displaystyle a_{i}}$cuyos cuadrados se combinan para dar un producto de primos pequeños elevados a una potencia par , es decir, un subconjunto de los${\displaystyle a_{i}}$cuyos cuadrados se multiplican para dar el cuadrado de un número (con suerte diferente) módulo N.

Supongamos que se está factorizando el número compuesto N. Se elige el límite B y se identifica la base del factor (que se llama P ), el conjunto de todos los primos menores o iguales a B. A continuación, se buscan 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 basta con que el número de relaciones sea un poco mayor que el tamaño de P ), se pueden utilizar los métodos del álgebra lineal , como la eliminación gaussiana , para multiplicar estas diversas relaciones de tal manera que los exponentes de los primos del 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{donde }}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 se puede convertir 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 ocurrir si a ≡ ± b (mod N ), en cuyo caso se debe intentar de nuevo con una combinación diferente de relaciones; pero si se alcanza un par de factores no triviales de N , el algoritmo termina.

Esta sección está tomada directamente de Dixon (1981).

El algoritmo de Dixon

Inicialización. Sea L una lista de enteros en el rango [1, n ], y sea P = { p ₁ , ..., p _h } la lista de los h primos ≤ v . Sean B y Z listas inicialmente vacías ( Z será indexada por B ).

Paso 1. Si L está vacío, salir (el algoritmo no tuvo éxito). De lo contrario, tomar el primer término z de L , eliminarlo de L y proceder al Paso 2.

Paso 2. Calcula w como el menor resto positivo de z² ^mod n . Factoriza w como:

${\displaystyle w=w'\prod _ {i}p_ {i}^{a_ {i}}}$

donde w ′ no tiene ningún factor en P . Si w ′ = 1, proceda al Paso 3; de lo contrario, regrese al Paso 1.

Paso 3. Sea a ← ( a ₁ , ..., a _h ). Agregue a a B y z a Z . Si B tiene como máximo h elementos, regrese al Paso 1; de lo contrario, proceda al Paso 4.

Paso 4. Encuentra el primer vector c en B que depende linealmente (módulo 2) de vectores anteriores en B. Elimina c de B y${\displaystyle z_{c}}$de Z . Calcular coeficientes${\displaystyle f_{b}}$de tal manera que:

${\displaystyle \mathbf {c} \equiv \sum _{b\in B}f_{b}\mathbf {b} {\pmod {2}}}$

Definir:

${\displaystyle \mathbf {d} =(d_{1},\dots ,d_{n})\gets {\frac {1}{2}}\left(\mathbf {c} +\sum f_{b}\mathbf {b} \right)}$

Continúe con el paso 5.

Paso 5. Calcular:

${\displaystyle x\gets z_{c}\prod _{b}z_{b}^{f_{b}},\quad y\gets \prod _{i}p_{i}^{d_{i}}}$

de modo que:

${\displaystyle x^{2}\equiv \prod _{i}p_{i}^{2d_{i}}=y^{2}\mod n.}$

Si${\displaystyle x\equiv y}$o${\displaystyle x\equiv -y{\pmod {n}}}$, vuelva al paso 1. De lo contrario, devuelva:

${\displaystyle \gcd(n,x+y)}$

lo que proporciona un factor no trivial de n y termina con éxito.

En este ejemplo, factorizamos ( n = 84923) usando el algoritmo de Dixon. Este ejemplo es una ligera adaptación del subconjunto de LeetArxiv. ^{[ 3 ]} Se reconoce el mérito del autor original.

• Inicialización :
  • Defina una lista de números L , que va desde 1 hasta 84923:

${\displaystyle L=\{1,\dots ,84923\}}$

• Defina un valor v , que es el factor de suavidad:

${\displaystyle v=7}$

• Defina una lista P que contenga todos los números primos menores o iguales a v :

${\displaystyle P={2,3,5,7}}$

• Definimos B y Z , dos listas vacías. B es una lista de potencias, mientras que Z es una lista de números enteros aceptados:

${\displaystyle B=[]}$

${\displaystyle Z=[]}$

• Paso 1 : Iterar${\displaystyle z}$valores
  • Inicia un bucle for que indexe la lista.${\displaystyle L}$. El elemento actual en${\displaystyle L}$está etiquetado como${\displaystyle z}$El bucle for finaliza al término de la lista, o cuando el paso 5 interrumpe el bucle.

int n = 84923 ; for ( int i = 1 ; i <= n ; i ++ ) { int z = i ; // Los pasos restantes van aquí. // El paso 4 puede activar el paso 5. // El paso 5 puede romper el bucle. }

• Paso 2 : Cálculo${\displaystyle z^{2}\mod n}$y factorización prima v-suave
  • Para continuar, calcule${\displaystyle z^{2}\mod 84923}$Para cada z , exprese el resultado como una factorización prima.

${\displaystyle 1^{2}\mod 84923\equiv 1\mod 84923=2^{0}\cdot 3^{0}\cdot 5^{0}\cdot 7^{0}\mod 84923}$

${\displaystyle \vdots }$

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

${\displaystyle \vdots }$

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

${\displaystyle 538^{2}\mod 84923=34675\mod 84923=5^{2}\cdot 19^{1}\cdot 73^{1}\mod 84923}$

Este paso continúa para todos los valores de z en el rango.

• Paso 3 : Agregar resultados de v-smooth
  • Si${\displaystyle z^{2}\mod 84923}$es 7-suave, luego agregue sus poderes a la lista${\displaystyle B}$y añadir${\displaystyle z}$para enumerar${\displaystyle Z}$.
  • Si${\displaystyle B}$tiene como máximo${\displaystyle h=4}$elementos, vuelva al paso 1. De lo contrario, proceda al paso 4.
  • Por ejemplo, después de 537 iteraciones, tenemos:

${\displaystyle Z=\{1,\ldots ,513,537\}}$

${\displaystyle B=\{[0,0,0,0],\ldots ,[4,1,2,1],[6,1,2,1]\}}$

y procedemos al paso 4 ya que tendríamos más de${\displaystyle h=4}$vectores en${\displaystyle B}$.

• Paso 4 : Este paso se divide en dos partes.
  • Parte 1 : Hallazgo${\displaystyle B}$módulo 2

${\displaystyle B={\begin{pmatrix}0&0&0&0\\4&1&2&1\\6&1&2&1\end{pmatrix}}\mod 2\equiv B={\begin{pmatrix}0&0&0&0\\0&1&0&1\\0&1&0&1\end{pmatrix}}}$

• Parte 2 : Encontrar una combinación de filas de${\displaystyle B}$que suman números pares

Por ejemplo, sumando la fila${\displaystyle 2}$y fila${\displaystyle 3}$nos da un vector de números pares.

${\displaystyle R_{2}=\{0,1,0,1\}}$y${\displaystyle R_{3}=\{0,1,0,1\}}$

entonces

${\displaystyle R_{2}+R_{3}=\{0,1,0,1\}+\{0,1,0,1\}}$

${\displaystyle R_{2}+R_{3}=\{0,2,0,2\}}$.

• Paso 5 : Este paso se divide en cuatro partes.
  • Parte 1 : Computación x
    • Multiplica el correspondiente${\displaystyle z}$valores para las filas encontradas en el Paso 4 , módulo${\displaystyle n}$Llegar${\displaystyle x}$.

Las filas 2 y 3 corresponden a 513 y 537, por lo tanto${\displaystyle x=(513\cdot 537)=20712\mod 84923}$

• Parte 2 : Informática${\displaystyle y}$

• Agregue las filas encontradas en el Paso 4 .
• Divide entre 2. (Como estos representan exponentes, esto equivale a calcular una raíz cuadrada).
• Aplicar como exponentes a los primos en${\displaystyle P}$Llegar${\displaystyle y}$.
• Regrese al paso 1 si${\displaystyle x=\pm y}$.

Calcula la mitad de la suma de las filas 2 y 3:

${\displaystyle {\begin{array}{ccccc}&4&1&2&1\\+&6&1&2&1\\\hline &10&2&4&2\\\div 2\\\hline &5&1&2&1\end{array}}}$

Aplique esos como exponentes a${\displaystyle P=\{2,3,5,7\}}$:

${\displaystyle y=2^{5}\cdot 3^{1}\cdot 5^{2}\cdot 7^{1}=16800}$

• Desde${\displaystyle x\neq \pm y}$, procedemos a la Parte 3 .

• Parte 3 : Informática${\displaystyle x+y}$y${\displaystyle x-y}$dónde${\displaystyle x=20712}$y${\displaystyle y=16800}$

${\displaystyle x+y=20712+16800=37512}$

${\displaystyle x-y=20712-16800=3912}$

• Parte 4 : Informática${\displaystyle \gcd(x+y,n)}$y${\displaystyle \gcd(x-y,n)}$dónde${\displaystyle n=84923}$,${\displaystyle x+y=292281}$y${\displaystyle x-y=258681}$

${\displaystyle {\begin{array}{ll}\gcd(37512,84923)=521\\\gcd(3912,84923)=163\end{array}}}$

Una comprobación rápida muestra${\displaystyle 84923=521\cdot 163}$.

El pseudocódigo dice que solo hay que calcular${\displaystyle x+y}$y regresar${\displaystyle \gcd(x+y,n)}$Esto se debe a que es el MCD más rápido de calcular, y una vez que lo tienes, dividir${\displaystyle n}$por el resultado es más rápido que el cálculo${\displaystyle \gcd(x-y,n)}$.

El método ^de 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 tales que x² módulo N sea pequeño, lo que aumenta considerablemente la probabilidad de obtener un número suave.

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

Un análisis más sofisticado, utilizando la aproximación de que un número tiene todos sus factores primos menores que${\displaystyle N^{1/a}}$con probabilidad sobre${\displaystyle a^{-a}}$(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 elegir una demasiado grande, y que el tamaño ideal de la base de factores es alguna potencia de${\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 de O grande , o

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

en notación L.