Réduction de Montgomery
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
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 = ab [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.
L'algorithme utilisé pour calculer cette valeur est beaucoup plus efficient que la méthode classique de prendre un produit sur les nombres entiers et de réduire le résultat modulo n.
