16 mai 2024
Le calcul modulaire est utilisé dans de nombreuses applications des mathématiques, telles que la cryptographie. La réduction modulaire dans un contexte très général est coûteuse, car elle nécessite principalement une division. Dans la pratique, cependant, le modulo est souvent fi xe, par exemple lorsqu’on calcule sur un corps fi ni, et il est donc possible de mettre en oeuvre des stratégies pour réduire le coût de la réduction. Les premières approches consistent, si l’on a le choix, à travailler avec des modulo particuliers, comme les nombres premiers de Mersenne ou les pseudo-premiers de Mersenne, voire des généralisations de ces formes. D’autres approches consistent à faire des réductions modulaires sans division avec des modules qui n’ont pas de particularités, comme les algorithmes de Montgomery ou de Barrett. Un autre type de stratégies revient à travailler sur les systèmes de numération pour améliorer le calcul ou la réduction.
C’est le cas des systèmes de nombres résiduels basés sur le théorème du reste chinois, où le gain se fait sur la multiplication et l’addition, et avec lesquels la réduction de Montgomery est adaptable. Nous pouvons également construire des systèmes modulo-dépendants qui prennent une forme similaire à celle du pseudo-Mersenne. Les réductions ici sont similaires à la recherche du vecteur le plus proche dans un réseau euclidien. Enfi n, le produit modulaire peut être considéré comme un changement de représentation vers une base d’Ostrowski sur les entiers.
Bio : Jean Claude Bajard est professeur à Sorbonne Université. Depuis 2020, il est membre de l’équipe Ouragan Inria et de l’Institut de Mathématiques de Jussieu-Paris Rive Gauche. Son domaine de recherche est l’arithmétique informatique. Jean Claude Bajard a enseigné les mathématiques en lycée une dizaine d’années avant de faire une thèse de doctorat en informatique à l’ENS Lyon, qu’il a soutenue en 1993. En 1993 il a été recruté maître de conférences à Marseille, puis en 1999 il devient professeur à l’Institut Universitaire de Technologie de Montpellier, membre du LIRMM. En 2009, il a rejoint l’Université Pierre et Marie Curie et a été membre du LIP6 jusqu’en 2019.
