Montgomery reduction: Difference between revisions
Content added Content deleted
m (small fixes) |
m (small fixes) |
||
| Line 2: | 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 |
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 |
* 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 |
* Montgomery reduction calculates T*(R<sup>-1</sup>) mod m, without having to divide by m |
||
* R is usually chosen as b |
* 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 |
* 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 |
||