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 :
 
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  constant et , remplaçant les divisions par des multiplications.

Idée générale 

Soit  l'inverse de  comme nombre à virgule flottante. Alors

où  est la fonction partie entière. Le résultat est exact, tant que  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  avec la méthode ci-dessus, mais avec des entiers, l'analogue évident serait la division par :

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  par la valeur , car la division par  est juste un décalage de bits vers la droite, donc est très rapide.

Afin de calculer la meilleure valeur pour  étant donné , on considère :

Pour que  soit un entier, on a besoin d'arrondir  d'une certaine manière. Arrondir à l'entier le plus proche donnerait la meilleure approximation mais peut faire que  soit plus grand que , qui peut provoquer un soupassement arithmétique. Ainsi,  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 , la valeur de  dans cette fonction peut être un peu trop petite, et ainsi  est seulement garantie d'être dans  plutôt que  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  est seulement une approximation, l'intervalle de validité de  doit être considéré. L'erreur sur l'approximation de  est:

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

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

Exemple 

Regardons le cas  en utilisant des entiers de 16 bits.

La plus petite valeur de  qui a du sens est  car si  alors la réduction ne sera valide que pour des valeurs qui sont déjà minimales ! Pour une valeur de sept, . Pour une valeur de huit . Ainsi  ne donne aucun avantage car l'approximation de , dans ce cas , est exactement la même que . Pour , on obtient , qui donne une meilleure approximation.

Maintenant, considérons les intervalles de validité pour  et .

Dans le premier cas,  donc  implique . Puisque  est un entier, la valeur maximum effective est 478. (En pratique la fonction donne le bon résultat jusque 504.)

Si on prend  alors  et donc la valeur maximum de  est 7387. (En pratique la fonction donne le bon résultat jusque 7473.)

La valeur suivante de  qui donne une meilleure approximation est 13, donnant . Cependant, notons que la valeur intermédiaire  dans les calculs va dépasser la capacité d'un entier 16 bits non-signé lorsque , ainsi  fonctionne mieux dans cette situation.

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

Soit  le plus petit entier tel que . Prenons  comme valeur raisonnable pour  dans les équations précédentes. Comme dans les fragments de code ci-dessus, soit

  et
 .

Grâce à la fonction partie entière,  est un entier et . Aussi, si  alors . Dans ce cas, en écrivant le fragment de code en expression :

La preuve que  est alors immédiate :

Si , alors

Puisque  indépendamment de , on obtient :

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

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

Sources 

Arithmétique modulaire
Arithmétique des ordinateurs