kmGNFS - A General Number Field Sieve (GNFS) Implementation

 
 

A few words...


Welcome to the kmGNFS project. kmGNFS is an implementation of the General Number Field Sieve (GNFS) algorithm written in C++. Its development started in 2008 as part of the master thesis of Christos Bakogiannis and Nikolaos Karapanos.


kmGNFS is absolutely free software written in C++. It makes use of Victor Shoup’s NTL library. This means that you will have to install NTL on your system, in order to compile kmGNFS. Apart from this, kmGNFS uses mostly standard C++ code, and should compile fine on any Unix like system. It has been tested under Linux, FreeBSD and Mac OS X. The distributed version of kmGNFS uses MPI, and has been tested on an Open MPI environment.


kmGNFS is still pretty “young” and lacks many of the advanced features and algorithms that are used by state of the art implementations of GNFS. Such features include:

  1. •Factoring with two or four large primes

  2. •Lattice sieving

  3. •Use of bucket sort in sieving

  4. •Relation filtering strategy

  5. •Use of an advanced matrix reduction algorithm such as the block Lanczos method etc.


These optimizations are all planned for future releases of kmGNFS, hoping that we will find the required spare time to incorporate them in kmGNFS.


As an example factorization, we factored the following 60-digit number using kmGNFS:


171347248017422581339647672720789796161956165640387071960497

has the following factors:

351499192146543980092804727329

487475510174105833736777634193



Download...


Here you can download the source code of the initial release of kmGNFS. There are two versions, a sequential and a distributed one.

The distributed version is MPI aware, so that computation can be divided to multiple nodes of a cluster that supports MPI. It is assumed that the nodes of the cluster have access to a common filesystem, which is usually the case, and that kmGNFS gets executed from this filesystem. The steps that have been made parallel are: polynomial selection, sieving and square root. The rest of the algorithm (like factor bases setup and liner algebra) still remain sequential in the distributed version.

Each version comes as a set of Netbeans C++ projects. Of course, you don’t need the Netbeans IDE to compile or edit the sources. Makefiles are properly included. Type “make help” to see the available targets.

Unfortunately, for the moment, kmGNFS completely lacks any documentation, so you are on your own...!


Sequential version

Distributed (MPI) version