Chris Monico's
Homepage
Courses
Research
Software
About me
Main

TTU Math & Stat
TTU
GGNFS - A Number Field Sieve implementation

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.


    Romanian translation by Maxim Petrenko at Software blog



    This page has been viewed

    time since 2/12/04.