La géométrie des nombres : de Gauss aux codes secrets

Phong Nguyen

Hermann Minkowski (1864-1909) est un mathématicien allemand d'origine lithuanienne, connu pour ses travaux sur le continuum espace-temps, utilisés par Albert Einstein dans sa célèbre théorie de la relativité générale. À la fin du dix-neuvième siècle, il créa une branche de la théorie des nombres baptisée géométrie des nombres. La géométrie des nombres étudie les réseaux, c'est-à-dire des arrangements réguliers de points dans l'espace, une structure simple qui intervient notamment en crystallographie. Un réseau contient une infinité de points (dont l'origine), mais il comporte au moins un point (non trivial) qui a la particularité d'être le plus proche de l'origine. Le plus célèbre problème de la géométrie algorithmique des nombres, connu sous le nom de problème du plus court vecteur, consiste à trouver un tel point. Gauss a complètement résolu ce problème en dimension 2, par analogie avec le classique algorithme d'Euclide permettant de calculer le pgcd de deux entiers. Mais le problème général dans l'espace à n dimensions semble particulièrement difficile.

Au début des années 80, des mathématiciens hollandais et hongrois (les frères Lenstra, et Lovász) ont découvert un algorithme, connu sous le nom de LLL, qui fournit une réponse partielle à ce problème. Cet algorithme a eu des applications spectaculaires notamment pour attaquer plusieurs codes secrets, ou pour factoriser des polnômes ou des entiers. La réussite expérimentale de cet algorithme a laissé penser que le problème du plus court vecteur était facile. Mais cette opinion fut récemment mise à mal par les travaux d'un mathématicien hongrois, Miklós Ajtai, ancien élève du célèbre Paul Erdös. Or si on suppose que le problème du plus court vecteur est difficile et non pas facile, alors on peut curieusement construire des codes secrets sûrs. Certains de ces codes secrets s'avèrent même bien plus efficaces que tous les codes secrets connus à ce jour !

Dans cet exposé, nous présenterons ce domaine de recherche en pleine effervescence qu'est la géométrie algorithmique des nombres, à la frontière entre mathématiques et informatique. On s'intéressera en particulier aux relations entre géométrie des nombres et cryptologie, pour illustrer l'utilité des mathématiques.