Método de forma cuadrática de Shanks

El método de forma cuadrática de Shanks es un método de factorización de números enteros basado en el uso de formas cuadráticas , desarrollado por Daniel Shanks [1] en 1975 , como un desarrollo del método de factorización de Fermat .

Para las computadoras de 32 bits, los algoritmos basados en este método son los líderes indiscutibles entre los algoritmos de factorización para números de hasta y probablemente seguirán siéndolo. [2] Este algoritmo puede dividir casi cualquier número compuesto de 18 dígitos en menos de un milisegundo. El algoritmo es extremadamente simple, hermoso y eficiente. Además, los métodos basados en este algoritmo se utilizan como auxiliares en la expansión de divisores de números grandes como los números de Fermat . $10^{{10}}$ $10^{18}$

Historia

Otro nombre para el algoritmo es SQUFOF ( un acrónimo de inglés es SQUare FORm Factorization), que significa factorización de forma cuadrática . Este enfoque ha tenido bastante éxito a lo largo de los años y, como resultado, se pueden encontrar bastantes modificaciones e implementaciones diferentes sobre este tema en la literatura. [3] La mayoría de los métodos son complejos y confusos, especialmente cuando el método debe implementarse en una computadora. Como resultado, muchas variantes de algoritmos no son adecuadas para su implementación. Sin embargo, en 1975, Daniel Shanks propuso crear un algoritmo que pudiera implementarse y usarse no solo en una computadora, sino también en un simple teléfono móvil.

Aunque Shanks ha descrito otros algoritmos para la factorización de enteros, no ha publicado nada en SQUFOF. Dio conferencias sobre el tema y explicó la esencia básica de su método a un círculo bastante pequeño de personas. Algunos artículos de otros científicos [4] [3] [5] [6] discutieron el algoritmo, pero ninguno contiene un análisis detallado. También es interesante que en su método, Shanks hace una gran cantidad de suposiciones [7] que, desafortunadamente, quedaron sin prueba. En [8] se presentan los resultados de algunos experimentos, que indican que existen muchas suposiciones. Al final, en base a estas suposiciones simplificadoras, Shanks pudo crear SQUFOF.

Definiciones auxiliares

Para comprender cómo se implementa este algoritmo, es necesario conocer la información mínima sobre los objetos matemáticos utilizados en este método, a saber, las formas cuadráticas . Una forma cuadrática binaria es un polinomio en dos variables y : $X$ $y$

f(x,y)=ax^{2}+bxy+cy^{2}={\begin{pmatrix}x&y\end{pmatrix}}{\begin{pmatrix}a&b\\0&c\end{ pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}.

El método Shanks usa solo formas indefinidas . Por entendemos el discriminante de una forma cuadrática. Diremos que la forma cuadrática representa un número entero si existen números enteros tales que la igualdad sea cierta: . Si la igualdad es verdadera , entonces la representación se llama primitiva . $\Delta$ $F$ $m\en \mathbb {Z}$ ${\ estilo de visualización x_ {0}, y_ {0}}$ $f(x_{0},y_{0})=ax_{0}^{2}+bx_{0}y_{0}+cy_{0}^{2}$ ${\ estilo de visualización \ gcd (x_ {0}, y_ {0}) = 1}$

Para cualquier forma cuadrática indefinida , el operador de reducción se puede definir como: $f={\begin{pmatrix}a,&b,&c\end{pmatrix}}$

\rho {\begin{pmatrix}a,&b,&c\end{pmatrix}}={\begin{pmatrix}c,&r(-b,c),&{\frac {r(-b,c) )^{2}-\Delta }{4c}}\end{matrix}}

, donde se define como un entero , determinado únicamente por las condiciones: [8]

{\ estilo de visualización r (-b, c)}

r

$r+b\equiv 0\mod (2c)$
$-|c|<r<|c|,\quad si\quad {\sqrt {\Delta }}<|c|$
${\sqrt {\Delta }}-2|c|<r<{\sqrt {\Delta }},\quad si\quad |c|<{\sqrt {\Delta }}$

El resultado de aplicar el operador al formulario una vez se escribe como . El operador también se define como: $\rho$ $F$ $norte$ ${\ estilo de visualización \ rho ^ {n} (f)}$ ${\ estilo de visualización \ rho ^ {-1}}$

\rho ^{-1}{\begin{pmatrix}a,&b,&c\end{pmatrix}}={\begin{pmatrix}{\frac {r(-b,c)^{2}- \Delta {4c}},&r(-b,c),&c\end{pmatriz}}

, donde se define de la misma forma que en el caso anterior. Nótese que como resultado de aplicar los operadores y a una forma cuadrática con discriminante , las formas cuadráticas resultantes también tendrán discriminante .

{\ estilo de visualización r (-b, c)}

{\ estilo de visualización \ rho ^ {-1}}

\rho

f={\begin{pmatrix}a,&b,&c\end{pmatrix}}

\Delta

\Delta

El método para obtener una forma reducida equivalente a esta fue encontrado por Carl Gauss y consiste en la aplicación sucesiva del operador de reducción hasta que se reduce. ${\ estilo de visualización g = \ rho (f)}$ $F$

Teorema.

Cada forma es equivalente a alguna forma reducida, y cualquier forma reducida de es igual a alguna positiva . Si - se reduce, entonces también se reduce. $F$ $F$ ${\ estilo de visualización \ rho ^ {k} (f)}$ $k$ $F$ $\rho (f)$

Además, para una comprensión clara de todas las operaciones con formas cuadráticas, necesitamos los conceptos de formas cuadráticas cuadradas, adyacentes y ambiguas.

Opciones

La idea del método de Shanks es comparar el número a descomponer con una forma binaria cuadrática con discriminante , con lo cual luego se realiza una serie de transformaciones equivalentes y el paso de la forma a la forma ambigua . Entonces, será un divisor . $norte$ $F$ ${\ estilo de visualización D = 4n}$ $F$ ${\ estilo de visualización (a', b', c')}$ ${\ estilo de visualización \ gcd (a', b')}$ $norte$

La primera variante trabaja con formas cuadráticas binarias definidas positivas de un discriminante negativo dado, y en el grupo de clases de formas encuentra una forma ambigua , que da una factorización del discriminante. La complejidad de la primera opción está sujeta a la verdad de la hipótesis de Riemann extendida . [9] $O(n^{1/5+\varepsilon})$

La segunda variante es SQUFOF, que utiliza un grupo de clases de formas cuadráticas binarias con un discriminante positivo. También encuentra la forma ambigua y factoriza el discriminante. La complejidad de SQUFOF equivale a operaciones aritméticas; el algoritmo trabaja con números enteros que no excedan . Entre los algoritmos de factorización con complejidad exponencial, SQUFOF se considera uno de los más eficientes. [9] $O(n^{1/4+\varepsilon})$ ${\ estilo de visualización 2 {\ sqrt {n}}}$

Puntuación de convergencia

Según los cálculos realizados por el propio Shanks, el número de iteraciones del primer y segundo ciclo del algoritmo está determinado por el número de factores del número y es aproximadamente igual a: $w$ $norte$

${\frac{C}{2^{w}-2}}\cdot n^{1/4},$

donde es una constante igual a aproximadamente 2,4 para el primer ciclo de iteraciones. [diez] $C$

Descripción del algoritmo

Con más detalle, el algoritmo se puede escribir de la siguiente manera: [11]

Entrada: un número compuesto impar para factorizar. Si reemplazamos por Now La última propiedad es necesaria para que el determinante de la forma cuadrática sea fundamental, lo que asegura la convergencia del método. $norte$ $n\!\!\!\mod 4=1,$ $norte$ ${\ estilo de visualización 2n.}$ $n\!\!\!\mod 4=2;3.$

Salida: divisor no trivial . $norte$

1. Defina la forma cuadrática original , con discriminante , donde .

{\ estilo de visualización f = (1,2b,b^{2}-D)}

{\ estilo de visualización D = 4n}

b={\mathcal {b}}{\sqrt {n}}{\mathcal {c}}

2. Ejecutemos el ciclo de reducciones hasta que la forma quede cuadrada.

{\ estilo de visualización f = \ rho (f)}

F

3. Calcula la raíz cuadrada de

{\displaystyle f:~g=(a^{\prime},b^{\prime},c^{\prime})=f^{1/2))

4. Ejecutemos el ciclo de reducciones hasta que se estabilice el valor del segundo coeficiente . El número de iteraciones de este ciclo debe ser aproximadamente igual a la mitad del número de iteraciones del primer ciclo. El último valor dará el divisor del número (posiblemente trivial).

{\ estilo de visualización p = \ rho (g)}

b_{i+1}'=b_{i}'

metro

{\ estilo de visualización a ^ {\ principal}}

norte

Implementación del algoritmo

Ahora describimos el algoritmo para su implementación en una computadora. [11] Nótese que si bien la parte teórica del algoritmo está relacionada con transformaciones equivalentes de formas cuadráticas, la parte práctica del algoritmo se basa en calcular los coeficientes del método de fracción continua sin recurrir a las formas. Cada iteración del ciclo corresponde a una operación de aplicar el operador de reducción al formulario correspondiente. Si es necesario, puede restaurar los formularios correspondientes utilizando las fórmulas: ${\ estilo de visualización P, Q, r}$ $f_{k}=(a_{k},b_{k},c_{k})$ $(a_{k},b_{k},c_{k})=((-1)^{k-1}Q_{k-1},2P_{k},(-1)^{k }Q_{k})$

Entrada: número compuesto $norte$

Salida: divisor no trivial $norte$

Inicialización del algoritmo.
- Comprobemos si es un cuadrado perfecto. En caso afirmativo, calcule y finalice el cálculo. De lo contrario, pasemos al siguiente elemento. $norte$ $d={\sqrt {n)),$
- Si luego reemplazamos por Definir $n\equiv 1(mod4),$ $norte$ ${\ estilo de visualización 2n.}$ $D=4n,~q_{0}={\mathcal {b}}{\sqrt {D}}{\mathcal {c}}.$
- Determinar los valores iniciales de los parámetros. ${\ estilo de visualización P, Q, r:}$

$P_{0}=0,~Q_{0}=1,~r_{0}=P_{1}={\mathcal {b}}{\sqrt {n}}{\mathcal {c}} ,~Q_{1}=n-r_{0}^{2},r_{1}={\mathcal {b}}2r_{0}/Q_{1}{\mathcal {c}}.$

Primer ciclo
- $P_{k}=r_{k-1}\cdot Q_{k-1}-P_{k-1},~Q_{k}=Q_{k-2}+(P_{k-1} -P_{k})\cdot r_{k-1},r_{k}={\mathcal {b}}{\frac {P_{k}+{\mathcal {b}}{\sqrt {n}} {\mathcal {c}}}{Q_{k}}}{\mathcal {c}},~k\geq 2.$
- Seguimos calculando los coeficientes hasta encontrar Q_k, que es un cuadrado perfecto. Esto debería suceder en algún Let para un número entero Pasemos al siguiente ciclo. ${\displaystyle P_{k},~Q_{k}~r_{k))$ $k.$ $Q_{k}=d^{2}$ ${\ estilo de visualización d> 0.}$

Segundo ciclo.
- comencemos un ciclo de cálculo de nuevos parámetros Las fórmulas para la implementación del segundo ciclo seguirán siendo las mismas que antes. Solo cambiarán los valores iniciales de los parámetros. $P_{j}^{\principal},~Q_{j}^{\principal},~r_{j}^{\principal}.$ $P^{\principal},~Q^{\principal},~r^{\principal}:$
- $P_{0}^{\prime }=-P_{k},~Q_{0}^{\prime }=d,~r_{0}^{\prime }={\mathcal {b)) {\frac {P_{0}^{\prime }+{\mathcal {b}}{\sqrt {n}}{\mathcal {c}}}{Q_{0}^{\prime }}}{\ mathcal {c)),~P_{1}^{\prime }=r_{0}^{\prime }\cdot Q_{0}^{\prime }-P_{0}^{\prime },~Q_ {1}^{\principal}=(N-P_{1}^{\principal 2})/Q_{0}^{\principal}.$
- El cálculo debe continuar hasta que dos valores sucesivos sean iguales. Entonces, el valor dará el divisor deseado del número.La descripción del algoritmo de Shanks está completa. ${\displaystyle P_{j}^{\principal},~P_{j+1}^{\principal})$ $Q_{j}$ $norte.$

Como ya se mencionó, esta no es la única implementación de este algoritmo. También puede encontrar la implementación del algoritmo aquí [8]

Un ejemplo de factorización de un número

Aplicamos este método para factorizar el número [8] ${\ estilo de visualización N = 22117019}$

Ciclo #1
$F_{yo}$
$i$	${\ estilo de visualización (-1) ^ {i-1} Q_ {i-1}}$	${\displaystyle 2\cdot P_{i))$	${\ estilo de visualización (-1) ^ {i} Q_ {i}}$
${\ estilo de visualización 0}$	${\ estilo de visualización -8215}$	${\ estilo de visualización 2 \ cdot 4702}$	$una$
$una$	$una$	${\ estilo de visualización 2 \ cdot 4702}$	${\ estilo de visualización -8215}$
$2$	${\ estilo de visualización -8215}$	${\ estilo de visualización 2 \ cdot 3513}$	${\ estilo de visualización 1190}$
$3$	${\ estilo de visualización 1190}$	${\ estilo de visualización 2 \ cdot 3627}$	${\ estilo de visualización-7531}$
$cuatro$	${\ estilo de visualización-7531}$	${\ estilo de visualización 2 \ cdot 3904}$	${\ estilo de visualización 913}$
$5$	${\ estilo de visualización 913}$	${\ estilo de visualización 2 \ cdot 4313}$	${\ estilo de visualización -3850}$
$6$	${\ estilo de visualización -3850}$	${\ estilo de visualización 2 \ cdot 3387}$	${\ estilo de visualización 2765}$
$7$	${\ estilo de visualización 2765}$	${\ estilo de visualización 2 \ cdot 2143}$	${\displaystyle-6338}$
$ocho$	${\displaystyle-6338}$	${\ estilo de visualización 2 \ cdot 4195}$	${\ estilo de visualización 713}$
$9$	${\ estilo de visualización 713}$	${\ estilo de visualización 2 \ cdot 4361}$	${\ estilo de visualización -4346}$
$diez$	${\ estilo de visualización -4346}$	${\ estilo de visualización 2 \ cdot 4331}$	${\ estilo de visualización 773}$
$once$	${\ estilo de visualización 773}$	${\ estilo de visualización 2 \ cdot 4172}$	${\ estilo de visualización -6095}$
$12$	${\ estilo de visualización -6095}$	$2\cdot 1923$	${\ estilo de visualización 3022}$
$13$	${\ estilo de visualización 3022}$	${\ estilo de visualización 2 \ cdot 4121}$	${\ estilo de visualización-1699}$
$catorce$	${\ estilo de visualización-1699}$	${\ estilo de visualización 2 \ cdot 4374}$	${\ estilo de visualización 1757}$
$quince$	${\ estilo de visualización 1757}$	${\ estilo de visualización 2 \ cdot 4411}$	${\ estilo de visualización-1514}$
$dieciséis$	${\ estilo de visualización-1514}$	${\ estilo de visualización 2 \ cdot 4673}$	${\ estilo de visualización 185}$
$17$	${\ estilo de visualización 185}$	${\ estilo de visualización 2 \ cdot 4577}$	${\displaystyle-6314}$
$Dieciocho$	${\displaystyle-6314}$	${\ estilo de visualización 2 \ cdot 1737}$	${\ estilo de visualización 3025}$

Ciclo #2
$Soldado americano}$
$i$	$(-1)^{i-1}Q_{i-1}^{\principal}$	${\displaystyle 2\cdot P_{i}^{\prime ))$	${\ estilo de visualización (-1) ^ {i} Q_ {i} ^ {\ principal}}$
${\ estilo de visualización 0}$	${\ estilo de visualización -55}$	${\ estilo de visualización 2 \ cdot 4652}$	${\ estilo de visualización 8653}$
$una$	${\ estilo de visualización 8653}$	${\ estilo de visualización 2 \ cdot 4001}$	${\ estilo de visualización -706}$
$2$	${\ estilo de visualización -706}$	${\ estilo de visualización 2 \ cdot 4471}$	${\ estilo de visualización 3013}$
$3$	${\ estilo de visualización 3013}$	${\ estilo de visualización 2 \ cdot 4568}$	${\ estilo de visualización -415}$
$cuatro$	${\ estilo de visualización -415}$	${\ estilo de visualización 2 \ cdot 4562}$	${\ estilo de visualización 3145}$
$5$	${\ estilo de visualización 3145}$	${\ estilo de visualización 2 \ cdot 1728}$	${\displaystyle-6083}$
$6$	${\displaystyle-6083}$	${\ estilo de visualización 2 \ cdot 4355}$	${\ estilo de visualización 518}$
$7$	${\ estilo de visualización 518}$	${\ estilo de visualización 2 \ cdot 4451}$	${\ estilo de visualización -4451}$
$ocho$	${\ estilo de visualización -4451}$	${\ estilo de visualización 2 \ cdot 4451}$	${\ estilo de visualización 518}$

Ahora puedes ver en el segundo ciclo que De ahí el número $P_{7}^{\principal}=P_{8}^{\principal}.$ $N=22117019=4451\cdot 4969.$

Aplicaciones

Este algoritmo se usa en muchas implementaciones de NFS y QS para factorizar pequeños números auxiliares que surgen cuando se factoriza un entero grande. En cualquier caso, SQUFOF se usa principalmente como algoritmo auxiliar en algoritmos de factorización más potentes y, por lo tanto, SQUFOF generalmente se usará para factorizar números de tamaño modesto que no tienen divisores primos pequeños. Dichos números suelen ser el producto de un pequeño número de números primos diferentes. [8] .

Notas

↑ Para obtener más información sobre la historia de este método y su conexión con el método de la fracción continua, consulte el artículo de Gover y Wagstaff (J. Gover, SS Wagstaff).
↑ Yike Guo, 1999 , Minería de datos de alto rendimiento: algoritmos, aplicaciones y sistemas de escala.
↑ 1 2 Hans Riesel, 1994 , Números primos y métodos informáticos para la factorización. Birkhauser, segunda edición.
↑ Henri Cohen, 1996 , Un curso de teoría algebraica computacional de números.
↑ DA Buell, 1989 , Formas cuadráticas binarias.
↑ Samuel S. Wagstaff Jr., 2003 , Criptoanálisis de cifrados teóricos numéricos.
↑ Por ejemplo, en FACTORIZACIÓN EN FORMA CUADRADA JASON E. GOWER Y SAMUEL S. WAGSTAFF, JR. Supuesto 4.12. en la página 20, Supuesto 4.5 en la página 16, también al probar teoremas de complejidad de algoritmos, etc.
↑ 1 2 3 4 5 FACTORIZACIÓN EN FORMA CUADRADA, 2003 , FACTORIZACIÓN EN FORMA CUADRADA.
↑ 1 2 Vasilenko, 2003 , Algoritmos teóricos de números en criptografía.
↑ Ishmukhametov, 2011 , Métodos de factorización para números naturales: Libro de texto.
↑ 1 2 Ishmukhametov, 2011 , Métodos de factorización para números naturales: Libro de texto, págs. 79-80.

Literatura

Vasilenko O. N. Algoritmos teóricos de números en criptografía . - Moscú: MTSNMO, 2003. - S. 75 - 76. - 328 p. — ISBN 5-94057-103-4 . Archivado el 27 de enero de 2007 en Wayback Machine .
Ishmukhametov Sh. T. Métodos de factorización de números naturales: Libro de texto . - Kazan: Universidad de Kazan, 2011. - P. 74 - 82. - 190 p.
DA Buell. Formas cuadráticas binarias (neopr.) . - Nueva York: Springer-Verlag , 1989. - S. 197 - 199. - 247 p. - ISBN 0-387-97037-1 .
Hans Riesel. Números primos y métodos informáticos de factorización. Birkhauser, segunda edición . - Suecia: Birkhauser, 1994. - P. pp. 186 - 192. - ISBN 978-0-8176-8297-2 .
Enrique Cohen. Un curso de teoría de números algebraicos computacionales . - Springer-Verlag , 1996. - P. 433 - 437. - 534 p. — ISBN 3-540-55640-0 .
Jason E. Gower y Samuel S. Wagstaff, JR. FACTORIZACIÓN EN FORMA CUADRADA . - Moscú: MTSNMO, 2003. - S. 1-16, 35-36. — 38 s. — ISBN 5-94057-103-4 .
Samuel S. Wagstaff Jr. Criptoanálisis de cifrados teóricos de números . - Prensa CRC , 2003. - 318 p. — ISBN 978-1584881537 .
Yike Guo, RL Grossman. Minería de datos de alto rendimiento : algoritmos de escalado, aplicaciones y sistemas . - Editores académicos de Kluwer , 1999. - P. 111. - ISBN 0-7923-7745-1 .

Véase también

Factorización de números enteros

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin