Most of the factoring source code here was written by Ami Fischman and myself. We started futzing around in 1995 while giving a seminar on eliptic curves. The code here is not at all optimized - it is here for illustrative purposes, for you to LEARN. We'd still like to shake out some bugs, so please mail us with code, suggestions for improvement, or pointers to other places for info if ya got 'em.

The code below uses type Integer for its int type. I suggest you use the gmp library with the Integer class that I wrote (see below), but you can use any class you wish.

• Factoring Code
• Related Code

• Basic.cc
  Factors integers using the "try every number before sqrt(n)" algorhithm. Not very efficient at all. The better factoring programs use this method to clear out all the small factors first, and then use a more powerful method, like Pollard's 'P-1'...
  Requires an Integer Class for the GMP library
  
  
• Fermat.cc
  Fermat's algorithm is pretty good when the number you wish to factor has two factors very near to sqrt(n). Otherwise, it is just as slow as the basic division algorithm.
  Requires an Integer Class for the GMP library
  
  
• Shor.cc
  A simple algorithm based on looking at the size of certain Groups mod n. It's only justification for existence is that it (theoreticaly) runs great on quantum computers . . . but stinks on "normal computers". Only here for illustrative purposes.
  Requires an Integer Class for the GMP library
  
  
• Shanks.cc
  Shank's square form method. I don't know much about this one. It's OK.
  Requires an Integer Class for the GMP library
  
  
• Williams_p1.cc
  William's 'P+1' method. I don't know much about this one either, but it isn't too bad.
  Requires an Integer Class for the GMP library
  
  
• Pollard_p1.cc
  Called "Pollard's 'P-1' method" and is based upon Fermat's Little Theorem. Not a bad little algorithm.
  Requires an Integer Class for the GMP library
  
  
• Pollard_rho.cc
  Called "The Pollard rho algorithm" and is also based upon Fermat's Little Theorem. Faster than P-1. Very nice for general use (small numbers).
  Requires an Integer Class for the GMP library
  
  
• Lenstra.cc
  Factors integers based on H.W. Lenstra's algorhithm using eliptic curves. This method hit the big time in the early 90's, but other more sophisticated routines have since then eclipsed this fella.
  Requires an Integer Class for the GMP library
  
  
• Dixon.cc
  A "modular arithmetic" extension of Fermat's idea. Not to swift, but the idea is fundamental if you wish to understand how the MPQS and NFS algorithms work. This example here is not quite finished.
  Requires an Integer Class for the GMP library
  
  

• gmp-2.0.2.tar.gz
  Inorder to factor very large integers, you need a library to give you big integers. This C library allows you to play with arbitrarily large integers, and is supported by the GNU project. When downloading, you should get this library from a GNU mirror site near you.
  
  
• Integer.h, and Integer.cc
  This is a C++ Integer class that I threw together to make the gmp library work like normal arithmetic. It lets you play with big integers just like you would with (int) or (long int). There is also a .tar.gz version available that includes small Makefile and demo test code.
  Requires the GMP library from GNU.
  
  
• Miracl Package from Shamus Software Ltd can do multiple precision arithmatic as well.
  
  
• PGP Related Source Code
  If you are doing any playing around with PGP packets, public / private exponents, large numbers, or whatever, be sure to check out these little code snippets and utilities to help you play around.