Algorithmes de calcul de logarithmes discrets dans les corps finis

Membre du Jury : von zur Gathen, Joachim et Coppersmith, Don et Berger, Thierry et Villard, Gillles et Sendrier, Nicolas et Roblot, XavierComputing 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 onthe 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 importantmanagement work on the human side. Driving such tasks also yields some observations.Le calcul de logarithmes discrets est un problème central en cryptologie. Lorsqu'un algorithme sous-exponentiel pour résoudre ce problème existe, le cryptosystème concerné n'est pas nécessairement considéré comme disqualifié, et il convient d'actualiser avec soin l'état de l'art de la cryptanalyse. Les travaux de ce mémoire s'inscrivent dans cette optique. Nous décrivons en particulier comment nous avons atteint un record de calculs de logarithmes discrets: \GFn(607).Dans une première partie, nous exposons les différentes améliorations que nous avons apportées à l'algorithme de Coppersmith pour le calcul de logarithmes discrets en caractéristique 2. Ces améliorations ont rendu possible le record que nous avons atteint. La portée de ce calcul dépassele simple cadre des corps finis, à cause de l'existence de la réduction MOV d'une part, et de la récente introduction des cryptosystèmes fondés sur l'identité.On s'intéresse plus en détail, dans une seconde partie du mémoire, au problème classique de la résolution d'un système linéaire creux défini sur un corps fini, porté aux limites de ce que la technologie (théorique et pratique) permet. Nous montrons comment une amélioration substantielle de l'algorithme de Wiedemann par blocs a rendu celui-ci compétitif pour la résolution d'un grand système linéaire creux sur \GF p.Une partie de ce mémoire est consacrée au point de vue de l'expérimentateur, grand utilisateur de moyens de calcul, de la surcharge de travail humain que cela impose, et des constatations que cette position amène