Linear Algebra for the Discrete Logarithm Problem using GPUs

par Jeljeli HAMZA (Loria, Nancy)

mardi 10 déc. 2013, 10:30 → 11:30 Europe/Paris

U304 (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.