Bonjour Monsieur,
Je suis actuellement en classe préparatoire MP au lycée Henri Poincaré de Nancy et je souhaiterais obtenir des informations sur l'exponentiation modulaire car je réalise un TIPE sur la cryptographie et plus particulièrement le système RSA. pourriez-vous m'indiquez en quoi consiste l'exponentiation modulaire et comment cela fonctionne.
je vous remercie d'avance.
Bonjour,
Ici, on notera
% la division modulaire, comme en programmation plutôt que comme
en
algèbre. Pour évaluer par exemple 1268 % 71,
on peut y aller naïvement en évaluant
(12 
12 .... 12 12)
et en prenant le reste de la division par 71, mais cette méthode
prend beaucoup de temps (67 multiplications par 12) et beaucoup d'espace
(le résultat de la multiplication a plus de 70 chiffres)
On peut y aller plus efficacement par mises au carré successives:
| Exposant | Valeur | Résultat |
|---|---|---|
| 68 | 12 | 1 |
| 34 | (12 12) % 71 = 2 |
1 |
| 17 | (2 2) % 71 = 4 |
(1 4) % 71 = 4 |
| 8 | (4 4) % 71 = 16 |
4 |
| 4 | (16 16) % 71 = 43 |
4 |
| 2 | (43 43) % 71 = 3 |
4 |
| 1 | (3 3) % 71 = 9 |
(4 9) % 71 = 36 |
Ainsi, 1268 % 71 = 36. Le calcul s'est effectue comme suit:
1268 % 71 = [(124 % 71) (1264 %
71)] % 71. On peut effectuer le calcul des puissance
121 % 71, 122 % 71, 124 % 71, 128 % 71, ...
récursivement, en mettant la valeur précédente au carré et prenant le reste modulo 71. C'est ici le calcul de la colonne du millieu.
La question à savoir lesquelles de ces puissances
doit on multiplier ensemble pour obtenir le résultat dépend
des puissance de 2 qu'on doit additionner ensemble pour obtenir l'exposant
(ici 68 = 4 + 64) donc de l'expression de l'exposant en base 2. On l'obtient
en divisant successivement l'exposant par 2
sans tenir compte du reste (c'est la colonne de gauche) et en multipliant
ensemble (dans la colonne de droite) les valeurs correspondant à un
nombre impair de la colonne de gauche. Conclusions:
- En prenant toujours le reste modulo 71, on évite
d'avoir à manipuler
des gros nombres. - Surtout, avec les mises au carré successives, on diminue de beaucoup le nombre de multiplications à effectuer (ici, 8 plutot que 67).
Les nombres employés en cryptographie sont beaucoup plus grands, mais l'efficacité de l'exponentiation modulaire est toujours valide. Le système de Diffie-Hellmann repose sur l'efficacité relative de l'exponentiation modulaire par rapport au probleme inverse du logarithme discret, et le système RSA repose sur l'efficacité relative de l'exponentiation modulaire par rapport à l'extraction de racines dans un module dont on ne connait pas les facteurs premiers. L'Introduction à l'algorithmique de Cormen, Leiserson et Rivest explique assez bien le sujet.
Claude