Conférence
Notice
Lieu de réalisation
Centre Inria d'Université Côte d'Azur
Langue :
Français
Crédits
Jean-Claude Bajard (Intervention)
Crédit image : Centre Inria d'Université Côte d'Azur
Détenteur des droits
Centre Inria d'Université Côte d'Azur
DOI : 10.60527/r8vx-5f19
Citer cette ressource :
Jean-Claude Bajard. Inria. (2024, 16 mai). Des systèmes de numération pour le calcul modulaire. [Vidéo]. Canal-U. https://doi.org/10.60527/r8vx-5f19. (Consultée le 21 juin 2024)

Des systèmes de numération pour le calcul modulaire

Réalisation : 16 mai 2024 - Mise en ligne : 22 mai 2024
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

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 fixe, par exemple lorsqu’on calcule sur un corps fini, 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. Enfin, le produit modulaire peut être considéré comme un changement de représentation vers une base d’Ostrowski sur les entiers.

Intervention

Sur le même thème