CADO-NFS

Crible Algébrique: Distribution, Optimisation - Number Field Sieve

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 script that runs them, possibly in parallel over a network of computers. Starting with version 2.0 there are some functionalities for computing discrete logarithms in finite fields. CADO-NFS is distributed under the Gnu Lesser General Public License (LGPL) version 2.1 (or any later version).

The main authors are:

Additional authors who have worked on the Function Field Sieve part of the code:

Other persons have contributed parts of the code, in current or in earlier revisions of CADO-NFS: Richard Brent, Andreas Enge, Nuno Franco, Jérome Milan, Lionel Muller, Thomas Prest.

News

Date Newsflash


22-07-2014:   CADO-NFS 2.1 is now available (release notes)
18-11-2013:   CADO-NFS 2.0 is now available (release notes)
11-10-2013:   Version 2.0 will soon be available. Please test the alpha version.
30-06-2012:   RSA-704 has been factored using CADO-NFS (announcement)
27-10-2011:   CADO-NFS 1.1 is now available (release notes)
10-12-2010:   CADO-NFS 1.0 is now available.

People who used CADO-NFS

If you used CADO-NFS and wish to be added to this list, send an email.

Download

Supported platforms

The primary development platform is x86_64 linux with gcc 4.4 or later, the most common processor being Intel Core2-like, Nehalem and Ivy Bridge. 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.

Required software tools

Optionally:

Features

Algorithms used in CADO-NFS 2.1 are the following:

Speed comparison of CADO-NFS versions 1.1 and 2.0, obtained on a dual 8-core Intel(R) Xeon(R) CPU E5-2650 at 2.00GHz, running Linux 3.2.0. Both CADO releases were compiled with gcc 4.7.2.
With CADO-NFS 1.1 using cadofactor.pl, the timing runs used 16 processes of 1 thread each for polynomial selection and 8 processes of 2 threads each for sieving; with CADO-NFS 2.0 using cadofactor.py, both phases used 8 processes of two threads each. These are the default values in the parameter files included in the respective CADO-NFS release. The table lists CPU time.

Input number CADO-NFS 1.1 CADO-NFS 2.0 CADO-NFS 2.1
RSA-120 100 hours 45.6 hours 43.9 hours
RSA-130 288 hours 231 hours 219 hours
RSA-140 809 hours (=33.7 days) 614 hours (=25.6 days) 599 hours (=25 days)
RSA-155 268 days 141 days 123 days

Known bugs

All known bugs below are with respect to CADO-NFS-2.1. Previous versions are considered outdated, and we do not provide the (long) list of known-and-fixed bugs. Please upgrade to CADO-NFS-2.1.

The list below is almost surely incomplete. A separate branch of the repository collects small bugfixes to the 2.1 branch, which is a more comprehensive source of known bugs. See there for the log files. The command line for a checkout of that branch is:
git clone git://scm.gforge.inria.fr/cado-nfs/cado-nfs.git -b 2.1

Contact/Support

Please direct enquiries about cado-nfs to the public mailing list cado-nfs-discuss@lists.gforge.inria.fr.