Header image
Maître de Conférences, à l'Université de Limoges
  Mise à jour le 21 juillet 2014
Thèmes de recherche

Théorie algorithmique des nombres

Algorithmes pour les corps de nombres, les courbes elliptiques, les formes quadratiques binaires.

Cryptographie

Protocoles. Preuves de sécurité.

Primalité, factorisation, logarithme discret

La primalité est mon centre d'intérêt "historique". Il s'agit des méthodes pour déterminer si un nombre donné est premier ou non. Cela est aujourd'hui essentiellement résolu, pour principalement trois raisons :

  • Il existe des tests extrêmement rapides (Rabin-Miller, Lucas) donnant la bonne réponse avec probabilité très proche de 1.
  • Il existe des algorithmes relativements rapides en pratique (ECPP) donnant la bonne réponse avec certitude.
  • Il existe un algorithme (AKS) polynomial (résultat théorique majeur, mais de peu d'intérêt pratique).

    Les problèmes de la factorisation des entiers et du logarithme discret restent des problèmes algorithmiques d'importance primordiale. Malgré une grande diversité d'algorithmes pour ces deux problèmes et des décennies de recherche, ils restent non résolus que ce soit en pratique (on ne sait pas factoriser de très grands entiers) ou en théorie (on ne sait pas montrer qu'il n'existe pas de méthode rapide).


    • Générateurs aléatoires

    Les LFSR (Linear Feedback Shift Register) sont les circuits majoritairement utilisés pour le chiffrement à flot et la génération rapide de bits aléatoires. Les FCSR (Feedback with Carries Shift Register) sont une alternative presque aussi rapide mais sont non linéaires, ce qui peut fournir des garanties sur la sécurité des algorithmes les utilisant. L'étude de leur structure et de leurs applications s'est rapidement développée au cours de ces dernières années.


    Information quantique

    Les lois de la Mécanique Quantique ont des implications importantes en cryptographie pour deux raisons. 1) Elles ont ouvert la voie à des algorithmes et protocoles spécifiquement quantiques dont la sécurité repose sur des lois physiques. 2) Elles ouvrent une voie vers une nouvelle classe d'algorithmes qui contient des méthodes rapides de factorisation et de logarithme discret, et qui rendront obsolètes les protocoles à clés publiques actuels si des ordinateurs quantiques sont construits un jour.

    Mais l'importance de la théorie de l'information quantique est certainement encore plus grande. On sait aujourd'hui que les lois de la physique "classique" ne décrivent pas avec exactitude la nature. D'un autre côté, de nombreux aspects de la mécanique quantique, dans laquelle l'information joue un rôle fondamental, restent mals compris. La théorie de l'information pourrait bien fournir les clés de la physique de demain.