Parallel Structured Gaussian Elimination for the Number Field Sieve
Vol. 0 No. 1 (2020), Articles
Vol. 0 No. 1 (2020)

Parallel Structured Gaussian Elimination for the Number Field Sieve

Articles
Published 2021-01-08
Charles Bouillaguet
Univ. Lille, CNRS, Centrale Lille, UMR 9189 - CRIStAL - Centre de Recherche en Informatique Signal et Automatique de Lille, F-59000 Lille, France
https://orcid.org/0000-0001-9416-6244
Paul Zimmermann
}Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
https://orcid.org/0000-0003-0718-4458
PDF

Keywords

Number Field Sieve
Structured Gaussian Elimination
parallel algorithm

How to Cite

Bouillaguet, C., & Zimmermann, P. (2021). Parallel Structured Gaussian Elimination for the Number Field Sieve. Mathematical Cryptology, (1), 22–39. Retrieved from https://journals.flvc.org/mathcryptology/article/view/126033
ACM ACS APA ABNT Chicago Harvard IEEE MLA Turabian Vancouver

Download Citation

Endnote/Zotero/Mendeley (RIS) BibTeX

Abstract

This article describes a parallel algorithm for the Structured Gaussian Elimination step of the Number Field Sieve (NFS). NFS is the best known method for factoring large integers and computing discrete logarithms.

State-of-the-art algorithms for this kind of partial sparse elimination, as implemented in the CADO-NFS software tool, were unamenable to parallel implementations. We therefore designed a new algorithm from scratch with this objective and implemented it using OpenMP. The result is not only faster sequentially, but scales reasonably well: using 32 cores, the time needed to process two landmark instances went down from 38 minutes to 21 seconds and from 6.7 hours to 2.3 minutes, respectively.

This parallel algorithm was used for the factorization records of RSA-240 and RSA-250, and for the DLP-240 discrete logarithm record.

PDF

It is the authors' responsibility that all submitted material, including supplementary files, can be made publicly accessible.