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

5020Fermat Factoring with First Digits

Expand Messages
  • Milton Brown
    Feb 1, 2002
    • 0 Attachment
      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]
    • Show all 11 messages in this topic