--- Kermit Rose <kermit@...
> Hello everyone
> Over a year an a half ago I wondered how much improvement I could make
> on Fermat factoring, by using mod 8, 3, 5, 7, etc
> for more quickly finding difference of squares equal to the number to
> be factored.
I remember doing the same. I was sitting at an HPUX workstation at Nokia, so I
guess that was 6-7 years ago.
> Finally the algorithm for doing it came to me. I've written tentative
> code, but it still has a bug in it.
> In spite of this bug, I now realize that the screening by small modulii
> does not help significantly.
> I should go back to the textbooks for more inspiration on some of the
> other factoring algorithms that have come to mind.
It's a constant factor speedup. See the 'Factoring with sieves' section in
Knuth. Which is basically an accelerated Fermat. I'm convinced it's possible to
implement faster than how Knuth suggests, but again, that would only be another
small constant factor speedup.
() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed
[stolen with permission from Daniel B. Cristofani]
Want to start your own business?
Learn how on Yahoo! Small Business.