Montgomery reduction: Difference between revisions

This is sample code in C++ for implementing Montgomery Reduction algorithm as explained in "Handbook of Applied Cryptography, Section 14.3.2, page 600. Montgomery reduction calculates T*(R^-1) mod m, without having to divide by m.

* Let M be a positive integer, and R and T integers such that R > m, gcd(m, R) = 1, and 0 <= T < mR.

* R is usually chosen as bⁿ, where b = base (radix) in which the numbers in the calculation as represented in [b = 10 in 'normal' paper arithmetic, b = 2 for computer implementations] and n = number of digits in base m

* The numbers m(n digits long), T (2n digits long), R, b, n are known entities, a number m' (represented m_dash in code) = -m^-1 mod b is precomputed.

Wikipedia link: [[Wikipedia:Montgomery reduction|Montgomery reduction]].

See Handbook of Applied Cryptography for brief introduction to theory and numerical example in radix 10.