Anonymous user
Square form factorization: Difference between revisions
m
Tightened the intro
m (→{{header|Wren}}: Added a word to the preamble.) |
m (Tightened the intro) |
||
Line 1:
{{
Line 6:
[[wp:Daniel_Shanks|Daniel Shanks]]'s Square Form Factorization [[wp:Shanks%27s_square_forms_factorization|(SquFoF)]].
An integral [[wp:Binary_quadratic_form|binary quadratic form]] is a polynomial
{{math|''f''(''x,y'') = ''ax<sup>2</sup>'' + ''bxy'' + ''cy<sup>2</sup>''}}
with integer coefficients and discriminant {{math|''D'' = ''b<sup>2</sup>'' – ''4ac''}}.
For each positive discriminant there are
The next form in a periodic sequence (cycle) of adjacent forms is found by applying a reduction operator
Using {{math|floor(''√N'')}}, rho constructs a ''principal form''
{{math|(''1, b, c'')}} with {{math|''D'' = ''4N''}}.
SquFoF
They come in pairs of associated forms {{math|(''a, b, c'') and (''c, b, a'')}}
{{math|(''ak'')''<sup>2</sup>'' – ''4ac'' = ''a''(''a·k<sup>2</sup>'' – ''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
is squared, that square form will always land in the principal cycle. Conversely, the square root of
form
A square form is easy to find: the last coefficient ''c'' is a perfect square. This happens about once
Line 39 ⟶ 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 a proper square
of SquFoF in parallel, with input N and 3, 5, 7, 11 times N; the discriminants then will have different periods.
(A
and the program will duly report failure.
Line 69 ⟶ 66:
type arg
'
as ulong m, f
as integer vb
Line 100 ⟶ 97:
dim shared N as ulongint
'the number to split
dim shared flag as integer
'signal to end all threads
Line 398 ⟶ 396:
</lang>
{{out|
<pre>
N = 2501
| |||