Algorithms for discrete logarithm in finite fields

Abstract : In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic
Document type :
Theses
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-01750438
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 12:46:15 PM
Last modification on : Tuesday, April 24, 2018 - 1:30:09 PM

File

DDOC_T_2013_0183_BARBULESCU.pd...
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01750438, version 1

Collections

Citation

Razvan Barbulescu. Algorithms for discrete logarithm in finite fields. Other [cs.OH]. Université de Lorraine, 2013. English. ⟨NNT : 2013LORR0183⟩. ⟨tel-01750438⟩

Share

Metrics

Record views

65

Files downloads

134