Sites Inria

English version

Equipe de recherche LFANT

Théorie algorithmique des nombres rapide et flexible

Présentation de l'équipe

L'équipe LFANT travaille sur les algorithmes en théorie des nombres et en géométrie arithmétique. Elle couvre toute la chaîne de la conception et l'analyse d'algorithmes passant par des implantations performantes jusqu'aux applications.

Axes de recherche

L'équipe Lfant a pour but de faire l'inventaire des algorithmes majeurs en théorie des nombres, en particulier en théorie algébrique des nombres et en géométrie arithmétique, et d'en proposer des analyses de complexité. La plupart de ces algorithmes ont été développés et testés sur des corps de nombres de petit degré and ne passent que difficilement à l'échelle. Des analyses de complexité devraient naturellement mener à des améliorations algorithmiques en identifiant des goulots d'étranglement et en introduisant des approches modernes asymptotiquement rapides.

La fiabilité des algorithmes développés est un deuxième objectif à long term de notre équipe. Quitte à démontrer l'hypothèse de Riemann, elle peut être atteinte à travers le déploiement d'algorithmes particuliers, plus lents, qui ne reposeraient sur aucune hypothèse non prouvée. Nous préférerions, par contre, d'ajouter aux algorithmes non prouvés les plus rapides des certificats vérifiables indépendamment. Dans l'idéal, il ne devrait pas prendre plus de temps de vérifier ces certificats que de les créer.

Tous nos résultats théoriques sont complémentés par des implantations de référence dans Pari/Gp, permettant ainsi de déterminer et d'ajuster les seuils pour atteindre la complexité asymptotique. Ces implantations aident également à évaluer la performance pratique des algorithmes sur des problèmes de recherche fournis par la communauté. Une autre source de problèmes traités par l'équipe Lfant découle de la cryptologie moderne. Effectivement, la sécurité de tous les cryptosystèmes à clef publique déployés en pratique repose sur la difficulté de résoudre des problèmes en théorie des nombres; inversement, implanter les systèmes et trouver des paramètres sûrs requièrent des algorithmes efficaces.

Logiciels

Relations industrielles et internationales

Partenaires industriels

  • France Télécom R&D
  • ST-Ericsson
  • Gemalto
  • Cryptolog

Collaborations internationales

  • University of Calgary
  • University of Waterloo
  • Universiteit Leiden

Mots-clés : Théorie algorithmique des nombres Corps de nombres Corps de fonctions Courbes algébriques Cryptologie