En teoría de números , el método de factorización de Dixon (también el método de cuadrados aleatorios de Dixon [1] o el algoritmo de Dixon ) es un algoritmo de factorización de enteros de propósito general ; es el método prototípico de la base de factores . A diferencia de otros métodos de base de factores, su límite de tiempo de ejecución viene con una prueba rigurosa que no se basa en conjeturas sobre las propiedades de suavidad de los valores tomados por 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 encontrar una congruencia de cuadrados módulo el entero N que se pretende factorizar. El método de factorización de Fermat encuentra tal congruencia seleccionando valores x aleatorios o pseudoaleatorios y esperando que el número entero x 2 mod N sea un cuadrado perfecto (en los números enteros):
Por ejemplo, si N = 84923 , (comenzando en 292, el primer número mayor que √ N y contando hacia arriba) el 505 2 mod 84923 es 256, el cuadrado de 16. Entonces (505 - 16) (505 + 16) = 0 mod 84923 . Cálculo del máximo común divisor de 505 a 16 y N usando el algoritmo de Euclides da 163, que es un factor de N .
En la práctica, la selección al azar x valores tendrá un excesivamente largo tiempo para encontrar una congruencia de cuadrados, ya que sólo hay √ N plazas menos de N .
El método de Dixon reemplaza la condición "es el cuadrado de un número entero" por la mucho más débil "tiene solo pequeños factores primos"; 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. (Tales números se llaman B-suave con respecto a algún límite B ).
Si hay muchos números cuyos cuadrados se pueden factorizar como para un conjunto fijo de pequeños números primos, álgebra lineal módulo 2 en la matriz dará un subconjunto del cuyos cuadrados se combinan en un producto de pequeños números primos a una potencia par, es decir, un subconjunto de la cuyos cuadrados se multiplican al cuadrado de un número (con suerte diferente) mod N.
Método
Suponga que se factoriza el número compuesto N. Bound B se elige, y la base de factor de se identifica (que se llama P ), el conjunto de todos los números primos menos de o igual a B . A continuación, se buscan números enteros positivos z de manera que z 2 mod N sea B - suave. Por lo tanto, se puede escribir, para exponentes adecuados a i ,
Cuando se han generado suficientes de estas relaciones (generalmente es suficiente que el número de relaciones sea un poco más que el tamaño de P ), se pueden usar los métodos de álgebra lineal (por ejemplo, eliminación de Gauss ) para multiplicar estas diversas relaciones. de tal forma que los exponentes de los números primos del lado derecho sean todos pares:
Esto produce una congruencia de cuadrados de la forma a 2 ≡ b 2 (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 puede 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 se puede alcanzar un par no trivial de factores de N , y el algoritmo terminará.
Pseudocódigo
entrada: entero positivosalida: factor no trivial de Elija encuadernado Dejar ser todos primos repetir para a no elegir tal que es -liso Dejar tal que final para Encontrar no vacío tal que Dejar tiempo regreso
Ejemplo
Este ejemplo intentará factorizar N = 84923 usando 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 entrey N cuyos cuadrados mod N son B -suaves . Suponga que dos de los números encontrados son 513 y 537:
Entonces
Luego
Es decir,
La factorización resultante es 84923 = mcd (20712 - 16800, 84923) × mcd (20712 + 16800, 84923) = 163 × 521.
Optimizaciones
El tamiz cuadrático 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 2 módulo N sea pequeño, lo que aumenta en gran medida 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 defactores, por lo que cada fila de la matriz es casi todos ceros. En la práctica, a menudo se utiliza el algoritmo de bloque de Lanczos . Además, el tamaño de la base de factores debe elegirse con cuidado: si es demasiado pequeño, será difícil encontrar números que factoricen completamente sobre él, y si es demasiado grande, será necesario 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 con probabilidad de (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 demasiado grande, y que el tamaño de la base de factores ideal es alguna potencia de.
La complejidad óptima del método de Dixon es
en notación O grande , o
en L-notación .
Referencias
- ^ Kleinjung, Thorsten; et al. (2010). "Factorización de un módulo RSA de 768 bits". Avances en criptología - CRYPTO 2010 . Apuntes de conferencias en Ciencias de la Computación. 6223 . págs. 333–350. doi : 10.1007 / 978-3-642-14623-7_18 . ISBN 978-3-642-14622-0.
- ^ Dixon, JD (1981). "Factorización asintóticamente rápida de enteros" . Matemáticas. Comp. 36 (153): 255–260. doi : 10.1090 / S0025-5718-1981-0595059-1 . JSTOR 2007743 .