Montgomery reduction: Difference between revisions
Content deleted Content added
m small fixes |
cleanup task description |
||
Line 1: | Line 1: | ||
{{draft task}} |
{{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 |
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. |
||
* |
* Let M be a positive integer, and R and T integers such that R > m, gcd(m, R) = 1, and 0 <= T < mR. |
||
⚫ | |||
* Montgomery reduction calculates T*(R<sup>-1</sup>) mod m, without having to divide by m |
|||
⚫ | |||
⚫ | |||
⚫ | |||
Wikipedia link |
Wikipedia link: [[Wikipedia:Montgomery reduction|Montgomery reduction]]. |
||
[http://en.wikipedia.org/wiki/Montgomery_reduction] |
|||
See Handbook of Applied Cryptography for brief introduction to theory and numerical example in radix 10 |
See Handbook of Applied Cryptography for brief introduction to theory and numerical example in radix 10. |
||
Algorithm: |
Algorithm: |
||
Line 19: | Line 17: | ||
if A >= m, A ← A - m |
if A >= m, A ← A - m |
||
Return (A) |
Return (A) |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
<lang cpp>#include<iostream> |
<lang cpp>#include<iostream> |