Séminaire de Cryptographie

Accueil     Présentation     Archives

Grégoire Lecerf


Algorithmique détendue pour les nombres entiers p-adiques

Les implantations actuelles des nombres p-adiques reposent souvent sur des techniques dites zélées qui demandent de connaître à l'avance la précision nécessaire pour les calculs. Cette approche est très efficace du point de vue de la complexité asymptotique et elle est largement utilisée, par exemple dans des algorithmes de remontée de type Newton-Hensel intervenant dans la factorisation des polynômes et la résolution des systèmes algébriques.

Néanmoins il existe des techniques alternatives, appelées paresseuses, qui ont l'avantage d'être plus naturelles d'un point de vue mathématique. Un nombre p-adique y est représenté comme une suite de coefficients munie d'une fonction pour calculer le coefficient suivant et ce, à tout ordre. Cette approche facilite grandement la résolution d'équations implicites et retire tout soucis de choix de la précision des calculs à l'utilisateur. Pendant longtemps cette approche paresseuse était pénalisée par son manque d'efficacité. Les premières variantes rapides ont été développées en calcul formel dans les années 90 par van der Hoeven pour les séries formelles, et portent désormais la terminologie d'algorithmes détendus car combinant le confort de l'approche paresseuse avec l'efficacité des méthodes zélées.

Dans cet exposé, nous montrerons les algorithmes utilisés pour les calculs détendus avec des nombres p-adiques. Nous comparerons les approches détendues et zélées des points de vue théoriques sur différents types de calcul. Et enfin nous aborderons les aspects pratiques liés à la programmation de ces méthodes réalisée au sein de la bibliothèque C++ algebramix du logiciel de calcul formel et analytique Mathemagix (http://www.mathemagix.org).

Ce travail a été réalisé en collaboration avec Jérémy Berthomieu et Joris van der Hoeven.