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

5054Fermat Factoring with First Digits

Expand Messages
  • Milton Brown
    Feb 2, 2002
    • 0 Attachment
      Consider Yan's RSA example on page 318
      n = 63978486879527143858831415041
      if you obtain the first 7 digits of each factor as
      p = 1452951... and
      q = 4403346... yielding
      delta/2 = 1475197...

      Spliting this value of k to 14751970...+ and 14751975...+
      between two 1 gHz machines, enables the complete
      factorization to be done on the second machine with
      y = sqrt(21762078295163316989407257600)
      to be done in 6.75 minutes.

      (The notation corresponds to Yan's Fermat Factoring p. 198)

      For anyone interested, I can provide additional documentation.
      Contact me directly.

      Milton L. Brown
      miltbrown@...

      ----- Original Message -----
      From: "Milton Brown" <miltbrown@...>
      To: <primenumbers@yahoogroups.com>
      Cc: "Milton Brown" <miltbrown@...>
      Sent: Friday, February 01, 2002 12:13 AM
      Subject: [PrimeNumbers] Fermat Factoring with First Digits


      > 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]
      >
      >
      >
      > Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
      > The Prime Pages : http://www.primepages.org
      >
      >
      >
      > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
      >
      >
    • Show all 11 messages in this topic