Talk:Square form factorization

Since people use RC as a code quarry, and most SquFoF solutions follow the example c-code on Wp, I should point out a defect.

A telling example:

N = 569537
f = 239  N/f = 2383

We have our factor, so everything seems fine.

But is it? Take a look under the hood; m is the multiplier, forms P# are in the principal and A# in an ambiguous cycle.

Each time, after just a few steps, the multiplier or some trivial factor is returned and the principal cycle exited:

N = 569537
m = 1
P1 = ( 1, 1508,-1021)
P14 = (-1021, 1508, 1)

A short cycle, so no luck. Use the multipliers:

m = 3
P1 = ( 1, 2614,-362)
P26 = (-890, 922, 41^2)
A1 = ( 41, 2562,-1650)
A18 = (-3, 2610, 1862)
m = 5
P1 = ( 1, 3374,-1716)
P10 = (-2149, 2616, 23^2)
A1 = ( 23, 3352,-1683)
A4 = (-5, 3370, 1692)
m = 7
P1 = ( 1, 3992,-2743)
P68 = (-1643, 3228, 29^2)
A1 = ( 29, 3982,-782)
A33 = ( 1, 3992,-2743)
m = 11
P1 = ( 1, 5004,-4903)
P6 = (-1107, 3680, 51^2)
A1 = ( 51, 4904,-4953)
A3 = ( 2, 5002,-4953)
m = 15
P1 = ( 1, 5844,-4971)
P26 = (-2255, 4360, 41^2)
A1 = ( 41, 5836,-691)
A12 = (-6, 5838, 3749)
m = 21
P1 = ( 1, 6916,-2513)
P28 = (-5957, 5936, 23^2)
A1 = ( 23, 6902,-2212)
A12 = (-3, 6912, 5447)
m = 33
P1 = ( 1, 8670,-2496)
P14 = (-6512, 6578, 35^2)
A1 = ( 35, 8608,-7723)
A6 = (-1, 8670, 2496)
m = 35
P1 = ( 1, 8928,-6499)
P10 = (-146, 8642, 93^2)
A1 = ( 93, 8828,-4843)
A6 = (-7, 8918, 7302)
m = 55
P1 = ( 1, 11192,-9319)
P28 = (-4054, 7246, 67^2)
A1 = ( 67, 11132,-5137)
A15 = ( 22, 11154,-10073)
m = 77
P1 = ( 1, 13244,-3465)
P8 = (-4716, 11714, 45^2)
A1 = ( 45, 13244,-77)
A2 = (-77, 13244, 45)
m = 105
P1 = ( 1, 15466,-2096)
P18 = (-4856, 14258, 43^2)
A1 = ( 43, 15462,-768)
A8 = (-5, 15460, 9697)
m = 165
P1 = ( 1, 19386,-19356)
P8 = (-7361, 18644, 31^2)
A1 = ( 31, 19326,-19356)
A3 = ( 1, 19386,-19356)
m = 231
P1 = ( 1, 22940,-2147)
P4 = (-7446, 20382, 61^2)
A1 = ( 61, 22822,-22166)
A3 = ( 717, 21510,-22166)
f = 239  N/f = 2383

Finally, 3*7*11 works. For such a tiny N, this odd behaviour should raise suspicion.

Observe what happens if the last square form is saved and we continue searching the principal cycle:

N = 569537
m = 1
P1 = ( 1, 1508,-1021)
P14 = (-1021, 1508, 1)
m = 3
P1 = ( 1, 2614,-362)
P26 = (-890, 922, 41^2)
A1 = ( 41, 2562,-1650)
A18 = (-3, 2610, 1862)

That same useless 3 again; but at this point a proper square is just a stone's throw away:

P38 = (-1019, 1120, 37^2)
A1 = ( 37, 2600,-503)
A27 = ( 478, 2390,-587)
f = 239  N/f = 2383

Factor found, now using only 2 instead of 8 bits multiplier space. (This task can do without bigint's; for the reduction steps even 32 bits suffice).

To understand how the bug crept in, look at these statements from the example c-code:

L = 2 * sqrtl( 2*s );
B = 3 * L;

The ghost of Shanks's Queue lingers on in this spectral variable L, referenced once and never to be seen again: it's the Q-entry bound.

To make the code short & simple, it seems, the editor cut the queue, but didn't realize that absent a queue, SquFoF heuristic demands a return to the principal cycle if a square turns out to be improper.

But (happy conclusion) the fact that SquFoF finds a factor in spite of careless coding bears testimony to its strength.