Exponentiation rapide

 

L'algorithme suivant est utilisé pour le calcul de x=me mod n et m=xd mod n, qui servent à crypter et décrypter le message. En effet, lorsque les valeurs de e et de d sont élevées, le calcul ne peut se faire facilement en calculant la puissance puis le modulo.

Cet algorithme appelé repeated square and multiply algorithm permet simplement et rapidement d'effectuer un tel calcul en utilisant l'écriture binaire de l'exposant. Sa complexité est proportionnelle au logarithme de l'exposant (nombre de chiffre).

 

Principe de l'algorithme pour le calcul de ak mod n

On exprime k en numération binaire. Par exemple, si k s'écrit 10011010 (k=154), on a :
k=2+8+16+128 et alors ak=a2.a8.a16.a128

La suite a1, a2, a4, a8, a16, a32, a64, a128 est obtenue par élévation au carré successives.
Pour le calcul de ak, il suffit de prendre chacun des chiffres binaires de l'exposant k en partant de droite et d'effectuer les opérations (au départ, p=1) :

Le résultat est alors donné par la dernière valeur prise par p.

Algorithme théorique de la fonction à utiliser (en C)

  long puissance (long a, long k, long n) {
    for ( p=1 ; k>0 ; k=k/2 ) {
      if ( k % 2 != 0 )   p = ( p * a ) % n
      a =( a * a ) % n 
    }
    return p;
  }

 

Exemples de calcul

Comment, par exemple calculer le 4137 mod 527 (= 113) qui intervient dans l'exemple de cryptage avec cet algorithme ?

a = 41
k = 37 s'écrit, en binnaire, 100101
n=527

p=1 au départ.

on lit les bits de droite à gauche :

le premier chiffre binaire vaut 1 donc :
p devient égal à p*a mod n = 1*41 mod 527 = 41
a devient égal à a2 mod 527 = 412 mod 527 = 1681 mod 527 = 100

le second chiffre binaire vaut 0 donc :
p inchangé
a devient égal à a2 mod 527 = 1002 mod 527 = 10000 mod 527 = 514

le 3ème chiffre binaire vaut 1 donc :
p devient égal à p*a mod n = 41*514 mod 527 = 521
a devient égal à a2 mod 527 = 5142 mod 527 = 169

le 4ème chiffre binaire vaut 0 donc :
p reste égal à 521
a devient égal à a2 mod 527 = 1692 mod 527 = 103

le 5ème chiffre binaire vaut 0 donc :
p = 521
a devient égal à a2 mod 527 = 1032 mod 527 = 69

le 6ème chiffre binaire vaut 1 donc :
p devient égal à p*a mod n = 521*69 mod 527 = 113

p=113 est le résultat du calcul cherché.

 

Cet algorithme devient très vite interressant pour les grands nombres.

 

 

[ Retour présentation de RSA | Une utilisation de RSA | Exemple | Euclide ]

Mynath 2000 - www.mynath.t2u.com