Large-scale computational records for public-key cryptography: current state of the art, and further directions

Abstract. In 2020, we set the academic state of the art in integer factoring (IF) at 240, and immediately afterwards 250 decimal digits, and finite field discrete logarithm computation (DL), modulo a 240-digit prime. These records still hold.  Previous records date back to 2016 (for DL) and 2009 (for IF).  The IF and DL problems are still of utmost importance to public key cryptography as it is deployed now. In this talk, I will try to explain some of the techniques that were essential in making these computations a success. I also want to take this occasion to reflect on the insight that these computational records can give.  While such records provide of course very important data points for the assessment of the computational hardness of the IF and DL problems, the sad fact is that it is quite hard to extrapolate from there in a rigorous way.

Suggested readings: ia.cr/2020/697, arxiv.org/abs/2007.02730

[Slides]