Anonymous user
Talk:Square form factorization: Difference between revisions
Clearing some points
mNo edit summary |
(Clearing some points) |
||
Line 1:
Since most SquFoF solutions follow the
I will expose how it might fail to factor a composite number
and why it is better to stick to the original algorithm.
Below 50,000,000 these N do not split:
Line 41 ⟶ 42:
49531597}</nowiki>
The
won't factor, so more than 2^41 misses below 2^62.
Line 49 ⟶ 50:
Now look under the hood; m is the multiplier,
forms P# are
Each time, after just a few steps, the multiplier or some
trivial factor is
<nowiki>N = 4558849
Line 80 ⟶ 81:
A9 = ( 22, 14146,-5455)</nowiki>
the last multiplier gives:
Line 99 ⟶ 100:
where the problem doesn't exist.
This brings us to Shanks's approach.
The last square form is saved and if a trivial factor is found we
[[Square_Form_Factorization#Classical_heuristic|''continue searching the principal cycle'']]:
<nowiki>N = 4558849
Line 131 ⟶ 133:
A7 = ( 3, 7392,-5377)</nowiki>
and back
is but two steps away:
<nowiki>P14 = (-1898, 7334, 11^2)
| |||