Réduction de Montgomery
De Wikipedia, l'encyclopédie encyclopedia
La réduction de Montgomery est un algorithme efficace pour la multiplication en arithmétique modulaire introduit en 1985 par Peter L. Montgomery. Plus concrètement, cette méthode permet de calculer :
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
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. Elle est donc particulièrement adaptée au calcul d'exponentiation modulaire.
Elle est aujourd'hui très utilisée en cryptologie.