Réduction de Montgomery

La réduction de Montgomery est un algorithme efficace pour la multiplication en arithmétique modulaire introduit en 1985 par Peter L. Montgomery. Plus concrètement, cette méthode permet de calculer :

$a\ \times \ b{\pmod {n}}.$

Elle est surtout efficace lorsqu'un grand nombre de multiplications modulaires avec un même n doivent être effectuées car le calcul nécessite des étapes de normalisation. Elle est donc particulièrement adaptée au calcul d'exponentiation modulaire.

$a^{b}{\pmod {n}}.$

Elle est aujourd'hui très utilisée en cryptologie.

Définition de la réduction

Soit n un entier strictement positif et soient R et T des entiers tels que R > n, avec R et n premier entre eux et 0 ≤ T < nR. La réduction de Montgomery de T modulo n relativement à R est définie comme la valeur

$T\,R^{-1}{\pmod {n}},$

où R⁻¹ est l'inverse modulaire de R, pour la multiplication mod n, et mod désigne la congruence sur les entiers.

Pseudo-code

La fonction de réduction peut être décrite à l'aide du pseudo-code suivant :

fonction reduction(T, n, R) {

  /* Calcul du nombre m de multiples de N à ajouter T */
  /*  pour que T + m*n soit divisible par R           */
  ninv = R - ModInverse(n, R);
  m = ((T mod R) * ninv) mod R;  
  /* Ajout des multiples et décalage éventuel */
  x = (T + m*n) / R;           
  if (x < n)  return x;
  else        return x - n;

}

où ModInverse(n, R) désigne l'inverse modulaire de n (mod R). On choisit généralement R sous forme d'une puissance de 2 de façon que les calculs modulo R se traduisent en binaire par un simple décalages de bits. Par ailleurs, ninv peut être pré-calculé. Alors la fonction ci-dessus se réduit à deux multiplications (en négligeant le temps pris par les autres opérations moins coûteuses).

Multiplication de Montgomery

L'algorithme de la multiplication de Montgomery est très simple. Il suffit à chaque pas (ligne) d'une multiplication classique d'ajouter un multiple de n bien choisi de façon à faire apparaître des 0 dans le résultat. Le modulo n se réduit alors à un simple décalage des chiffres. Cette opération d'ajout de multiples de n est autorisée puisque l'on travaille avec modulo n. Un choix de R classique en base 2 consiste à prendre R = 2^k mod n, 2^k > n et k multiple de 32. L'algorithme calcule abR⁻¹ mod n. Attention, dans certains cas, l'algorithme retourne un résultat compris entre n et 2n. Il faut alors retrancher n au résultat.

Exemple en base 10

Soit à calculer $234\times 167{\pmod {293}},$ on choisit $R=10^{6}{\pmod {293}}=284$ pour 6 chiffres, il suffit de multiplier a ou b par R pour obtenir $a\,b\,R\,R^{-1}{\pmod {n}}=a\,b{\pmod {n}}.$ En choisissant a ou b égal à 1, on obtient une réduction modulo n simple. R (ici réduit mod n) étant inférieur à n, la condition a, b < R (non réduit) est suffisante pour éviter un dépassement.

   066456  (234*284)
 × 000167
   ------
1) 465192  (7*66456)
  +  1758  (6×293)
   466950
   ------
2) 445431  (6*66456 + 466950/10)
  +   879  (3×293)
   446310  
   ------
3) 111087  (1*66456 + 446310/10)
  +   293  (1×293)
   111380  
   ------
4)  11138  (0*66456 + 111380/10)
  +  1172  (4×293)
    12310  
   ------
5)   1231  (0*66456 + 12310/10)
  +   879  (3×293)
     2110  
   ------
6)    211  (0*66456 + 2110/10)
  +   879  (3×293)
     1090
   ------
  =   109

On obtient bien le résultat, néanmoins il faut effectuer la normalisation (*284), ce qui coûte une multiplication supplémentaire et un nombre de chiffres plus grand mais ce procédé peut être adapté en fonction du besoin de façon à minimiser le nombre de multiplications ainsi que le nombre de chiffres nécessaires. Le calcul du nombre de multiples à ajouter à chaque ligne requiert l'inversion modulaire d'un seul chiffre, ici le 3 de 293 (voir ci-dessous). À noter qu'en base 10, n ne peut pas se terminer par 0, 2, 4, 5, 6 ou 8. L'utilisation d'une base 2^p est beaucoup plus pratique.

Exemple pour l'étape 1) , on a 3⁻¹ = 7 mod 10, on veut trouver b tel que 2 + 3b = 0 mod 10.

       2 + b*3 = 0        (mod 10)
       b*3     = -2       (mod 10) = 8  (mod 10)
       b       = 8 * 3^-1 (mod 10)
       b       = 8 * 7    (mod 10) = 56 (mod 10) = 6

Annexes

Bibliographie

• [Montgomery 1985] (en) Peter L. Montgomery, « Modular Multiplication Without Trial Division », Mathematics of Computation, vol. 44, n^o 170,‎ avril 1985, p. 519–521 (lire en ligne [PDF])

Articles connexes

• Exponentiation rapide
• Multiplication de Kochanski (en)
• Réduction de Barrett

Liens externes

• (en) Implémentation dans divers langages, sur rosettacode.org