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).

CADO-NFS is the result of a collaborative effort involving many persons, over various periods of time. The current list of active contributors can be extracted from the git repository or from the openhub.net page. A tentative list of CADO-NFS authors is (alphabetical order):

The recommended way to cite CADO-NFS in a scientific publication is (bibtex entry):

where the release number and date should be changed to correspond to the version you actually used. If you used the development version, it is a good idea to give the git revision number.

Download

Release Link Date
Development version git repository today!
CADO-NFS 2.2.0 cado-nfs-2.2.0.tar.gz 11-12-2015
CADO-NFS 2.1.1 cado-nfs-2.1.1.tar.gz 08-10-2014
CADO-NFS 2.1 cado-nfs-2.1.tar.gz 22-07-2014
CADO-NFS 2.0 cado-nfs-2.0.tar.gz 18-11-2013
CADO-NFS 1.1 cado-nfs-1.1.tar.gz 27-10-2011
CADO-NFS 1.0 cado-nfs-1.0.tar.gz 10-12-2010

CADO-NFS is also available as a package in distributions:

Statistics and monitoring of development

Supported platforms

The primary development platform is x86_64 linux with gcc 4.4 or later, the most common processor being Intel core2-like or more recent.

Other architectures are checked regularly, and should work. Please refer to the CI page for the status of the currently tested platforms for the development branch.

The current release has undergone regular testing for the following hardware/software configurations, with gcc-4.4 or later:

Anything else perhaps works, perhaps does not work:

Required software tools

Optionally:

People who used CADO-NFS

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

Features

Algorithms used in CADO-NFS 2.2.0 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, with CADO-NFS 2.1 using ./factor.sh N -s 8 -t 2. The table below lists CPU time [wall clock time in square brackets].

Input number CADO-NFS 1.1 CADO-NFS 2.0 CADO-NFS 2.1 CADO-NFS 2.2.0
RSA-120 100 hours 45.6 hours 43.6 hours [4.3 hours] 32.2 hours [2.2 hours]
RSA-130 288 hours 231 hours 219 hours [18.5 hours] 124 hours [8.2 hours]
RSA-140 809 hours 614 hours 597 hours [49.4 hours] 469 hours [30.9 hours]
RSA-155 268 days 141 days 126 days [12.2 days] 90 days [5.8 days]

For 85- to 100-digits, Ben Buhrow did compare various QS and NFS tools, see here.

Known bugs

None so far for CADO-NFS-2.2.0.

Contact/Support

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

To report a bug, please include: