Skip to Main content Skip to Navigation

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 :
Complete list of metadata
Contributor : Thèses Ul Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 12:46:15 PM
Last modification on : Saturday, October 16, 2021 - 11:26:08 AM


Files produced by the author(s)


  • HAL Id : tel-01750438, version 1



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



Record views


Files downloads