Réduction de Montgomery

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (avril 2016).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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[modifier | modifier le code]

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[modifier | modifier le 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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

[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[modifier | modifier le code]

Liens externes[modifier | modifier le code]

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