BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//6.4.6.4.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:3669@test.i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20150312T110000
DTEND;TZID=Europe/Paris:20150312T120000
DTSTAMP:20200828T140825Z
URL:https://test.i2m.univ-amu.fr/events/polynomial-selection-for-nfs-dl-in
-finite-fields-gf-p-k-of-medium-to-large-characteristic-with-practical-app
lication-to-gf-p-2/
SUMMARY:Polynomial selection for NFS-DL in finite fields GF(p^k) of medium
to large characteristic with practical application to GF(p^2) - Aurore Gui
llevic
DESCRIPTION:This talk is about the asymptotic and practical hardness of dis
crete logarithms (DL) in non-prime finite fields of medium to large charac
teristic. This is needed to evaluate the security of e.g. pairing-based cr
yptosystems. The Number Field Sieve (NFS) algorithm is known to be the mos
t efficient to compute discrete logarithms in prime finite fields and larg
e characteristic finite fields. We are interested in adapting NFS for DL i
n GF(p^k)\, starting with k=2. NFS algorithm requires two number fields th
at can be embedded into GF(p^k). We introduce two new methods for polynomi
al selection\, i.e. the choice of the two polynomials defining the two num
ber fields involved in NFS. We generalize the Joux-Lercier method\, and pr
opose the Conjugation method.\nThese methods provide an important practica
l speed-up for DL in GF(p^2) compared to DL in prime fields of the same si
ze. We show that by a record of DL computation in a field GF(p^2) of 180 d
ecimal digits (p is 90 digit long).\n\nOur methods have an asymptotic comp
lexity of L(1/3\,(64/9)^(1/3)). Moreover they can be applied in medium-siz
ed characteristic and have in this case a better asymptotic complexity of
L(1/3\, (96/9)^(1/3)) instead of L(1/3\, (128/9)^(1/3)). Compared to the r
ecent MNFS paper\, our asymtotic complexity is slightly better (2.20 vs 2.
24 for the second constant in the L(1/3) formula).\n\nThis is a joint work
with Razvan Barbulescu\, Pierrick Gaudry and François Morain from the CA
TREL project (http://catrel.loria.fr).\n\nAurore Guillevic\, Inria Nancy G
rand Est\, Équipe CARAMBA \n\n
CATEGORIES:Séminaire Arithmétique et Théorie de l’Information (ATI)
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20141026T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR