Description
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.<br/> 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.
Next sessions
-
Random lattices that are modules over the ring of integers
Speaker : Nihar Gargava - Institut de Mathématiques d'Orsay
We investigate the average number of lattice points within a ball where the lattice is chosen at random from the set of unit determinant ideal or modules lattices of some cyclotomic number field. The goal is to consider the space of such lattice as a probabilistic space and then study the distribution of lattice point counts. This is inspired by the connections of this problem to lattice-based[…]-
Cryptography
-
-
Schéma de signature à clé publique : Frobénius-UOV
Speaker : Gilles Macario-Rat - Orange
L'exposé présente un schéma de signature à clé publique post-quantique inspiré du schéma UOV et introduisant un nouvel outil : les formes de Frobénius. L'accent est mis sur le rôle et les propriétés des formes de Frobénius dans ce nouveau schéma : la simplicité de description, la facilité de mise en oeuvre et le gain inédit sur les tailles de signature et de clé qui bat RSA-2048 au niveau de[…] -
Yoyo tricks with a BEANIE
Speaker : Xavier Bonnetain - Inria
TBD-
Cryptography
-
Symmetrical primitive
-