Skip to Main content Skip to Navigation
Journal articles

Parallel Structured Gaussian Elimination for the Number Field Sieve

Charles Bouillaguet 1, * Paul Zimmermann 2
* Corresponding author
2 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-02098114
Contributor : Paul Zimmermann <>
Submitted on : Tuesday, January 5, 2021 - 9:34:59 AM
Last modification on : Monday, January 11, 2021 - 2:27:51 PM

File

merge.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02098114, version 2

Citation

Charles Bouillaguet, Paul Zimmermann. Parallel Structured Gaussian Elimination for the Number Field Sieve. Mathematical Cryptology, Florida Online Journals, In press. ⟨hal-02098114v2⟩

Share

Metrics

Record views

47

Files downloads

96