Séminaire de Nicolas Méloni, IMATH - Université de Toulon
PMNS : généralisation via l’algorithme de Babai
Résumé : Le Polynomial Modular Number System permet de représenter les éléments d’un corps finis via les polynomes d’un anneau quotient de type ZZ[X]/(E(X)). En terme de cout de calcul, la principale opération dans ce système est la réduction interne qui consiste essentiellement à faire une recherche de plus proche vecteur dans un réseau euclidien. La grande majorité des méthodes de réduction de l’état de l’art reposent sur une approche dérivée de l’algorithme réduction de Montgomery pour les entiers. Nous verrons qu’il s’agit en fait d’un cas particulier d’une méthode générale reposant sur l’algorithme "Rounding" de Babai. Celui-ci nous permettra extension naturelle des algorithmes standards de réduction modulaire (Barrett et Mongomery) des entiers vers les anneaux quotient de polynomes.
