| Hamza Jeljeli |  |
 |
Date of the talk: 8 April 2015, 11h30-12h00, amphithéâtre (dans le cadre des RAIM)
RNS Arithmetic for Linear Algebra of Discrete Logarithm Computations Using Parallel Architectures
In cryptanalysis, computing discrete logarithm problem (DLP) in multiplicative subgroups of finite fields using index-calculus-based methods requires solving large sparse systems of linear equations over finite fields of large characteristic. We run these linear algebra computations on GPU- and multi-core-based clusters. In this talk, we will describe the different levels of parallelism that can be exploited in these computations and will focus on the arithmetic aspects. We will show how the use of the Residue Number System (RNS) representation with architectures that exploit data level parallelism such that GPUs or CPUs featuring SIMD instructions accelerate the arithmetic over finite fields of large characteristic. We will illustrate our approach with record-sized DLP computations.
