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, c'est une méthode pour calculer :

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

La méthode 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 maintenant 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, pgcd(n, R) = 1 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 de multiples à ajouter pour que */
  /* T + m*N soit divisible par R                     */
  ni = R - ModInverse(N, R);
  m = ((T mod R) * ni) mod R;  
  /* Ajout des multiples et décalage */
  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). Si l'on choisit R = 2^k et que ni 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 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

Notes et références

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])

Liens externes

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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.