5-10 December 2013
Université de Toulon
Europe/Paris timezone

Linear Algebra for the Discrete Logarithm Problem using GPUs

10 Dec 2013, 10:30
1h
S112 (Université de Toulon)

S112

Université de Toulon

Speaker

Mr Jeljeli HAMZA (Loria, Nancy)

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.

Presentation Materials

There are no materials yet.