Réduction de Montgomery
Un article de Wikipédia, l'encyclopédie libre.
La réduction de Montgomery est un algorithme efficace pour la multiplication en arithmétique modulaire introduite en 1985 par Peter L. Montgomery. Plus concrètement, c'est une méthode pour calculer
- c = a^b [mod n]
où a, b, et n sont des nombres binaires de k bits. Elle est maintenant particulièrement appliquée en cryptologie.
[modifier] Enoncé formel
Soit n est un nombre entier positif, et soit R et T des entiers tels que R > n, pgcd(n,R) = 1 et 
. La réduction de Montgomery de T modulo n qui préserve R est défini comme la valeur
R − 1 est l'inverse modulaire de R et mod désigne la congruence sur les entiers.
L'algorithme utilisé pour calculer cette valeur est beaucoup plus efficace que la méthode classique de prendre un produit sur les nombres entiers et de réduire le résultat modulo n.
