Anonymous user
Montgomery reduction: Difference between revisions
cleanup task description
m (small fixes) |
(cleanup task description) |
||
Line 1:
{{draft task}}
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<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
*
▲* 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
Wikipedia link:
See Handbook of Applied Cryptography for brief introduction to theory and numerical example in radix 10.
Algorithm:
Line 19 ⟶ 17:
if A >= m, A ← A - m
Return (A)
=={{header|C++}}==
<lang cpp>#include<iostream>
| |||