Re: [PrimeNumbers] Using small moduli to filter in Fermat factoring
- View Source--- Kermit Rose <kermit@...> wrote:
> Hello everyoneI remember doing the same. I was sitting at an HPUX workstation at Nokia, so I
> 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.
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 theIt's a constant factor speedup. See the 'Factoring with sieves' section in
> other factoring algorithms that have come to mind.
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.