Introduction
CADO-NFS is a complete implementation in C/C++ of the Number Field Sieve (NFS) algorithm for factoring integers. It consists in various programs corresponding to all the phases of the algorithm, and a general perl script that run them, possibly in parallel over a network of computers. CADO-NFS is distributed under the Gnu Lesser General Public License (LGPL) version 2.1 (or any later version).
The main authors are:
- Shi Bai
- Pierrick Gaudry
- Alexander Kruppa
- François Morain
- Emmanuel Thomé
- Paul Zimmermann
Other persons have contributed parts of the code, in current or in earlier revisions of CADO-NFS: Richard Brent, Jérémie Detrey, Andreas Enge, Nuno Franco, Jérome Milan, Lionel Muller, Thomas Prest.
News
| Date | Newsflash |
| 27-10-2011: | CADO-NFS 1.1 is now available (release notes) |
| 10-12-2010: | CADO-NFS 1.0 is now available. |
Download
- cado-nfs 1.1: cado-nfs-1.1.tar.gz
- All released versions are available at the Cado-nfs forge
- The developpement version is available as a public git repository
Supported platforms
The primary development platform is x86_64 linux with gcc 4.4 or later, the most common processor being Intel Core2-like and Nehalem. Other 64-bit microarchitectures and processors are checked regularly.
Anything else than the primary platform perhaps works, perhaps does not work. No platform beyond the primary one is ``supported'', although we are delighted if a given combination cpu/system/compiler works for you.
- Mac OS X Leopard and Snow Leopard have been tested to work at least once with GMP-5.0.2 (see section "Install" in README). ABI selection is sometimes tricky.
- FreeBSD and OpenBSD have been tested to work at least once.
- 32-bit Linux/BSD with gcc-4.1 or later is supposed to work.
- Windows is not supported (see a longer note at the end of README).
Required software tools
- GMP: usually installed in most Linux distributions.
- GCC 4.4 or later ; some others compilers might work, but are unsupported. Both C and C++ compilers are required.
- GNU make and CMake (2.6.3 or later) for building (CMake is installed on the fly if missing. This feature requires an Internet connection.)
- Support for posix threads.
- The main cadofactor.pl script uses a lot of unix tools: perl, ssh, rsync, gzip to mention but a few.
Optionally:
- Support for MPI.
Features
Algorithms used in CADO-NFS 1.1 are the following:
- The polynomial selection uses the algorithm of Kleinjung (2008).
- The filtering step follows Cavallar's thesis. Right now it is not parallel.
- Relation search is done using lattice sieving, including multithread support to reduce memory.
- The linear algebra step is implemented using block Wiedemann algorithm. This implementation is parallel at multithread and MPI levels.
- The square root step is implemented in a naive way. An alternate (experimental) implementation is available for very large computation, or pathological Galois groups.
Efficiency considerations (on a typical PC):
- CADO-NFS is competitive with the current best available MPQS implementations (say msieve) for numbers up from about 95 digits.
- Factoring a number of 120 digits will require 3 to 4 days on a single core of a typical PC.
- Factoring a number of 140 digits will require about 1 month on one core.
- Factoring a number of 160 digits will require 6 to 7 months on one core.
Contact/Support
Please direct enquiries about cado-nfs to the public mailing list cado-nfs-discuss@lists.gforge.inria.fr.