Journées Calculs Haute performance

Linear Algebra for the Discrete Logarithm Problem using GPUs

by Jeljeli HAMZA (Loria, Nancy)

Europe/Paris
U304 (Université de Toulon)

U304

Université de Toulon

Description
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.