Skip to Main content Skip to Navigation

Algorithmes de calcul de logarithmes discrets dans les corps finis

Abstract : Computing discrete logarithms is a fundamental task for public key cryptanalysis. The mere existence of a subexponential algorithm for this purpose is not su±cient to de¯nitely rule on the security level provided by some cryptosystem. Assessing state-of-the-art cryptanalysis calls for a thorough evaluation process. This dissertation contributes to such an evaluation. In particular, a record computation for discrete logarithms over F2607 is described.
The first part of this thesis focuses on our study and use of Coppersmith's algorithm for computing discrete logarithms in finite fields of characteristic two. We brought several improvements to this algorithm, which made the record computation feasible. The relevance of such a computation extends beyond the realm of finite fields, because of the existence of the MOV reduction on the one hand, and the recently introduced identity-based cryptography on
the other hand.
The second part of this work addresses the classical problem of solving large sparse linear systems over finite fields, using the full power of existing algorithms and hardware in order to solve the largest possible linear systems. Specifically, we show how the block Wiedemann algorithm can be substantially improved in order to become very competitive for solving large sparse linear systems over Fp. Practical considerations on the achievement of the computations implied by this work are also discussed. These computations involved large resources, and required an important
management work on the human side. Driving such tasks also yields some observations.
Document type :
Complete list of metadatas

Cited literature [89 references]  Display  Hide  Download
Contributor : Admin Pastel <>
Submitted on : Tuesday, November 30, 2004 - 4:27:38 PM
Last modification on : Wednesday, October 14, 2020 - 3:54:04 PM
Long-term archiving on: : Friday, April 2, 2010 - 8:44:17 PM


  • HAL Id : tel-00007532, version 1



Emmanuel Thomé. Algorithmes de calcul de logarithmes discrets dans les corps finis. Génie logiciel [cs.SE]. Ecole Polytechnique X, 2003. Français. ⟨tel-00007532⟩



Record views


Files downloads