Laboratoire IMATH

Institut de Mathématiques de Toulon (EA 2134)

logoUTLN

Séminaire de Nicolas Méloni, IMATH - Université de Toulon

Séminaire IAA
Jeudi 08/12/22, 14h00 salle M003

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.

Séminaire de Nicolas Méloni, IMATH - Université de Toulon