METHODS AND THEORY
This is it! Here is where you can learn about all the major factoring algorithms around, including some source code to boot. It is, of course, still being worked on, but for now...

A few names to drop are (with help from the sci.math FAQ):

NOTE: In run time notation, n is the number you wish to factor, and p is the largest prime factor of n.


  • Primitive division algorithm
    This is what you did in 1st grade...
    Theoretical runtime: O(exp(#of digits in n)) - not good

  • Euler's algorithm
    A tweaked around version of Fermat's Method.
    Theoretical runtime: O( unknown )

  • Shor's algorithm
    Uses group theory...
    Theo. runtime: O(exp(#of digits in n)) - also, not good

  • Shank's square form algorithm
    No clue on this one... yet...
    Theo. runtime: unknown

  • William's P+1 algorithm
    No clue on this one... yet...
    Theo. runtime: unknown

  • Pollard's P-1 algorithm
    Based on 'Fermats Little Theorem'
    Theo. runtime: O(q) (where q is largest factor of p-1) - "eh"

  • Pollard's rho algorithm
    Simple and very effective algorithm
    Theo. runtime: O(sqrt(p)) - not bad

  • Continued fraction algorithm
    Theo. runtime: O( exp(sqrt(2*ln(n)*ln(ln(n))) )

  • Class group method
    Theo. runtime: sub exponential

  • Fermat's algorithm
    You should understand this if you want to understand Dixon's alg.
    Theoretical runtime: O(exp(#of digits in n)) - not good

  • Dixon's random squares algorithm
    You need to understand this if you want to understand MPQS or NFS.
    Theo. runtime: sub exponential

  • Multiple polynomial quadratic sieve algorithm, or "MPQS"
    A supped up, hod rodded version of Dixon's algorithm...
    Theo. runtime: same as eliptic curve

  • Number field sieve, or "NFS"
    The hot algorithm of the 90's...
    Theo. runtime: O(exp(c*(ln(n)^1/3*ln(ln(n)^2/3))) - darn good

  • Eliptic curve algorithm, or "ECM"
    Used to be hip, now just a relic.
    Theo. runtime: O( exp(sqrt( ln(n)*ln(ln(n)) )) ) - good

  • Valles two-thirds algorithm
    Theo. runtime: sub exponential

  • Seysen's class group algorithm
    Theo. runtime: sub exponential
  • More to come...
    • Back to the factoring page
    Back to my home page
    Back to the pslc home page

    Paul Herman
    pherman@frenchfries.net

    Last Updated: May 23, 1997