The method of quadratic Shanks forms

The method of quadratic Shanks forms is a method of factorization of integers , based on the application of quadratic forms , developed by Daniel Shanks ( . ^[1] in 1975 , as a development of Fermat's factorization method .

For 32-bit computers, algorithms based on this method are the undisputed leaders among factorization algorithms for numbers from $10^{10}$ ${\ displaystyle 10 ^ {10}}$ $10 ^ {{10}}$ before $10^{18}$ ${\ displaystyle 10 ^ {18}}$ $10 ^ {18}$ and probably will remain so. ^[2] This algorithm can split almost any composite 18-digit number in less than a millisecond. The algorithm is extremely simple, beautiful and efficient. In addition, methods based on this algorithm are used as auxiliary methods in the expansion of divisors of large numbers such as Fermat numbers .

Content

History

Another name for the algorithm is SQUFOF (the acronym for English is SQUare FOrm Factorization), which means factorization using the quadratic form method. This approach has been quite successful over the years and, as a result, quite a lot of different modifications and implementations can be found on this topic in the literature. ^[3] Most of the methods are complicated and confusing, especially when it is necessary to implement the method on a computer. As a result, many variants of the algorithms are not suitable for implementation. However, in 1975, Daniel Shanks proposed creating an algorithm that can be implemented and used not only on a computer, but also on a simple mobile phone.

Although Shanks described other algorithms for factoring integers, he did not publish anything on SQUFOF. He gave lectures on this topic and explained the main essence of his method to a rather small circle of people. Some works of other scientists ^[4] ^[3] ^[5] ^[6] discussed the algorithm, but none contain a detailed analysis. It is also interesting that Shanks makes a rather large number of assumptions in his method ^[7] , which, unfortunately, remained without proof. In ^[8] , the results of some experiments are presented, which indicate that many assumptions hold true. As a result, based on these simplifying assumptions, Shanks managed to create SQUFOF.

Auxiliary definitions

In order to understand how this algorithm is implemented, it is necessary to find out the minimum information about the mathematical objects used in this method, namely, quadratic forms . A binary quadratic form is called a polynomial in two variables $x$ ${\ displaystyle x}$ and $y$ ${\ displaystyle 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}}.

{\ displaystyle 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}}.}

The Shanks method uses only vague forms . Under $\Delta$ ${\ displaystyle \ Delta}$ we will understand the discriminant of a quadratic form. We say that the quadratic form $f$ ${\ displaystyle f}$ represents an integer $m\in \mathbb {Z}$ ${\ displaystyle m \ in \ mathbb {Z}}$ if such integers exist $x_{0},y_{0}$ ${\ displaystyle x_ {0}, y_ {0}}$ that equality holds: $f(x_{0},y_{0})=ax_{0}^{2}+bx_{0}y_{0}+cy_{0}^{2}$ ${\ displaystyle f (x_ {0}, y_ {0}) = ax_ {0} ^ {2} + bx_ {0} y_ {0} + cy_ {0} ^ {2}}$ . If the equality holds $\gcd(x_{0},y_{0})=1$ ${\ displaystyle \ gcd (x_ {0}, y_ {0}) = 1}$ , then the representation is called primitive .

For any indefinite quadratic form $f={\begin{pmatrix}a,&b,&c\end{pmatrix}}$ ${\ displaystyle f = {\ begin {pmatrix} a, & b, & c \ end {pmatrix}}}$ it is possible to define a reduction operator as:

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

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

,Where

r(-b,c)

{\ displaystyle r (-b, c)}

- defined as an integer

r

{\ displaystyle r}

uniquely determined by the conditions: ^[8]

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

Result of using the operator $\rho$ ${\ displaystyle \ rho}$ to form $f$ ${\ displaystyle f}$ $n$ ${\ displaystyle n}$ times recorded as $\rho ^{n}(f)$ ${\ displaystyle \ rho ^ {n} (f)}$ . An operator is also defined. $\rho ^{-1}$ ${\ displaystyle \ rho ^ {- 1}}$ as:

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

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

where

r(-b,c)

{\ displaystyle r (-b, c)}

defined as in the previous case. Note that as a result of applying the operators

\rho ^{-1}

{\ displaystyle \ rho ^ {- 1}}

and

\rho

{\ displaystyle \ rho}

to quadratic form

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

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

with discriminant

\Delta

{\ displaystyle \ Delta}

obtained quadratic forms will also have discriminant

\Delta

{\ displaystyle \ Delta}

.

A method for obtaining a reduced form equivalent to this one was found by Karl Gauss and consists in the sequential application of the reduction operator $g=\rho (f)$ ${\ displaystyle g = \ rho (f)}$ , until $f$ ${\ displaystyle f}$ will not be reduced.

Theorem.

Each form $f$ ${\ displaystyle f}$ is equivalent to some reduced form, and any reduced form for $f$ ${\ displaystyle f}$ is equal to $\rho ^{k}(f)$ ${\ displaystyle \ rho ^ {k} (f)}$ for some positive $k$ ${\ displaystyle k}$ . If a $f$ ${\ displaystyle f}$ - reduced then $\rho (f)$ ${\ displaystyle \ rho (f)}$ also reduced.

Also, for clarity of understanding of all operations with quadratic forms, we need the concepts of square, adjacent and ambiguous quadratic forms

Options

The idea of the Shanks method is to match the number $n$ ${\ displaystyle n}$ , which must be decomposed, quadratic binary form $f$ ${\ displaystyle f}$ with discriminant $D=4n$ ${\ displaystyle D = 4n}$ with which a series of equivalent transformations and the transition from form are then performed $f$ ${\ displaystyle f}$ ambiguous $(a',b',c')$ ${\ displaystyle (a ', b', c ')}$ . Then, $\gcd(a',b')$ ${\ displaystyle \ gcd (a ', b')}$ will be a divider $n$ ${\ displaystyle n}$ .

The first option works with positively defined binary quadratic forms of a given negative discriminant, and in the group of classes of forms it finds an Ambigu form that decomposes the discriminant into factors. The complexity of the first option is $O(n^{1/5+\varepsilon })$ ${\ displaystyle O (n ^ {1/5 + \ varepsilon})}$ subject to the truth of the extended Riemann hypothesis . ^[9]

The second option is SQUFOF, it uses a group of classes of binary quadratic forms with positive discriminant. In it, the ambit form is also found and the discriminant is factorized. SQUFOF difficulty is $O(n^{1/4+\varepsilon })$ ${\ displaystyle O (n ^ {1/4 + \ varepsilon})}$ arithmetic operations; the algorithm works with integers not exceeding $2{\sqrt {n}}$ ${\ displaystyle 2 {\ sqrt {n}}}$ . Among exponential complexity factorization algorithms, SQUFOF is considered one of the most efficient. ^[9]

Convergence Rating

According to the calculations performed by Shanks himself, the number of iterations of the first and second cycles of the algorithm is determined by the number $w$ ${\ displaystyle w}$ number factors $n$ ${\ displaystyle n}$ and is approximately equal to:

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

Where $C$ ${\ displaystyle C}$ - a constant of approximately 2.4 for the first iteration cycle. ^[ten]

Algorithm Description

In more detail, the algorithm can be written as follows: ^[11]

Input: Odd Compound $n$ ${\ displaystyle n}$ to be factorized. If a $n\!\!\!\mod 4=1,$ ${\ displaystyle n \! \! \!! \ mod 4 = 1,}$ replace $n$ ${\ displaystyle n}$ on $2n.$ ${\ displaystyle 2n.}$ Now $n\!\!\!\mod 4=2;3.$ ${\ displaystyle n \! \! \!! \ mod 4 = 2; 3.}$ The last property requires that the determinant of the quadratic form be fundamental, which ensures the convergence of the method.

Output: Nontrivial Divider $n$ ${\ displaystyle n}$ .

1. Define the initial quadratic form

f=(1,2b,b^{2}-D)

{\ displaystyle f = (1,2b, b ^ {2} -D)}

, with discriminant

D=4n

{\ displaystyle D = 4n}

where

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

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

.

2. Perform a reduction cycle

f=\rho (f)

{\ displaystyle f = \ rho (f)}

while form

f

{\ displaystyle f}

will not become square.

3. Calculate the square root of

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

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

4. We carry out the reduction cycle

p=\rho (g)

{\ displaystyle p = \ rho (g)}

until the value of the second coefficient stabilizes

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

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

. Number of iterations

m

{\ displaystyle m}

this loop should be approximately equal to half the number of iterations of the first loop. Last value

a^{\prime }

{\ displaystyle a ^ {\ prime}}

will give a divisor of a number

n

{\ displaystyle n}

(possibly trivial).

Algorithm Implementation

Now we describe the algorithm for implementation on a computer. ^[11] Note that although the theoretical part of the algorithm is associated with equivalent transformations of quadratic forms, the practical part of the algorithm is based on the calculation of $P, Q, r$ ${\ displaystyle P, Q, r}$ the method of continued fractions without resorting to forms. Each iteration of the cycle corresponds to one operation of applying the reduction operator to the corresponding form. If necessary, you can restore the appropriate forms. $f_{k}=(a_{k},b_{k},c_{k})$ ${\ displaystyle f_ {k} = (a_ {k}, b_ {k}, c_ {k})}$ according to the formulas: $(a_{k},b_{k},c_{k})=((-1)^{k-1}Q_{k-1},2P_{k},(-1)^{k}Q_{k})$ ${\ displaystyle (a_ {k}, b_ {k}, c_ {k}) = ((- 1) ^ {k-1} Q_ {k-1}, 2P_ {k}, (- 1) ^ {k } Q_ {k})}$

Input: Compound $n$ ${\ displaystyle n}$

Output: Nontrivial Divider $n$ ${\ displaystyle n}$

Initialization of the algorithm.
- Check whether $n$ ${\ displaystyle n}$ full square. If yes, then calculate $d={\sqrt {n}},$ ${\ displaystyle d = {\ sqrt {n}},}$ and complete the calculation. Otherwise, move on to the next item.
- If a $n\equiv 1(mod4),$ ${\ displaystyle n \ equiv 1 (mod4),}$ then replace $n$ ${\ displaystyle n}$ on $2n.$ ${\ displaystyle 2n.}$ Define $D=4n,~q_{0}={\mathcal {b}}{\sqrt {D}}{\mathcal {c}}.$ ${\ displaystyle D = 4n, ~ q_ {0} = {\ mathcal {b}} {\ sqrt {D}} {\ mathcal {c}}.}$
- Define the initial values of the parameters $P, Q, r :$ ${\ displaystyle 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}}.$ ${\ displaystyle 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}}.}$

First cycle
- $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.$ ${\ displaystyle 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.}$
- We continue to calculate the coefficients $P_{k},~Q_{k}~r_{k}$ ${\ displaystyle P_ {k}, ~ Q_ {k} ~ r_ {k}}$ until we find Q_k, which is a full square. This should happen with some $k .$ ${\ displaystyle k.}$ Let be $Q_{k}=d^{2}$ ${\ displaystyle Q_ {k} = d ^ {2}}$ for the whole $d>0.$ ${\ displaystyle d> 0.}$ Let's move on to the next cycle.

Second cycle.
- start the cycle of computing new parameters $P_{j}^{\prime },~Q_{j}^{\prime },~r_{j}^{\prime }.$ ${\ displaystyle P_ {j} ^ {\ prime}, ~ Q_ {j} ^ {\ prime}, ~ r_ {j} ^ {\ prime}.}$ The formulas for the implementation of the second cycle will remain the same as before. Only the initial parameter values will change $P^{\prime },~Q^{\prime },~r^{\prime }:$ ${\ displaystyle P ^ {\ prime}, ~ Q ^ {\ prime}, ~ r ^ {\ prime}:}$
- $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}^{\prime }=(N-P_{1}^{\prime 2})/Q_{0}^{\prime }.$ ${\ displaystyle 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} ^ {\ prime} = (N-P_ {1} ^ {\ prime 2}) / Q_ {0} ^ {\ prime}.}$
- The calculation should continue until two consecutive values $P_{j}^{\prime },~P_{j+1}^{\prime }$ ${\ displaystyle P_ {j} ^ {\ prime}, ~ P_ {j + 1} ^ {\ prime}}$ will not be equal. Then, the value $Q_{j}$ ${\ displaystyle Q_ {j}}$ will give the desired divisor of the number $n .$ ${\ displaystyle n.}$ The description of the Shanks algorithm is complete.

As already mentioned, this is not the only implementation of this algorithm. Implementations of the algorithm can also be found here ^[8]

Example of factorization of a number

We apply this method to factorize a number $N=22117019$ ${\ displaystyle N = 22117019}$ ^[eight]

Cycle number 1
$F_{i}$ ${\ displaystyle F_ {i}}$
$i$ ${\ displaystyle i}$	$(-1)^{i-1}Q_{i-1}$ ${\ displaystyle (-1) ^ {i-1} Q_ {i-1}}$	$2\cdot P_{i}$ ${\ displaystyle 2 \ cdot P_ {i}}$	$(-1)^{i}Q_{i}$ ${\ displaystyle (-1) ^ {i} Q_ {i}}$
$0$ ${\ displaystyle 0}$	$-8215$ ${\ displaystyle -8215}$	$2\cdot 4702$ ${\ displaystyle 2 \ cdot 4702}$	$one$ ${\ displaystyle 1}$
$one$ ${\ displaystyle 1}$	$one$ ${\ displaystyle 1}$	$2\cdot 4702$ ${\ displaystyle 2 \ cdot 4702}$	$-8215$ ${\ displaystyle -8215}$
$2$ ${\ displaystyle 2}$	$-8215$ ${\ displaystyle -8215}$	$2\cdot 3513$ ${\ displaystyle 2 \ cdot 3513}$	$1190$ ${\ displaystyle 1190}$
$3$ ${\ displaystyle 3}$	$1190$ ${\ displaystyle 1190}$	$2\cdot 3627$ ${\ displaystyle 2 \ cdot 3627}$	$-7531$ ${\ displaystyle -7531}$
$four$ ${\ displaystyle 4}$	$-7531$ ${\ displaystyle -7531}$	$2\cdot 3904$ ${\ displaystyle 2 \ cdot 3904}$	$913$ ${\ displaystyle 913}$
$five$ ${\ displaystyle 5}$	$913$ ${\ displaystyle 913}$	$2\cdot 4313$ ${\ displaystyle 2 \ cdot 4313}$	$-3850$ ${\ displaystyle -3850}$
$6$ ${\ displaystyle 6}$	$-3850$ ${\ displaystyle -3850}$	$2\cdot 3387$ ${\ displaystyle 2 \ cdot 3387}$	$2765$ ${\ displaystyle 2765}$
$7$ ${\ displaystyle 7}$	$2765$ ${\ displaystyle 2765}$	$2\cdot 2143$ ${\ displaystyle 2 \ cdot 2143}$	$-6338$ ${\ displaystyle -6338}$
$eight$ ${\ displaystyle 8}$	$-6338$ ${\ displaystyle -6338}$	$2\cdot 4195$ ${\ displaystyle 2 \ cdot 4195}$	$713$ ${\ displaystyle 713}$
$9$ ${\ displaystyle 9}$	$713$ ${\ displaystyle 713}$	$2\cdot 4361$ ${\ displaystyle 2 \ cdot 4361}$	$-4346$ ${\ displaystyle -4346}$
$ten$ ${\ displaystyle 10}$	$-4346$ ${\ displaystyle -4346}$	$2\cdot 4331$ ${\ displaystyle 2 \ cdot 4331}$	$773$ ${\ displaystyle 773}$
$eleven$ ${\ displaystyle 11}$	$773$ ${\ displaystyle 773}$	$2\cdot 4172$ ${\ displaystyle 2 \ cdot 4172}$	$-6095$ ${\ displaystyle -6095}$
$12$ ${\ displaystyle 12}$	$-6095$ ${\ displaystyle -6095}$	$2\cdot 1923$ ${\ displaystyle 2 \ cdot 1923}$	$3022$ ${\ displaystyle 3022}$
$13$ ${\ displaystyle 13}$	$3022$ ${\ displaystyle 3022}$	$2\cdot 4121$ ${\ displaystyle 2 \ cdot 4121}$	$-1699$ ${\ displaystyle -1699}$
$14$ ${\ displaystyle 14}$	$-1699$ ${\ displaystyle -1699}$	$2\cdot 4374$ ${\ displaystyle 2 \ cdot 4374}$	$1757$ ${\ displaystyle 1757}$
$15$ ${\ displaystyle 15}$	$1757$ ${\ displaystyle 1757}$	$2\cdot 4411$ ${\ displaystyle 2 \ cdot 4411}$	$-1514$ ${\ displaystyle -1514}$
$sixteen$ ${\ displaystyle 16}$	$-1514$ ${\ displaystyle -1514}$	$2\cdot 4673$ ${\ displaystyle 2 \ cdot 4673}$	$185$ ${\ displaystyle 185}$
$17$ ${\ displaystyle 17}$	$185$ ${\ displaystyle 185}$	$2\cdot 4577$ ${\ displaystyle 2 \ cdot 4577}$	$-6314$ ${\ displaystyle -6314}$
$18$ ${\ displaystyle 18}$	$-6314$ ${\ displaystyle -6314}$	$2\cdot 1737$ ${\ displaystyle 2 \ cdot 1737}$	$3025$ ${\ displaystyle 3025}$

Cycle number 2
$G_{i}$ ${\ displaystyle G_ {i}}$
$i$ ${\ displaystyle i}$	$(-1)^{i-1}Q_{i-1}^{\prime }$ ${\ displaystyle (-1) ^ {i-1} Q_ {i-1} ^ {\ prime}}$	$2\cdot P_{i}^{\prime }$ ${\ displaystyle 2 \ cdot P_ {i} ^ {\ prime}}$	$(-1)^{i}Q_{i}^{\prime }$ ${\ displaystyle (-1) ^ {i} Q_ {i} ^ {\ prime}}$
$0$ ${\ displaystyle 0}$	$-55$ ${\ displaystyle -55}$	$2\cdot 4652$ ${\ displaystyle 2 \ cdot 4652}$	$8653$ ${\ displaystyle 8653}$
$one$ ${\ displaystyle 1}$	$8653$ ${\ displaystyle 8653}$	$2\cdot 4001$ ${\ displaystyle 2 \ cdot 4001}$	$-706$ ${\ displaystyle -706}$
$2$ ${\ displaystyle 2}$	$-706$ ${\ displaystyle -706}$	$2\cdot 4471$ ${\ displaystyle 2 \ cdot 4471}$	$3013$ ${\ displaystyle 3013}$
$3$ ${\ displaystyle 3}$	$3013$ ${\ displaystyle 3013}$	$2\cdot 4568$ ${\ displaystyle 2 \ cdot 4568}$	$-415$ ${\ displaystyle -415}$
$four$ ${\ displaystyle 4}$	$-415$ ${\ displaystyle -415}$	$2\cdot 4562$ ${\ displaystyle 2 \ cdot 4562}$	$3145$ ${\ displaystyle 3145}$
$five$ ${\ displaystyle 5}$	$3145$ ${\ displaystyle 3145}$	$2\cdot 1728$ ${\ displaystyle 2 \ cdot 1728}$	$-6083$ ${\ displaystyle -6083}$
$6$ ${\ displaystyle 6}$	$-6083$ ${\ displaystyle -6083}$	$2\cdot 4355$ ${\ displaystyle 2 \ cdot 4355}$	$518$ ${\ displaystyle 518}$
$7$ ${\ displaystyle 7}$	$518$ ${\ displaystyle 518}$	$2\cdot 4451$ ${\ displaystyle 2 \ cdot 4451}$	$-4451$ ${\ displaystyle -4451}$
$eight$ ${\ displaystyle 8}$	$-4451$ ${\ displaystyle -4451}$	$2\cdot 4451$ ${\ displaystyle 2 \ cdot 4451}$	$518$ ${\ displaystyle 518}$

Now you can see in the second cycle that $P_{7}^{\prime }=P_{8}^{\prime }.$ ${\ displaystyle P_ {7} ^ {\ prime} = P_ {8} ^ {\ prime}.}$ Hence the number $N=22117019=4451\cdot 4969.$ ${\ displaystyle N = 22117019 = 4451 \ cdot 4969.}$

Applications

This algorithm is used in many implementations of NFS and QS to factorize small auxiliary numbers that occur when factorizing a large integer. In any case, SQUFOF is mainly used as an auxiliary algorithm in more powerful factorization algorithms and, therefore, SQUFOF will usually be used to factorize numbers of modest sizes that do not have small prime divisors. Such numbers are usually the product of a small number of different primes. ^[8] .

Notes

↑ More details about the history of this method and its relation to the continuous fraction method can be found in the article by J. Gover, SS Wagstaff.
↑ Yike Guo, 1999 , High Performance Data Mining: Scaling Algorithms, Applications and Systems ..
↑ ¹ ² Hans Riesel, 1994 , Prime Numbers and Computer Methods for Factorization. Birkhauser, second edition.
↑ Henri Cohen, 1996 , A Course in Computational Algebraic Number Theory ..
↑ DA Buell, 1989 , Binary Quadratic Forms.
↑ Samuel S. Wagstaff Jr., 2003 , Cryptanalysis of Number Theoretic Ciphers.
↑ For example, SQUARE FORM FACTORIZATION JASON E. GOWER AND SAMUEL S. WAGSTAFF, JR. Assumption 4.12. on page 20, Assumption 4.5 on page 16, also in proving theorems on the complexity of the algorithm, etc.
↑ ¹ ² ³ ⁴ ⁵ SQUARE FORM FACTORIZATION, 2003 , SQUARE FORM FACTORIZATION.
↑ ¹ ² Vasilenko, 2003 , Number-theoretic algorithms in cryptography.
↑ Ishmukhametov, 2011 , Methods of factorization of natural numbers: Textbook.
↑ ¹ ² Ishmukhametov, 2011 , Methods of factorization of natural numbers: Textbook p. 79-80.

Literature

Vasilenko O. N. Number-theoretic algorithms in cryptography . - Moscow: ICMMO, 2003 .-- S. 75 - 76. - 328 p. - ISBN 5-94057-103-4 . Archived January 27, 2007 on the Wayback Machine
Ishmukhametov Sh. T. Methods of factorization of natural numbers: Textbook . - Kazan: Kazan University, 2011 .-- S. 74 - 82. - 190 p.
DA Buell. Binary Quadratic Forms . - New York: Springer-Verlag, 1989 .-- S. 197 - 199. - ISBN 0-387-97037-1 .
Hans Riesel. Prime Numbers and Computer Methods for Factorization. Birkhauser, second edition. - Sweden: Birkhauser, 1994. - S. p. 186 - 192. - ISBN 978-0-8176-8297-2 .
Henri Cohen. A Course in Computational Algebraic Number Theory .. - Springer-Verlag, 1996. - S. 433 - 437. - ISBN 3-540-55640-0 .
Jason E. Gower and Samuel S. Wagstaff, JR. SQUARE FORM FACTORIZATION . - Moscow: MCLMO, 2003 .-- S. 1-16, 35-36. - 38 p. - ISBN 5-94057-103-4 .
Samuel S. Wagstaff Jr. Cryptanalysis of Number Theoretic Ciphers. - CRC Press, 2003. - ISBN 978-1584881537 .
Yike Guo, RL Grossman. High Performance Data Mining: Scaling Algorithms, Applications and Systems .. - Kluwer Academic Publishers, 1999 .-- S. 111. - ISBN 0-7923-7745-1 .