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.