Séminaire Algorithmique : « Multiplication modulaire dans le système de représentation Residue Number System », Christophe Nègre (GREYC, Caen)

Dans cet exposé nous présenterons le système de représentation RNS utilisé pour l’arithmétique des grands entiers. Nous nous intéresserons en particulier à la multiplication modulaire en RNS et son application en cryptographie. Les algorithmes de Montgomery et de Barrett sont les plus couramment utilisés pour la multiplication modulaire. En RNS c’est l’approche de Montgomery qui est la plus utilisée, elle permet entre autre de masquer des données pour contrer des attaques par analyse de courant. Nous verrons ensuite des résultats récents sur l’approche de Barrett en RNS, la rendant compétitive pour des calculs n’impliquant que des réductions modulaires finales.