YAFU's Homepage
Yet Another Factorization Utility
[Last updated: 10/6/11]
News
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 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 and NFS) routine can be multi-threaded. I've seen C90's factored in less than 4 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, SIQS, and GNFS in a completely automated fashion. This program is the fastest way to factor a general number less than 90 to 100 digits that I am aware of. It can also complete factorizations up to 150 digits or so in a completely automated fashion using the best publically available implementations (msieve, ggnfs) of the best algorithms for that task.
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.
Links
Other things I think are interesting:
If you have questions/comments, let me know
bbuhrow (I think you know what goes here) gmail (and here) com
|
|
