Sorry, an error occurred while loading the content.

## 5077Re: [PrimeNumbers] Fermat Factoring with First Digits

Expand Messages
• Feb 3, 2002
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