Sommaire

  • Cet exposé a été présenté le 05 avril 2013.

Description

  • Orateur

    Grégoire Lecerf - CNRS

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.

Prochains exposés

  • Chiffrement homomorphe à l'aide des groupes après Nuida

    • 27 novembre 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Pierre Guillot - Ravel Technologies/Université de strasbourg

    Nuida et d'autres ont montré comment on peut obtenir un protocole de chiffrement pleinement homomorphe si l'on sait chiffrer les éléments d'un groupe G convenable, tout en sachant faire l'opération de G "en homomorphe". Les exemples étaient jusqu'à présent limités au chiffrement d'un bit à la fois, avec beaucoup d'opérations à effectuer pour "simuler" les portes logiques usuelles. Je vais[…]
    • Cryptography

  • Post-Quantum Signatures from Symmetric-Key-Friendly Techniques: From MPC-in-the-Head to VOLE-in-the-Head

    • 04 décembre 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Dung Bui - Northwestern University

    The MPC-in-the-Head (MPCitH) paradigm turns a secure multiparty computation protocol into a zero-knowledge proof and, via Fiat–Shamir, into a signature scheme whose security relies only on symmetric-key primitives. The framework of Katz, Kolesnikov and Wang (KKW, CCS18), which moves most of the MPC work into a committed preprocessing phase that the verifier checks by opening all-but-one of the[…]
  • Distinguishing and Attacking McEliece Cryptosystems Using GRS Codes with Higher-Weight Mask

    • 11 décembre 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Michael Schaller - University of Zürich, Applied Algebra group

    Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon (GRS) codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix $M$ with larger row and column weight. In many of them, the secret key is still a GRS code.There have been successful attacks on some of those schemes with row and column weight between $1$[…]
  • Nouveaux doctorants

    • 08 janvier 2027 (13:45 - 14:45)

    • Salle Guernesey à l'ISTIC

    Exposés courts des nouveaux doctorants (Elouan, Quentin, Eliot)
Voir les exposés passés