Intro

This code is the result of several's years effort to learn more about integer factorization, arbitrary precision arithmetic, C programming, memory and cpu speed optimizations. It's freely available to anyone that wants to use it. I provide binaries in several popular platforms/OSs below, or get the code and compile yourself. I'm interested to know about it if you compile and use it on something other than what I provide binaries for. My contact info is below.

I've implemented several versions of the quadratic sieve: the self initializing quadratic sieve (SIQS), multiple polynomial quadratic sieve (MPQS), and the original quadratic sieve (QS), as well as other factorization algorithms including: ECM, P-1, P+1, Shanks' squfof, pollard's rho (with Brent's improvement), and Fermat's algorithm. Many of these factorization algorithms require access to many small prime numbers, thus the library also contains a rather fast implementation of the sieve of Eratosthenes. It's all structured as a arbitrary precision calculator, like bc or pari/gp.

YAFU's SIQS implementation is the fastest publicly available quadratic sieve implementation. The SIQS routine can also be multi-threaded. I've seen 90 digit hard composites factored in less than 4 minutes on an 8 core box. Hard 100 digit composites take less than an hour on a modern quad core.

YAFU also implements a completely automated number field sieve (NFS) that is multi-threaded in all of the major stages of the algorithm (polynomial selection, sieving, and linear algebra). General or (as of version 1.34) special inputs are factored in a fire-and-forget automated way. The NFS implementation in YAFU is nearly all the work of others. I just wrote the automation and some of the multi-threading bits. It is enabled by the excellent public domain program msieve, and also by the lattice sievers of Franke and Kleinjung.

As of version 1.32, YAFU also has one of the fastest sieve of Eratosthenes implementations I am aware of for modern 64 bit processors. Kim Walisch's primesieve is faster in most cases, but YAFU is its closest competitor. Dan Bernstein's Primegen is also a fast prime sieve with asymptotic complexity lower than the sieve of Eratosthenes (via the sieve of Atkin), but slower in practice.

There are already several excellent utilities for factoring integers out there, so I'm calling the library YAFU, for Yet Another Factorization Utility. YAFU has a general purpose function, factor, which tries to reduce a number to its prime factors using an intelligent combination of all of the implemented factorization methods in a completely automated fashion; it is the fastest way to factor a general number less than 150 digits or so. (Note: 150 digit inputs will still take a week or more to complete.)

If you've read this far and aren't already aware of it, I encourage you to visit the factoring forum at mersenneforum.org. There is a discussion thread for YAFU there, as well as for msieve.

Happy factoring!

Links

Sums of Prime Squares

Other Factorization code

Aliquot Sequences

CUDA implementation of the Sieve of Erathosthenes

If you have questions/comments, let me know

bbuhrow (I think you know what goes here) gmail (and here) com