Loading ...
Sorry, an error occurred while loading the content.

5020Fermat Factoring with First Digits

Expand Messages
  • Milton Brown
    Feb 1, 2002
      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

      [Non-text portions of this message have been removed]
    • Show all 11 messages in this topic