Linear Algebra for the Discrete Logarithm Problem using GPUs
Jeljeli HAMZA(Loria, Nancy)
U304 (Université de Toulon)
Université de Toulon
In the context of cryptanalysis, computing discrete logarithms in large cyclic groups using index-calculus-based methods, such as the number field sieve (NFS-DL) or the function field sieve (FFS), 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). We investigate accelerating this central operation on NVIDIA GPUs. In this talk, we present a matrix format suitable to the sparsity and the specific computing model and how we use Residue Number System (RNS) arithmetic to accelerate modular operations.