Accelerating Iterative SpMV for Discrete Logarithm Problem Using GPUs

Hamza Jeljeli 1
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : In the context of cryptanalysis, computing discrete logarithms in large cyclic groups using index-calculus-based methods, such as the number field sieve or the function field sieve, requires solving large sparse systems of linear equations modulo the group order. Most of the fast algorithms used to solve such systems --- e.g., the conjugate gradient or the Lanczos and Wiedemann algorithms --- iterate a product of the corresponding sparse matrix with a vector (SpMV). This central operation can be accelerated on GPUs using specific computing models and addressing patterns, which increase the arithmetic intensity while reducing irregular memory accesses. In this work, we investigate the implementation of SpMV kernels on NVIDIA GPUs, for several representations of the sparse matrix in memory. We explore the use of Residue Number System (RNS) arithmetic to accelerate modular operations. We target linear systems arising when attacking the discrete logarithm problem on groups of size 100 to 1000 bits, which includes the relevant range for current cryptanalytic computations. The proposed SpMV implementation contributed to solving the discrete logarithm problem in GF($2^{619}$) and GF($2^{809}$) using the FFS algorithm.
Type de document :
Communication dans un congrès
International Workshop on the Arithmetic of Finite Fields WAIFI 2014, Sep 2014, Gebze, Turkey. <http://waifi.org/>
Liste complète des métadonnées


https://hal.inria.fr/hal-00734975
Contributeur : Hamza Jeljeli <>
Soumis le : jeudi 4 décembre 2014 - 17:43:43
Dernière modification le : jeudi 22 septembre 2016 - 14:31:20
Document(s) archivé(s) le : lundi 9 mars 2015 - 06:00:24

Fichiers

spmv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00734975, version 4
  • ARXIV : 1209.5520

Collections

Citation

Hamza Jeljeli. Accelerating Iterative SpMV for Discrete Logarithm Problem Using GPUs. International Workshop on the Arithmetic of Finite Fields WAIFI 2014, Sep 2014, Gebze, Turkey. <http://waifi.org/>. <hal-00734975v4>

Partager

Métriques

Consultations de
la notice

297

Téléchargements du document

166