YAFU

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 I know of, for just about any CPU, but especially for modern CPUs such as Intel Core2 and Nehalem, and AMD64 or opteron. The SIQS (and ECM) routine can be multi-threaded. I've seen C90's factored in about 6 minutes on an 8 core box.

As of version 1.19, YAFU also has one of the fastest sieve of Eratosthenes implementations I am aware of for modern 64 bit processors. Kim Walisch's Ecprime (or the newer primesieve) is competitive in many cases, and is faster for 32 bit systems. Dan Bernstein's Primegen is also a fast prime sieve with asymptotic complexity lower than the sieve of Eratosthenes (via the sieve of Atkin).

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 optimally reduce a number to its factors using a combination of all of the implemented methods. This method measures the elapsed time of several methods and strives for the optimum balance between ECM and SIQS in a completely automated fashion. I believe this program is the fastest way to factor a general number less than 85 to 90 digits, certainly less than 80 digits. The GNFS using msieve and optimized lattice sievers from ggnfs win over YAFU at about 90 digits.