What it is:
GGNFS is a GPL'd implementation of the General Number Field Sieve (GNFS)
for factoring integers.
Active development (by me, anyway) is stalled, as I haven't had time
to put into this for the last several years;
It has been used on SNFS numbers upto
180+ digits and general numbers upto 140. Some larger numbers have been done as
well, but there are issues in the software that make larger factorizations very
tricky at best. For the most part, the upper range in which GGNFS is pretty reliable
is probably upto about 150-160 digits for SNFS, 130-135 or so for general numbers.
It has bugs, it's almost
entirely documentation-free, and you might need some *NIX skills
to compile it,
but it is available.
What it is not (yet):
It is not a black box for factoring integers - you need to know a few things
about how the NFS works to use it. Having said that:
There is a Perl script for fire-and-forget operation on small-to-moderate
sized numbers (say, upto 120 digits or so for general numbers).
Jens Franke's lattice siever is included.
It is quite
fast, and easily puts 140-150 digit SNFS numbers in range for a single fast
machine (in several days or less).
I have done special numbers between 110 and 150 digits with it,
with a special c150 taking about 2 days on an Athlon XP 3200+.
The matrix code is not bad. It's a direct implementation of Montgomery's
block Lanczos algorithm, with no tricks or speed-ups. It still needs
some work and will admit much more optimization, but it's not bad
(assuming you have fast RAM).
The square root code is also not bad. It's an implementation of
Montgomery's fast square root, as described by Nguyen. There are still
a few details and bugs to be ironed out, but it works in most cases.
The nice thing here is that it's totally self-contained - I wrote the
integral basis code and the Buchmann-Lenstra code from scratch. This
means that you don't have to spend days trying how to figure out some
other libraries just to get this code compiled. (But compiling this
one is not completely trivial either, unless you happen to be on an
x86 Linux platform with reasonably recent gcc/gmp).
There is a native implementation of the Montgomery/Murphy polynomial selection,
but it still needs mucho work. It does seem to generate decent polynomials
for numbers upto around 130 digits or so (if you set the parameters
up right and wait long enough). But there are still many bugs in it
and many serious speed-ups possible.
The Kleinjung/Franke polynomial selection code is included for finding
good degree (5,1) polynomial pairs with a non-linear monic polynomial.
In its current state, GGNFS will not factor anything extraordinarily
large (i.e., it will not do a 160 digit general number). There are
some very specific issues in the code that need to be worked out before
numbers of that size will be factored. These issues are obviously nontrivial,
or I would have already taken care of them;
At the moment, I am not actively
working on the software, so it may be some time before I get to those
issues (if ever). Please don't send me an email asking what needs to be
fixed - you can discover the issues one at a time by yourself by
attempting to factor successively larger and larger numbers (say, 140,145,150,...),
until you encounter the problems. Suffice it to say, these problems are
not the result of a bug here or a bug here which can be fixed in an afternoon -
fixing them will require
a massive overhaul of several data structures and underlying algorithms.
Here is the latest released source code (Note: There are some
known potential problems when linked against GMP 4.2 or 4.2.1.
In particular, if you experience crashes in the `sqrt' program,
you might want to make sure that you are not linking against
one of these two versions. Thanks to Paul Zimmermann for tracking
this bug down. I hope to put a workaround in GGNFS
sometime soon).
ggnfs-0.77.0.tar.gz (5/3/05).
Here is the most recent, not-necessarily working,
code:
devel
There is a Yahoo! Group
for GGNFS users at
www.groups.yahoo.com/group/ggnfs. If you have questions or comments
about the software, your best bet is to first scan messages there to see
if the question [issue] has been asked [addressed]. If not, ask it there.
Emailing me directly should only be done as a last resort, and only if
you are submitting a bugfix or patch.
Please Note: What little documentation there is for GGNFS is now horribly
out of date. If you need help, you might try the group mentioned above.