Algoritmo de dixon

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de mayo de 2021; las comprobaciones requieren 4 ediciones .

El algoritmo de Dixon es un algoritmo de factorización que utiliza básicamente la idea de Legendre , que consiste en encontrar un par de enteros y tal que y $X$ $y$ $x^2 \equiv y^2\pmod{n}$ $x \not\equiv \pm y\pmod{n}.$

El método de Dixon es una generalización del método de Fermat .

Historia [1]

En la década de 1920, Maurice Krajczyk (1882-1957), generalizando el teorema de Fermat, sugirió que en lugar de pares de números que satisfagan la ecuación , busquen pares de números que satisfagan una ecuación más general . Krajczyk notó varios hechos útiles para resolver. En 1981, John Dickson publicó un método de factorización que desarrolló utilizando las ideas de Kraitzik y calculó su complejidad computacional. [2] $x^2 - y^2 = norte$ $x^2 \equiv y^2\pmod{n}$

Descripción del algoritmo [3]

Haz una base factorial que consista en todos los números primos , donde . $\Beta = \izquierda\{ {p_1,p_2,\puntos,p_h} \derecha\}$ $p <= METRO = L\left({n}\right)^{\frac{1}{2}}$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\right)}$
Elige al azar $b, \sqrt{n}<b<n$
Calcula _ $a = b^2\bmod{n}$
Verifique la uniformidad del número por divisiones de prueba. Si es un número suave , es decir , debe recordar los vectores y : $a$ $a$ $\mathrm{B}$ $a = \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}$ $\vec{\alfa}\izquierda({b}\derecha)$ $\vec{\varepsilon}\left({b}\right)$ $\vec{\alpha}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right), \dots, \alpha_{p_h}\left({b}\ bien bien)$ $\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\bmod{2}, \dots, \alpha_{p_h}\left ({b}\derecho)\bmod{2}}\derecho)$ .
Repita el procedimiento de generación de números hasta encontrar los números suaves . $b$ $h+1$ $\mathrm{B}$ $b_1,...,b_{h+1}$
Usando el método de Gauss, encuentre una relación lineal entre los vectores : $\vec{\varepsilon}\left({b_1}\right), \dots, \vec{\varepsilon}\left({b_{h+1}}\right)$ $\vec{\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus\vec{\varepsilon}\left({b_{i_t}}\right)=\vec{0}, 1 \leqslant t \leqslant m$ y pon: $x=b_{i_1} \puntos b_{i_t}\bmod{n}$ $y=\prod_{p\isin\Beta}p^{\left({ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) } \right) \over{2}}\bmod{n}$ .
comprobar _ Si es así, repita el procedimiento de generación. Si no, entonces se encuentra una descomposición no trivial: $x \equiv \pm y \pmod{n}$ $n=u\cdot v,u=gcd\left({x+y,n}\right),v=mcd\left({xy,n}\right).$

Prueba de corrección [4]

Para que la fórmula sea correcta, la suma debe ser par. Vamos a demostrarlo: $y$ $\alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right)$ $(\alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right))\bmod{2} = (\varepsilon_p\left({b_{i_1} }\right)+\dots+\varepsilon_p\left({b_{i_t}}\right))\bmod{2} = {\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus \varepsilon\izquierda({b_{i_t}}\derecha) = 0$
$x^2 \equiv y^2\pmod{n}$ se sigue del hecho de que: $x^2 = b_{i_1}^2 \dots b_{i_t}^2 \equiv \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+ \alpha_p\left({b_{i_t}}\right) }}\pmod{n}$ $y^2 = \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }}$

Ejemplo

Factoricemos el número . $n=89755$

L(89755) = 194.174...

M = 13.934...

\Beta = \izquierda\{ 2, 3, 5, 7, 11, 13 \derecha\}

Todos los números encontrados con los vectores correspondientes se escriben en la tabla. $b$ ${\ vec {\ alfa}} (b)$

$b$	$a$	$\alpha_2\left({b}\right)$	$\alpha_3\left({b}\right)$	$\alpha_5\left({b}\right)$	$\alpha_7\left({b}\right)$	$\alpha_{11}\left({b}\right)$
337	23814	una	5	0	2	0
430	5390	una	0	una	2	una
519	96	5	una	0	0	0
600	980	2	0	una	2	0
670	125	0	0	3	0	0
817	39204	2	cuatro	0	0	2
860	21560	3	0	una	2	una

Resolviendo un sistema lineal de ecuaciones, obtenemos que . Después $\vec{\varepsilon}\left(337\right)\oplus\vec{\varepsilon}\left(519\right)=\vec{0}$

x = 337 \cdot 519 \bmod{89755}= 85148

y = 2^3 \cdot 3^3 \cdot 7^1 \bmod{89755} = 1512

85148 \no\equivale \pm 1512 \pmod{89755}

Como consecuencia,

{\ estilo de visualización u = mcd (86660,89755) = 3095}

{\ estilo de visualización v = gcd (83636,89755) = 29}

Resultó descomposición $89755 = 3095\cdot 29$

Complejidad computacional [5]

Denotar por el número de enteros tales que y es un número suave, donde . Del teorema de de Bruijn-Erdős , donde . Esto significa que cada número suave, en promedio, se encontrará con intentos. Para comprobar si un número es suave, se deben realizar divisiones . De acuerdo con el algoritmo, es necesario encontrar un número suave. Así que la complejidad computacional de encontrar números $\Psi(n,M)$ $a$ $1 < a \leqslant n$ $a$ $\mathrm{B}$ $\Beta = \{p : p < M\}$ $\Psi(n, M) = n \cdot u^{-u}$ $u = \frac{\ln{n}}{\ln{M}}$ $\mathrm{B}$ $tu ^ tu$ $\mathrm{B}$ $h$ $h+1$ $\mathrm{B}$

T_1 = O\izquierda({u^{u}\cdot h^{2}}\derecha)

Complejidad computacional del método de Gauss a partir de ecuaciones $h$

T_2 = O\izquierda({h^3}\derecha)

Por lo tanto, la complejidad total del algoritmo de Dixon

T = T_1 + T_2 = O\izquierda({u^{u}\cdot h^{2}+h^{3}}\derecha)

Teniendo en cuenta que el número de números primos es menor que el estimado por la fórmula , y que simplificando se obtiene $METRO$ $h = \frac{M}{\ln{M}}$ $u = \frac{\ln{n}}{\ln{M}}$

T=O\left(exp({\frac {\ln {n}\cdot \ln {\ln {n))}{\ln {M))}+2\ln {M})\right )

$METRO$ se elige de tal manera que sea mínimo. Luego sustituyendo obtenemos $T$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\right)}$

M=\left({\frac {L\left({n}\right)}{2}}\right)^{\frac {1}{2}}

T=O\left({L\left({n}\right)}^{2{\sqrt {2))}\right)

La estimación realizada por Pomeranz sobre la base de un teorema más riguroso que el teorema de Bruijn-Erdös [6] da , mientras que la estimación original de complejidad de Dixon da . $T = O\izquierda({L\izquierda({n}\derecha)}^{2}\derecha)$ $T=O\left({L\left({n}\right)}^{3{\sqrt {2))}\right)$

Estrategias adicionales [7]

Considere estrategias adicionales que aceleren el funcionamiento del algoritmo.

estrategia LP

La estrategia LP (Large Prime Variation) utiliza números primos grandes para acelerar el procedimiento de generación de números . $b$

Algoritmo

Deje que el número que se encuentra en el punto 4 no sea suave. Entonces se puede representar donde no es divisible por números de la base de factores. Es obvio que . Si además , entonces s es primo y lo incluimos en la base factorial. Esto le permite encontrar números suaves adicionales, pero aumenta la cantidad de números suaves requeridos en 1. Para volver a la base de factores original después del paso 5, haga lo siguiente. Si solo se encuentra un número, cuya expansión está incluida en un grado impar, entonces este número debe eliminarse de la lista y eliminarse de la base de factores. Si, por ejemplo, hay dos números y , entonces deben tacharse y agregarse el número . El indicador entrará en la expansión en un grado uniforme y estará ausente en el sistema de ecuaciones lineales. $a$ $\mathrm{B}$ $a = s \cdot \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}$ $s$ $s > M$ $s < M^2$ $\mathrm{B}$ $s$ $s$ $b_{1}$ $b_{2}$ $b = b_1\cdot b_2$ $s$ $b^2\bmod{n}$

Variación de estrategia

Es posible utilizar la estrategia PL con varios números primos que no están contenidos en la base de factores. En este caso , se utiliza la teoría de grafos para descartar números primos adicionales .

Complejidad computacional

La estimación teórica de la complejidad del algoritmo utilizando la estrategia LP, realizada por Pomerants, no difiere de la estimación de la versión original del algoritmo de Dixon:

T_{LP} = O\izquierda({L\izquierda({n}\derecha)}^{2}\derecha)

Estrategia EAS

La estrategia EAS (rotura temprana) elimina algunas de las consideraciones al no completar la prueba de suavidad . $b$ $a$

Algoritmo

se eligen los fijos . En el algoritmo de Dixon, se factoriza mediante divisiones de prueba por . En la estrategia, se elige EAS y el número se factoriza primero mediante divisiones de prueba por , y si después de la descomposición la parte no descompuesta sigue siendo mayor que , entonces se descarta la dada. $0 < k, l, m < 1$ $a$ $p < METRO = L\left({n}\right)^{\frac{1}{2}}$ $METRO = L\izquierda({n}\derecha)^{k}$ $pag < M^l = L\left({n}\right)^{kl}$ $n^{1-m}$ $b$

Variación de estrategia

Es posible utilizar una estrategia EAS con múltiples quiebres, es decir, con alguna secuencia ascendente y una secuencia descendente . $l_j$ $m_{j}$

Complejidad computacional

Se estima el algoritmo de Dixon usando la estrategia EAS para $k = \sqrt{\frac{2}{7}}, l = \frac{1}{2}, m = \frac{1}{7}$

T_{EAS} = O\izquierda({L\izquierda({n}\derecha)}^{\sqrt{\frac{7}{2))}\derecha)

Estrategia PS

La estrategia PS utiliza el algoritmo de Pollard-Strassen , que para y encuentra el divisor primo mínimo del número de gcds en . [ocho] $z, t \in \mathbb{N}$ $y=z^2$ $(t, y!)$ $O\left(z \cdot \ln^2{z} \cdot \ln^2{t}\right)$

Algoritmo

Fijo está seleccionado . En el algoritmo de Dixon, se factoriza mediante divisiones de prueba por . En la estrategia PS, . creemos _ Aplicamos el algoritmo de Pollard-Strassen, eligiendo para la parte no descompuesta, obtenemos la expansión . $0<k<1$ $a$ $p < METRO = L\left({n}\right)^{\frac{1}{2}}$ $METRO = L\izquierda({n}\derecha)^{k}$ $z = [L\left({n}\right)^{\frac{k}{2}}] + 1, y = z^2 \geqslant L\left({n}\right)^{k}, t = un$ $t$ $a$

Complejidad computacional

La complejidad del algoritmo de Dixon con estrategia PS es mínima en y es igual a $k = \frac{1}{\sqrt{3))$

T_{PS}=O\left({L\left({n}\right)}^{\sqrt {3}}\right)

Notas

↑ Ishmukhametov, 2011 , pág. 115.
↑ Dixon, J.D.Factorización asintóticamente rápida de enteros // Math . compensación : diario. - 1981. - vol. 36 , núm. 153 . - P. 255-260 . -doi : 10.1090/ S0025-5718-1981-0595059-1 . — .
↑ Cheryomushkin, 2001 , pág. 77-79.
↑ Vasilenko, 2003 , pág. 79.
↑ Cheryomushkin, 2001 , pág. 79-80.
↑ C. Pomerancia. Análisis y comparación de algunos algoritmos de factorización de enteros // HW Lenstra y R. Tijdeman, Eds., Computational Methods in Number Theory, Math Center Tracts —Part 1. Math Centrum, Ámsterdam: artículo. - 1982. - S. 89-139 . Archivado desde el original el 6 de noviembre de 2021.
↑ Vasilenko, 2003 , pág. 81-83.
↑ Cheryomushkin, 2001 , pág. 74-75.

Literatura

Vasilenko O. N. Algoritmos teóricos de números en criptografía . — M .: MTsNMO , 2003. — S. 78-83. — 328 pág. — ISBN 5-94057-103-4 . Archivado el 27 de enero de 2007 en Wayback Machine .
Cheremushkin AV Conferencias sobre algoritmos aritméticos en criptografía . - M. : MTSNMO , 2001. - S. 74-80. — 104 pág. — ISBN 5-94057-060-7 . Archivado el 31 de mayo de 2013 en Wayback Machine .
Ishmukhametov Sh. T. Métodos de factorización para números naturales: un tutorial . - Kazán: Kazán. un., 2011. - S. 115-117. — 190 págs.