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).<br /><br />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épasse<br />le 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é.<br /><br />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.<br /><br />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.

Le 10ème problème de Hilbert, consistant à trouver les solutions entières d'équations polynomiales est un problème crucial en cryptanalyse. Si ce dernier a été prouvé indécidable, Coppersmith publia en 1996 une méthode basée sur la réduction de réseaux permettant de trouver efficacement l'ensemble des petites solutions de certaines équations polynomiales. De nombreuses applications de cette méthode ont vu le jour dans le domaine de la cryptanalyse à clé publique, notamment lorsque le cryptosystème est exécuté sur un système embarqué et qu'une partie de la clé secrète est dévoilée par la réalisation d'attaques physiques sur le dispositif. Dans ce contexte, nous proposons une attaque physique sur le schéma de signature RSA en mode CRT où une application de la méthode de Coppersmith permet de compléter l'information obtenue par l'attaque physique. Nous proposons également un nouvel algorithme déterministe basé sur la méthode de Coppersmith pour factoriser les entiers de la forme $N=p^rq^s$ en temps polynomial lorsque $r$ ou $s$ sont suffisamment grands. Enfin, si les applications de la méthode de Coppersmith sont nombreuses, en pratique, du fait que les réseaux à réduire soient gigantesques, les petites solutions ne peuvent être retrouvées que jusqu'à une borne qui est plus petite que la borne théorique annoncée. Aussi, une autre contribution de cette thèse consiste en la proposition de deux méthodes permettant une accélération du temps d'exécution de l'algorithme de Coppersmith. Lorsque les deux méthodes sont combinées, le nouvel algorithme s'effectue des centaines de fois plus rapidement pour des paramètres typiques, permettant ainsi dans de nombreux cas d'atteindre la borne théorique. / The 10th Hilbert problem, which consists in finding integer solutions to polynomial equations is a crucial problem in cryptanalysis, which has been proven to be undecidable. However, Coppersmith published in 1996 a method based on lattice reduction, which allows to efficiently find all small solutions to some polynomial equations. Many applications of this method have risen in public key cryptanalysis, especially when the cryptosystem is executed on embedded systems and part of the secret key is revealed through physical attacks performed on the device. In this context, we propose in this thesis a physical attack on the RSA signature scheme when the CRT mode is used, where an application of Coppersmith's method allows to complete the information previously obtained by the physical attack. We also propose a new deterministic algorithm based on Coppersmith's method for factoring integers of the form $N=p^rq^s$ in polynomial time, under the condition that $r$ and/or $s$ are sufficiently large.Finally, if the applications of Coppersmith's method are numerous, in practice, since the lattices to be reduced are huge, the small solutions can only be recovered until a bound which is smaller than the enounced theoretical bound. Thus, another contribution of this thesis lies in the proposition of two methods which allow to speed up the execution time of Coppersmith's algorithm. When both speedups are combined, the new algorithm performs hundreds of times faster for typical parameters, which allows to reach the theoretical bound in many cases.