Talk:Square form factorization: Difference between revisions
Content added Content deleted
(A hidden frailty) |
(Wrong example removed, but the issue still needs investigation.) |
||
Line 1: | Line 1: | ||
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: |
|||
<nowiki>N = 569537 |
|||
f = 239 N/f = 2383</nowiki> |
|||
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: |
|||
<nowiki>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</nowiki> |
|||
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: |
|||
<nowiki>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)</nowiki> |
|||
That same useless 3 again; but at this point |
|||
a proper square is just a stone's throw away: |
|||
<nowiki>P38 = (-1019, 1120, 37^2) |
|||
A1 = ( 37, 2600,-503) |
|||
A27 = ( 478, 2390,-587) |
|||
f = 239 N/f = 2383</nowiki> |
|||
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: |
|||
<nowiki>L = 2 * sqrtl( 2*s ); |
|||
B = 3 * L;</nowiki> |
|||
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. |