Square form factorization: Difference between revisions

Line 1:

Line 6:

[[wp:Daniel_Shanks|Daniel Shanks]]'s Square Form Factorization [[wp:Shanks%27s_square_forms_factorization|(SquFoF)]].

Invented around 1975, ''‘On a 32-bit computer, SquFoF is the clear champion factoring algorithm''

''for numbers between 1010 and 1018, and will likely remain so.’''

An integral [[wp:Binary_quadratic_form|binary quadratic form]] is a polynomial

{{math|''f''(''x,y'') = ''ax2'' + ''bxy'' + ''cy2''}}

with integer coefficients and discriminant {{math|''D'' = ''b2'' – ''4ac''}}.

For each positive discriminant there are ~~nearly always~~ multiple forms {{math|(''a, b, c'')}}.

For each positive discriminant there are multiple forms {{math|(''a, b, c'')}}.

The next form in a periodic sequence (cycle) of adjacent forms is found by applying a reduction operator ~~''rho''.~~

The next form in a periodic sequence (cycle) of adjacent forms is found by applying a reduction operator

It is a variant of Euclid's algorithm for finding the continued fraction of a square root. ~~Using~~

''rho'', essentially a variant of Euclid's algorithm for finding the continued fraction of a square root.

{{math|floor(''√N'')}}, rho constructs a ''principal form''

Using {{math|floor(''√N'')}}, rho constructs a ''principal form''

{{math|(''1, b, c'')}} with {{math|''D'' = ''4N''}}.

SquFoF ~~works~~ ~~because~~ ~~there~~ ~~are~~ cycles containing ''ambiguous forms'', with the property that ''a'' divides ''b''.

SquFoF is based on the existence of cycles containing ''ambiguous forms'', with the property that ''a'' divides ''b''.

They come in pairs of associated forms {{math|(''a, b, c'') and (''c, b, a'')}}, ~~easy~~ to ~~spot and obviously called~~

They come in pairs of associated forms {{math|(''a, b, c'') and (''c, b, a'')}} called symmetry points.

~~symmetry points.~~ If an ambiguous form is found (there is one for each divisor of D), write the discriminant as

If an ambiguous form is found (there is one for each divisor of D), write the discriminant as

{{math|(''ak'')''2'' – ''4ac'' = ''a''(''a·k2'' – ''4c'') = ''4N''}}

and (if a is not equal to 1 or 2) N is split.

Shanks used ''square forms'' to jump to a random ambiguous cycle. Fact: if a form on an ambiguous cycle

Shanks used ''square forms'' to jump to a random ambiguous cycle. Fact: if any form in an ambiguous cycle

is squared, that square form will always land in the principal cycle. Conversely, the square root of a

is squared, that square form will always land in the principal cycle. Conversely, the square root of any

form on the principal cycle lies in an ambiguous cycle. (Possibly the principal cycle itself).

form in the principal cycle lies in an ambiguous cycle. (Possibly the principal cycle itself).

A square form is easy to find: the last coefficient ''c'' is a perfect square. This happens about once

Line 39:

Line 36:

no roots land in the principal cycle itself and cases a = 1 or a = 2 do not happen.

Sometimes the cycle length is too short to find proper square ~~forms~~. This is fixed by running five instances

Sometimes the cycle length is too short to find a proper square form. This is fixed by running five instances

of SquFoF in parallel, with input N and 3, 5, 7, 11 times N; the discriminants then will have different periods.

(A ~~short~~ trial division loop acts as sentry). If N is prime or the cube of a prime, there are ~~only trivial~~ squares

(A trial division loop acts as sentry). If N is prime or the cube of a prime, there are improper squares only

and the program will duly report failure.

Line 69:

Line 66:

type arg

'~~SquFoF~~ arguments

'squfof arguments

as ulong m, f

as integer vb

Line 100:

Line 97:

dim shared N as ulongint

'the number to split

dim shared flag as integer

'signal to end all threads

Line 398:

Line 396:

</lang>

<pre>

N = 2501