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

https://hal.inria.fr/hal-02098114
Contributor : Paul Zimmermann <>
Submitted on : Friday, April 12, 2019 - 1:31:28 PM
Last modification on : Thursday, October 10, 2019 - 2:16:07 PM

File

merge.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02098114, version 1

Citation

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

Share

Metrics

Record views

210

Files downloads

262