SIMPQS

Here you will find a fast implementation of the self initialising quadratic sieve (SIMPQS), for factoring large integers, written by William Hart.

Jason P's msieve is a little faster (as of msieve v 1.19), but it may be possible to be competitive with it in future versions (at msieve 1.18 we were actually slightly faster at some factorisations on certain platforms).

The large prime variant has now been implemented.

SIMPQS has been released under the GNU Public License.

---------------------------------------------------------------------------------------

7 Oct 2006:

SIMPQS version 1.0 released

Version 1.01 fixes a small bug which prevents numbers of around 75 digits factoring. The sieve stage was also universally sped up very slightly.

11 Feb 2007:

Version 1.1 The linear algebra stage now uses Jason Papadopoulous' block Lanczos implementation. Many thanks to Jason P. for letting me use it in SIMPQS. This dramatically speeds up large factorizations. The sieve now compiles on a MAC and some build issues have been corrected for certain platforms. Duplicate factors are now only returned once.

15 Apr 2007:

Version 2.0 The sieve now makes use of the large prime variant (the large prime code was forked from Pari/GP). It has been sped up considerably, and in particular is scorchingly fast on an Athlon. A nasty segfault problem which could occur for some large factorisations has been fixed. The large prime code is file based. At this stage only one version of the sieve can be run at once.

---------------------------------------------------------------------------------------

Compiling SIMPQS:

SIMPQS is distributed in source form. The sieve depends on GMP (as GMP improves, so does SIMPQS). You may need to edit the makefile in SIMPQS to tell it where to find GMP. The lines you need to edit (if it does not find GMP) are:

LIBS = -L"/usr/lib" -lgmp

CXXINCS = -I"/usr/include"

To compile SIMPQS under linux, unix or cygwin, place all the files in a directory, edit the makefile as above to point to your GMP installation, type make and SIMPQS should compile. It currently compiles as a standalone program.

Notes:

Currently SIMPQS refuses to factor integers below 40 digits, since the full quadratic sieve is not the optimal algorithm in this range.

Please notify the maintainer of any bugs or build issues: hart_wb {at_thingy} yahoo.com. Also, if you use the code in any other open source projects, the maintainer would very much like to hear about it.

SIMPQS is part of the FLINT library Fast Library for Number Theory maintained by David Harvey (Harvard) and William Hart (Warwick). SIMPQS is accessible by means of the qsieve command and is available as part of SAGE, which is maintained by William Stein of the University of Washington.