L'exponentiation modulaire rapide

RSA demande de calculer des choses comme m^65537 mod n, où n a 600 chiffres. Calculer m^65537 puis réduire est impossible : le nombre intermédiaire aurait des millions de chiffres.

Deux idées

Réduire à chaque étape. Puisque la multiplication passe au modulo, on réduit après chaque produit. Les nombres ne dépassent jamais la taille de n.

Élever au carré plutôt que multiplier un par un. Pour calculer a^16, on ne fait pas 15 multiplications :

a^2  = a × a
a^4  = a^2 × a^2
a^8  = a^4 × a^4
a^16 = a^8 × a^8

Quatre multiplications au lieu de quinze. Pour un exposant quelconque, on décompose en binaire.

Un exemple complet

Calculons 7^13 mod 11. En binaire, 13 = 1101.

7^1  ≡ 7          (mod 11)
7^2  ≡ 49 ≡ 5     (mod 11)
7^4  ≡ 5² = 25 ≡ 3   (mod 11)
7^8  ≡ 3² = 9     (mod 11)

Comme 13 = 8 + 4 + 1 :

7^13 ≡ 7^8 × 7^4 × 7^1
     ≡ 9 × 3 × 7
     ≡ 189
     ≡ 2       (mod 11)

Aucun nombre manipulé n'a dépassé 189.

Pourquoi c'est décisif

La méthode naïve demande un nombre de multiplications proportionnel à l'exposant. L'exponentiation rapide en demande un nombre proportionnel au nombre de chiffres de l'exposant.

Pour un exposant de 600 chiffres, on passe de 10^600 opérations — inconcevable — à quelques milliers. C'est cette différence qui rend RSA utilisable.

C'est aussi la dissymétrie centrale de la cryptographie moderne : certaines opérations sont rapides dans un sens et hors de portée dans l'autre.