Accelerating Iterative SpMV for the Discrete Logarithm Problem Using GPUs

DOI10.1007/978-3-319-16277-5_2MaRDI QIDQ2949470zbMATH OpenOpenAlexFDO

Authors Hamza Jeljeli

Publication date 1 October 2015

Published in Arithmetic of Finite Fields (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.5520

zbMATH Keywords

discrete logarithm problemGPUsmodular arithmeticresidue number systemsparse-matrix-vector product

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Mathematical problems of computer architecture (68M07) Cryptography (94A60)

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.

Recommendations

• Optimizing sparse matrix-matrix multiplication for the GPU
• Accelerating iterative linear solvers using multiple graphical processing units
• Accelerating preconditioned iterative linear solvers on GPU
• A parallel computing method using blocked format with optimal partitioning for SpMV on GPU

Cites work

• A monte carlo method for factorization
• Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
• Breaking Pairing-Based Cryptosystems Using η T Pairing over GF(397)
• Discrete logarithm in \(\mathrm{GF}(2^{809})\) with FFS
• scientific article; zbMATH DE number 3956969 (Why is no real title available?)
• scientific article; zbMATH DE number 503245 (Why is no real title available?)
• scientific article; zbMATH DE number 3269473 (Why is no real title available?)
• scientific article; zbMATH DE number 3353398 (Why is no real title available?)
• Reduction of Huge, Sparse Matrices over Finite Fields Via Created Catastrophes
• Solving sparse linear equations over finite fields
• Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm

Cited in

(2)

• Weakness of \(\mathbb{F}_{3^{6 \cdot 1429}}\) and \(\mathbb{F}_{2^{4 \cdot 3041}}\) for discrete logarithm cryptography
• Index calculus in the trace zero variety

This page was built for publication: Accelerating Iterative SpMV for the Discrete Logarithm Problem Using GPUs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2949470)