Anonymous user
Montgomery reduction: Difference between revisions
m
small fixes
No edit summary |
m (small fixes) |
||
Line 4:
* 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
* 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
Wikipedia link for Montgomery Reduction
Line 12:
Algorithm:
A
For i from 0 to (n-1) do the following:
u<sub>i</sub>
A
A
if A >= m, A
Return (A)
=={{header|C++}}==
Line 105:
cout<<"Montgomery domain representation = "<<e;
return 0;
}</lang>▼
▲</lang>
| |||