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

5077Re: [PrimeNumbers] Fermat Factoring with First Digits

Expand Messages
  • Andy Steward
    Feb 3, 2002
    • 0 Attachment
      Milton Brown wrote:

      >The algorithm is from page 198 of Yan's book, reproduced below
      >I just modified it to start with a different value of k based on knowing
      >the first digits of the two factors:
      ^^^^^^^^^^^^^^^^

      [snip]

      >I have implemented this, and used k <= lower(sqrt(n+(b-a)^2))+1
      ^^^
      >where b = b1 b2 b3 ... 000 first digits of larger factor
      ^^^^^^^
      >and a = a1 a2 a3 ... 000 first digits of smaller factor.
      ^^^^^^^
      >This is much faster, and faster with the more first digits you know.

      This requires knowing _how_many_digits_ are in $b and $a, not just
      the leading ones. (I'm sure others have noticed this, but I don't
      recall anyone pointing it out.)

      If Milton's Method provides this essential info, then why not iterate
      it in a sequence of well-chosen bases, rather than just 10. (This
      was abortively suggested in connection with the CRT, AFAIR.)

      IF the previous condition holds, you could choose a base such that a
      power of it was about in the middle of the range for one of $a or $b
      constrained by all previous iterations and find the number of digits
      in that base (and maybe some of the leading ones, but that would be
      a bonus).

      THEN you would have a factorisation algorithm that approximated a
      binary search, i.e. O(log(N)). That would be a breakthrough ;-)
      (You could use approximate logs to avoid too much faffing about.)

      Why do I think that the Milton Method probably falls down here?

      I would LOVE to be wrong.

      Andy
    • Show all 11 messages in this topic