Revision as of 02:14, 21 December 2011 (view source) rosettacode>Dkf m (small fixes) ← Older edit		Revision as of 02:16, 21 December 2011 (view source) rosettacode>Dkf m (small fixes) Newer edit →
Line 2: This is sample code in C++ for implementing Montgomery Reduction algorithm as explained in "Handbook of Applied Cryptography, Section 14.3.2, page 600 * let M be a positive integer, R and T integers such that R>m, gcd(m, R) = 10<= T < mR * Montgomery reduction calculates T(R^<sup>-1</sup>) mod m, without having to divide by m R is usually chosen as b^<sup>n</sup>, where b = base (radix) in which the numbers in the calculation as represented in [b = 10 in our normal paper arithmetics, b = 2 for computer implementations] and n = number of bits in modulus 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<sup>-1</sup> mod b is precomputed

Montgomery reduction: Difference between revisions

Montgomery reduction (view source)