5020Fermat Factoring with First Digits
- Feb 1, 2002Fermat's Factoring Algorithm with the first digits of the
factors known, can be done as on page 198 of Yan's book
(Number Theory for Computing) with a different starting value of k
k = Lower(Sqrt( n + (abc00...00)^2)) + 1
where a, b, c are the known first digits and Lower means
next smaller integer value.
For his exercise 2.3.3 with n = 278153 (= 349*797)
his k of 528 requires 45 steps, but with k = 565 requires
only 8 steps. This is obtained with abc00...00 = 200
where 200 = (700-300)/2.
Milton L. Brown
[Non-text portions of this message have been removed]
- Next post in topic >>