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

Re: [PrimeNumbers] Using small moduli to filter in Fermat factoring

Expand Messages
  • Phil Carmody
    ... I remember doing the same. I was sitting at an HPUX workstation at Nokia, so I guess that was 6-7 years ago. ... It s a constant factor speedup. See the
    Message 1 of 2 , Nov 10, 2006
    View Source
    • 0 Attachment
      --- Kermit Rose <kermit@...> wrote:
      > 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.

      Phil

      () 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.
      http://smallbusiness.yahoo.com/r-index
    Your message has been successfully submitted and would be delivered to recipients shortly.