International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment

Authors:
Fabrice Boudot , Université de Limoges, XLIM, UMR 7252, F-87000 Limoges, France
Pierrick Gaudry , Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Aurore Guillevic , Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Nadia Heninger , University of California, San Diego, USA
Emmanuel Thomé , Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Paul Zimmermann , Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Download:
DOI: 10.1007/978-3-030-56880-1_3 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
Abstract: We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records. The last page of this paper also reports on the factorization of RSA-250.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30365,
  title={Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-56880-1_3},
  author={Fabrice Boudot and Pierrick Gaudry and Aurore Guillevic and Nadia Heninger and Emmanuel Thomé and Paul Zimmermann},
  year=2020
}