Réduction de Barrett

En arithmétique modulaire, la réduction de Barrett est un algorithme de réduction introduit en 1986 par Paul D. Barrett. Une façon naïve de calculer :

$c=a\,{\bmod {\,}}n\,$

serait d'utiliser un algorithme de division rapide ; la réduction de Barrett est un algorithme conçu pour optimiser cette opération en supposant $n$ constant et $a<n^{2}$, remplaçant les divisions par des multiplications.

Idée générale

Soit $s=1/n$ l'inverse de $n$ comme nombre à virgule flottante. Alors

$a\,{\bmod {\,}}n=a-\lfloor as\rfloor n$

où $\lfloor x\rfloor$ est la fonction partie entière. Le résultat est exact, tant que $s$ est calculé avec une précision suffisante.

Réduction de Barrett à un mot machine

Barrett a initialement considéré une version de l'algorithme ci-dessus sur les nombres entiers qui tiennent dans un seul mot machine.

En calculant $a\,{\bmod {\,}}n$ avec la méthode ci-dessus, mais avec des entiers, l'analogue évident serait la division par $n$:

func reduire(a uint) uint {
  q := a / n  // La division retourne implicitement la partie entière du résultat
  return a - q * n
}

Cependant, la division est lente et, dans les algorithmes de cryptographie, peut ne pas être une opération en temps constant sur certains processeurs. Ainsi, la réduction de Barrett approxime $1/n$ par la valeur $m/2^{k}$, car la division par $2^{k}$ est juste un décalage de bits vers la droite, donc est très rapide.

Afin de calculer la meilleure valeur pour $m$ étant donné $2^{k}$, on considère :

${\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}$

Pour que $m$ soit un entier, on a besoin d'arrondir ${2^{k}}/{n}$ d'une certaine manière. Arrondir à l'entier le plus proche donnerait la meilleure approximation mais peut faire que $m/2^{k}$ soit plus grand que $1/n$, qui peut provoquer un soupassement arithmétique. Ainsi, $m=\lfloor {2^{k}}/{n}\rfloor$ est généralement utilisé.

La fonction reduire ci-dessus peut donc être approximée par :

func reduire(a uint) uint {
  q := (a * m) >> k // ">> k" est le décalage de k bits vers la droite.
  return a - q * n
}

Cependant, puisque $m/2^{k}\leq 1/n$, la valeur de $q$ dans cette fonction peut être un peu trop petite, et ainsi $a$ est seulement garantie d'être dans $[0,2n[$ plutôt que $[0,n)$ comme c'est généralement requis. Une soustraction conditionnelle peut corriger cela :

func reduire(a uint) uint {
  q := (a * m) >> k
  a -= q * n
  if n <= a {
    a -= n
  }
  return a
}

Puisque $m/2^{k}$ est seulement une approximation, l'intervalle de validité de $a$ doit être considéré. L'erreur sur l'approximation de $1/n$ est:

$e={\frac {1}{n}}-{\frac {m}{2^{k}}}$

Ainsi, l'erreur sur la valeur de $q$ est $ae$. Tant que $ae<1$, la réduction sera valide, d'où $a<1/e$. La fonction de réduction peut ne pas donner immédiatement un mauvais résultat quand $a\geq 1/e$ mais la borne sur $a$ doit être respectée pour garantir une réponse correcte dans le cas général.

En choisissant de plus grandes valeurs de $k$, l'intervalle des valeurs de $a$ pour lesquelles la réduction est valide peut-être augmentée, mais de plus grandes valeurs de $k$ peut causer des dépassements d'entiers.

Exemple

Regardons le cas $n=101$ en utilisant des entiers de 16 bits.

La plus petite valeur de $k$ qui a du sens est $k=7$ car si $2^{k}<n$ alors la réduction ne sera valide que pour des valeurs qui sont déjà minimales ! Pour une valeur de sept, $m=\lfloor 2^{k}/n\rfloor =\lfloor 128/101\rfloor =1$. Pour une valeur de huit $m=\lfloor 256/101\rfloor =2$. Ainsi $k=8$ ne donne aucun avantage car l'approximation de $1/101$, dans ce cas $2/256$, est exactement la même que $1/128$. Pour $k=9$, on obtient $m=512/101=5$, qui donne une meilleure approximation.

Maintenant, considérons les intervalles de validité pour $k=7$ et $k=9$.

Dans le premier cas, $e=1/n-m/2^{k}=1/101-1/128=27/12928$ donc $a<1/e$ implique $a<478.81$. Puisque $a$ est un entier, la valeur maximum effective est 478. (En pratique la fonction donne le bon résultat jusque 504.)

Si on prend $k=9$ alors $e=1/101-5/512=7/51712$ et donc la valeur maximum de $a$ est 7387. (En pratique la fonction donne le bon résultat jusque 7473.)

La valeur suivante de $k$ qui donne une meilleure approximation est 13, donnant $81/8192$. Cependant, notons que la valeur intermédiaire $ax$ dans les calculs va dépasser la capacité d'un entier 16 bits non-signé lorsque $810\leq a$, ainsi $k=7$ fonctionne mieux dans cette situation.

Preuve de l'intervalle de validité pour un certain k

Soit $k_{0}$ le plus petit entier tel que $2^{k_{0}}>n$. Prenons $k_{0}+1$ comme valeur raisonnable pour $k$ dans les équations précédentes. Comme dans les fragments de code ci-dessus, soit

• $q=\left\lfloor {\frac {ma}{2^{k}}}\right\rfloor$ et
• $r=a-qn$.

Grâce à la fonction partie entière, $q$ est un entier et $r\equiv a{\pmod {n}}$. Aussi, si $a<2^{k}$ alors $r<2n$. Dans ce cas, en écrivant le fragment de code en expression :

$a\,{\bmod {\,}}n={\begin{cases}r&{\text{si }}r<n\\r-n&{\text{sinon}}\end{cases}}$

La preuve que $r<2n$ est alors immédiate :

Si $a<2^{k}$, alors

${\frac {a}{2^{k}}}\cdot (2^{k}\mod n)<n$

Puisque $n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<n$ indépendamment de $a$, on obtient :

${\frac {a\cdot (2^{k}\mod n)}{2^{k}}}+n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<2n$

$a-\left(a-{\frac {a\cdot (2^{k}\mod n)}{2^{k}}}\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n$

$a-{\frac {a}{2^{k}}}\cdot \left(2^{k}-(2^{k}\mod n)\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n$

$a-{\frac {na}{2^{k}}}\cdot \left({\frac {2^{k}-(2^{k}\mod n)}{n}}\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n$

$a-{\frac {na}{2^{k}}}\cdot \left\lfloor {\frac {2^{k}}{n}}\right\rfloor \ +{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n$

$a-{\frac {nma}{2^{k}}}+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n$

$a-\left({\frac {ma-(ma\mod 2^{k})}{2^{k}}}\right)\cdot n<2n$

$a-\left\lfloor {\frac {ma}{2^{k}}}\right\rfloor \cdot n<2n$

$a-qn<2n$

$r<2n$

Réduction de Barrett à plusieurs mots machine

La motivation initiale de Barrett pour sa réduction était l'implémentation de RSA, lorsque les valeurs en question dépassent la taille d'un mot machine. Dans cette situation, Barrett donne un algorithme qui approxime la version à un mot ci-dessus mais pour des valeurs sur plusieurs mots. Pour plus de détails, voir la section 14.3.3 de Handbook of Applied Cryptography.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Barrett reduction » (voir la liste des auteurs).

Voir aussi

• La réduction de Montgomery est un autre algorithme similaire.

Sources

• A. Bosselaers, R. Govaerts, J. Vandewalle et Douglas R. Stinson (dir.), Advances in Cryptology — Crypto'93, vol. 773, Springer, coll. « Lecture Notes in Computer Science », 1993, 175–186 p. (ISBN 3-540-48329-2, lire en ligne), « Comparison of Three Modular Reduction Functions »
• W. Hasenplaugh, G. Gaubatz et V. Gopal, 18th IEEE Symposium on Computer Arithmetic(ARITH'07), 2007, 225-9 p. (ISBN 978-0-7695-2854-0 et 0-7695-2854-6, DOI 10.1109/ARITH.2007.18, lire en ligne), « Fast Modular Reduction »