• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Parallel Structured Gaussian Elimination ...
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Article dans une revue scientifique
Title :
Parallel Structured Gaussian Elimination for the Number Field Sieve
Author(s) :
Bouillaguet, Charles [Auteur correspondant] refId
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Zimmermann, Paul [Auteur]
Cryptology, arithmetic : algebraic methods for better algorithms [CARAMBA]
Journal title :
Mathematical Cryptology
Pages :
22-39
Publisher :
Florida Online Journals
Publication date :
2021-01-08
English keyword(s) :
parallel algorithm
Structured Gaussian Elimination
Number Field Sieve
HAL domain(s) :
Informatique [cs]/Algorithme et structure de données [cs.DS]
English abstract : [en]
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. ...
Show more >
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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • https://hal.inria.fr/hal-02098114v2/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.inria.fr/hal-02098114v2/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.inria.fr/hal-02098114v2/document
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017