Laurent GREMY (ENS LYON) Computing discrete logarithms in GF(p^5) and GF(p^6): a focus on the relation collection

mardi 28 nov. 2017, 10:30 → 11:30 Europe/Paris

M205 (Batiment M)

Résumé :

Factoring large integers and computing discrete logarithms over finite fields
are two difficult problems, solved by a family of algorithms of subexponential
complexity, the index calculus one. The security of some cryptosystems rely on
this difficulty.

Since 1982 and the use of the quadratic sieve by Pomerance to factor large
integers, it is well known that an important step of these index calculus
algorithms, called relation collection, can be done quickly using sieving
algorithms, similar to the sieve of Eratosthenes to find prime integers, a
one-dimensional sieve algorithm.

Among the index calculus algorithms, the number field sieve (NFS) reaches the
best known complexity to compute discrete logarithms in medium characteristic
finite fields: these fields are of the form GF(p^n), where n is small, basically
n = 6 or n = 12. To efficiently compute discrete logarithms in such fields, it
is needed to use sieve algorithms in dimension larger than two (as shown in the
article of Joux, Lercier, Smart and Vercauteren in 2006, or the one of Kim and
Barbulescu in 2016), on the contrary to the case of the large characteristic,
essentially GF(p).

In this talk, we will describe three sieve algorithms in dimension three and
computational results of their implementations.

This is a joint work with Pierrick Gaudry, Aurore Guillevic, François Morain,
Emmanuel Thomé and Marion Videau.

 

Le plan qui se trouve ici peut être utile pour localiser le Bâtiment M :

 

http://www.univ-tln.fr/IMG/pdf/plan-campus-lagarde-octobre2017.pdf

 

Les lignes de Bus 191 et 29 permettent de relier la gare au campus de La Garde.