Montgomery reduction: Difference between revisions
Content added Content deleted
No edit summary |
m (small fixes) |
||
| Line 4: | Line 4: | ||
* Montgomery reduction calculates T*(R^-1) mod m, without having to divide by m |
* Montgomery reduction calculates T*(R^-1) mod m, without having to divide by m |
||
* R is usually chosen as b^n, 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 |
* R is usually chosen as b^n, 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 |
* 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 |
||
Wikipedia link for Montgomery Reduction |
Wikipedia link for Montgomery Reduction |
||
| Line 12: | Line 12: | ||
Algorithm: |
Algorithm: |
||
A |
A ← T (temporary variable) |
||
For i from 0 to (n-1) do the following: |
For i from 0 to (n-1) do the following: |
||
u<sub>i</sub> |
u<sub>i</sub> ← a<sub>i</sub>* m' mod b // a<sub>i</sub> is the ith digit of A, u<sub>i</sub> is a single digit number in radix b |
||
A |
A ← A + u<sub>i</sub>*m*b<sup>i</sup> |
||
A |
A ← A/b<sup>n</sup> |
||
if A >= m, A |
if A >= m, A ← A - m |
||
Return (A) |
Return (A) |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
| Line 105: | Line 105: | ||
cout<<"Montgomery domain representation = "<<e; |
cout<<"Montgomery domain representation = "<<e; |
||
return 0; |
return 0; |
||
| ⚫ | |||
} |
|||
| ⚫ | |||