Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Exponentiation modulaire
Résumé
En mathématiques, plus précisément en arithmétique modulaire, l’exponentiation modulaire est un type d'élévation à la puissance (exponentiation) réalisée sur des entiers modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le domaine de la cryptologie.
Etant donnés une base b, un exposant e et un entier non nul m, l'exponentiation modulaire consiste à calculer c tel que :
Par exemple, si b = 5, e = 3, et m = 13, le calcul de c donne 8.
Calculer l'exponentiation modulaire est considéré comme facile, même lorsque les nombres en jeu sont énormes. Au contraire, calculer le logarithme discret (trouver e à partir de b, c et m) est reconnu comme difficile. Ce comportement de fonction à sens unique fait de l'exponentiation modulaire une bonne candidate pour être utilisée dans les algorithmes de cryptologie.
Le calcul naïf de l'exponentielle modulaire est le suivant : on multiplie e fois le nombre b par lui-même, et une fois l'entier be obtenu, on calcule son reste modulo m via l'algorithme de division euclidienne. Cette méthode souffre de deux défauts :
d'une part, le nombre de multiplications peut facilement être réduit, par la méthode générale d'exponentiation rapide : il n'y aura plus que log(e) multiplications à effectuer.
d'autre part, on ne profite pas de la structure d'anneau commutatif du domaine dans lequel on travaille : les entiers modulo m. Or, cette structure autorise que les calculs soient faits directement dans cet anneau, sans passage au préalable par les entiers. Pour mettre en œuvre cette idée, il faut en pratique, à chaque nouvelle multiplication effectuée, calculer un nouveau reste modulo m. On rajoute ainsi de nouvelles opérations (pour chaque multiplication, une division euclidienne), mais on gagne par ailleurs du fait que la taille des données à manipuler est limitée par celle de m.
La suite de l'article décrit ces différentes adaptations et discute leur efficacité en fonction notamment de la taille des données.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.