Fermat'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

miltbrown@...
[Non-text portions of this message have been removed]