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.

Cette méthode permet de calculer le produit $a\ \times \ b{\pmod {n}}$ en évitant les divisions par n, coûteuses en tant de calcul, et en leur substituant des divisions par un nombre R pour lequel ces divisions sont plus rapides (par exemple lorsque R est une puissance du mot de base utilisé par le processeur pour effectuer ses calculs, les divisions revenant alors à des décalages de registres).

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 sur les données en début de calcul, et sur les résultats en fin de calcul. 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. On se donne un entier R > n premier avec n et on calcule au préalable et une fois pour toutes les entiers R⁻¹ et n' satisfaisant l'identité de Bézout :

$RR^{-1}-nn'=1$, avec 0 < R⁻¹ < n et 0 < n' < R.

R⁻¹ est l'inverse modulaire de R, pour la multiplication modulo n.

Usuellement, une classe d'entiers modulo n est représentée par l'un de ses éléments x, souvent l'élément compris entre 0 et n-1 :

$C(x)=\{y,n\;{\textrm {divise}}\;y-x\}$

Montgomery propose que l'entier x représente non pas C(x), mais C(x R⁻¹).

Si T est un entier tel que 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}}$.

Elle associe donc à T un élément de la classe que T représente au sens de Montgoméry.

Pseudo-code

La fonction de réduction peut être décrite à l'aide du pseudo-code suivant. On suppose que les constantes globales n et R ont déjà été initialisée et que la constante n' définie précédemment a également été calculée. Cette dernière est désignée ci-dessous par ninv :

fonction reduction(T) {

  /* Calcul du nombre m de multiples de N à ajouter T */
  /*  pour que T + m*n soit divisible par 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;

}

On remarque que le calcul se fait modulo R ou par division par R (supposé moins coûteux pour la machine) et non plus modulo n.

Démonstration

La preuve de la validité de l'algorithme se fait comme suit. On a, modulo R :

$T+mn\equiv T+(Tn')n\mod R\equiv T(1+n'n)\mod R\equiv TRR^{-1}\mod R\equiv 0\mod R$

donc la division calculant la première valeur de x est exacte. Ce dernier nombre est un entier.

Ensuite, modulo n :

$xR-TRR^{-1}\equiv T+mn-T(1+nn')\mod n\equiv 0\mod n$

et comme n est premier avec R, $x-TR^{-1}\equiv 0\mod n$, donc $x\equiv TR^{-1}\mod n$.

Enfin, $0\leq T+mn<T+Rn<2Rn$ donc $0<(T+mn)/R<2n$, d'où le test final pour obtenir une valeur de x comprise entre 0 et n - 1.

Normalisation des données

Afin d'utiliser la réduction de Montgomery sur des données x, y, etc. connues modulo n, il convient dans un premier temps de déterminer les entiers a, b, etc. qui représenteront au sens de Montgoméry les classes C(x), C(y), etc. Ces entiers ne sont autres que xR modulo n, yR modulo n, etc. ou encore xR²R⁻¹ modulo n, yR²R⁻¹ modulo n, etc. ou enfin a= reduction(x(R² mod n)), b = reduction(y(R² mod n)), etc. Il est donc utile d'avoir également calculé au préalable et une fois pour toute R² mod n.

Les calculs sont alors effectués sur les représentants a, b, etc, jusqu'à un résultat final c, qui est le représentant final au sens de Montgoméry de la classe de z = cR⁻¹ = reduction(c). C'est ce dernier entier qui est le résultat attendu des opérations portant sur les données initiales x, y, etc.

Cette démarche est appliquée ci-dessous dans le cas du produit.

Multiplication de Montgomery

L'algorithme de la multiplication de Montgomery est très simple. Une fois calculés les représentants a et b au sens de Montgoméry de deux entiers x et y, on calcule c = reduction(ab). Le produit xy modulo n n'est autre que z = reduction(c). On notera qu'aucun des calculs précédents ne nécessite une division par n, alors même que le résultat final est connu modulo n.

En effet, on a :

$a\equiv xR\mod n,b\equiv yR\mod n$

donc :

$c={\textrm {reduction}}(ab)\equiv abR^{-1}\mod n\equiv xRyRR^{-1}\mod n\equiv xyR\mod n$

donc :

$z={\textrm {reduction}}(c)\equiv cR^{-1}\mod n\equiv xy\mod n$.

Exemple en base 10

On souhaite effectuer des calculs modulo n = 293. On choisit R = 1000. On calcule au préalable les entiers R⁻¹ et n' satisfaisant $RR^{-1}-nn'=1$, avec 0 < R⁻¹ < n et 0 < n' < R. On vérifiera que R⁻¹ = 247 et n' = 843 répondent à la question. On calcule également au préalable R² mod n = 284.

Soit maintenant à calculer 234 × 167 mod 293, les seules divisions effectuées étant par 1000.

• Le représentant de Montgomery a de 234 est reduction(234 × 284) = reduction(66456). L'application de l'algorithme donne :

m = ((66456 mod 1000) × 843) mod 1000 = (456 × 843) mod 1000 = 384408 mod 1000 = 408

a = (66456 + 408×293)/1000 = 186000/1000 = 186

• Le représentant de Montgomery b de 167 est reduction(167 × 284) = reduction(47428). L'application de l'algorithme donne :

m = ((47428 mod 1000) × 843) mod 1000 = (428 × 843) mod 1000 = 360804 mod 1000 = 804

b = (47428 + 804×293)/1000 = 283000/1000 = 283

• On calcule c = reduction(ab) = reduction(186×283) = reduction(52638) :

m = ((52638 mod 1000) × 843) mod 1000 = (638 × 843) mod 1000 = 537834 mod 1000 = 834

c = (52638 + 834×293)/1000 = 297000/1000 = 297 ≡ 297 - 293 = 4

• On normalise le résultat final en calculant z = reduction(4) :

m = ((4 mod 1000) × 843) mod 1000 = (4 × 843) mod 1000 = 3372 mod 1000 = 372

z = (4 + 372×293)/1000 = 109000/1000 = 109

Le résultat de 234 × 167 mod 293 est donc 109, ce qu'on pourra vérifier.

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