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

Citing CADO-NFS

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.

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 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: Fri 14 Oct 2016 11:19:43 AM CEST
© 2006– The CADO-NFS Development Team. ; valid XHTML 1.0, valid CSS