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

Re: [PrimeNumbers] trial division by addition

Expand Messages
  • Jack Brennen
    ... 1993, widely available ? I m looking at my copy of Riesel s Prime Numbers and Computer Methods for Factorization -- I have the second edition, which was
    Message 1 of 3 , May 4, 2007
    • 0 Attachment
      aldrich617 wrote:
      > This type of division runs much faster than the usual method
      > and may have made it a contender in 1993 for the swiftest
      > factoring method widely available.
      >

      1993, "widely available"?

      I'm looking at my copy of Riesel's "Prime Numbers and Computer
      Methods for Factorization" -- I have the second edition, which
      was published in 1994.

      It discusses a bunch of methods which are generally much
      faster than the method you mention. Pollard's rho algorithm
      comes to mind as one which is *easier to implement* than the
      method you describe, probably faster 99% of the time, and
      which was invented in 1975. Brent's variant which improved
      the performance was published in 1980.

      Your number factors on my laptop in about 2 milliseconds using
      the example implementation of Brent's variant which comes with
      PARI/GP.

      Jack
    Your message has been successfully submitted and would be delivered to recipients shortly.