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