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


CADO-NFS is a complete implementation in C/C++ of the Number Field Sieve (NFS) algorithm for factoring integers and computing discrete logarithms in finite fields. 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. 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 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.


Algorithms used in CADO-NFS 2.3.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, 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, both phases used 8 processes of two threads each, with CADO-NFS 2.1 using ./ N -s 8 -t 2. With CADO-NFS 2.3, the same behavior is obtained with ./ --client-threads 2 --server-threads 16 --slaves 8. 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 CADO-NFS 2.3.0
RSA-120 100 hours 45.6 hours 43.6 hours [4.3 hours] 32.2 hours [2.2 hours] 26 hours [1.9 hours]
RSA-130 288 hours 231 hours 219 hours [18.5 hours] 124 hours [8.2 hours] 107 hours [7.5 hours]
RSA-140 809 hours 614 hours 597 hours [49.4 hours] 469 hours [30.9 hours] 352 hours [23 hours]
RSA-155 268 days 141 days 126 days [12.2 days] 90 days [5.8 days] 83 days [5.3 days]

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

You can browse into the development tree history to find the NEWS file for past releases:

Last modification: Mon 11 Sep 2017 11:34:42 AM CEST
© 2006– The CADO-NFS Development Team. ; valid XHTML 1.0, valid CSS