Abstract:
In December 2009, the factorization of RSA-768 was announced.
This milestone, to which we participated, was then published at Crypto
and the article recently received a Test-of-Time award.
This is a good opportunity to look at what happened since then in the
area of the Number Field Sieve (NFS) algorithm. We will take a biased
point of view, looking in particular at the Cado-nfs software, which was
a young project in 2009 and the code was not used for the 768-bit
record. It has now become the reference implementation, and was used to
set the current records for both factoring (250 decimal digits) and
discrete logarithm in finite fields (240 digits).
We will tell a few stories of our journey through NFS and computing
records. Theoretical questions in number theory meet deep algorithmic
questions to form the basis of the cado-nfs software, which would not
survive without a lot of software engineering.
