Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Parallel Structured Gaussian Elimination for the Number Field Sieve

Abstract : This article describes a parallel algorithm for the Structured Gauss-ian 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 20 seconds and from 6.7 hours to 2.3 minutes, respectively.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [45 references]  Display  Hide  Download
Contributor : Paul Zimmermann <>
Submitted on : Friday, April 12, 2019 - 1:31:28 PM
Last modification on : Monday, May 4, 2020 - 11:39:30 AM


Files produced by the author(s)


  • HAL Id : hal-02098114, version 1


Charles Bouillaguet, Paul Zimmermann. Parallel Structured Gaussian Elimination for the Number Field Sieve. 2019. ⟨hal-02098114⟩



Record views


Files downloads