Abstract FR:

Nous decrivons dans cette these des algorithmes sous-exponentiels de resolution du probleme du logarithme discret dans les corps finis de grande caracteristique, utilisant la decomposition des nombres premiers dans les anneaux d'entiers des corps algebriques. Apres quelques generalites sur la cryptographie et le logarithme discret, nous decrivons ensuite les algorithmes d'adleman dans les corps a p elements et de hellman-reyneri dans les corps a p#n elements (avec p petit), et l'algorithme de elgamal dans les corps a p#2 elements. Nous proposons deux variantes de ce dernier, plus faciles a programmer. Nous etudions ensuite l'extension de ces algorithmes aux corps a p#n elements, n petit et p grand. Le passage a une nouvelle representation de ces corps nous permet d'effectuer l'essentiel de nos calculs dans les anneaux d'entiers de corps de nombres algebriques. Nous travaillons, quand cela est possible, dans l'anneau d'entiers d'une extension algebrique pure. Cela est le cas pour les nombres premiers p tels que n divise p-1. Dans les autres cas, nous nous ramenons aux anneaux des corps de nombres algebriques engendres par une racine d'un trinome de la forme x#n + bx+c. C'est ainsi que nous construisons, suivant chaque cas, des algorithmes permettant de fixer des bases d'entiers algebriques irreductibles de petites normes. Nous detaillons entierement l'etude dans les corps a p#n elements, pour n = 3, 4, 5. Apres l'etude de l'irreductibilite des binomes a coefficients dans les corps a p elements, nous donnons la construction de nos algorithmes et l'estimation de leur cout. Pour terminer, nous donnons quelques applications du logarithme discret en cryptographie: nous y exposons quelques protocoles de chiffrement et leur crypto-analyse. Enfin, nous donnons en annexes une implementation en maple des differents algorithmes exposes