Anonymous user
Montgomery reduction: Difference between revisions
m
Tweak task description
No edit summary |
m (Tweak task description) |
||
Line 5:
* The numbers <math>m</math> (<math>n</math> digits long), <math>T</math> (<math>2n</math> digits long), <math>R</math>, <math>b</math>, <math>n</math> are known entities, a number <math>m'</math> (often represented as <code>m_dash</code> in code) = <math>-m^{-1} \mathrm{mod} b</math> is precomputed.
See the <!--<amazon id=0849385237>[%buy%--> Handbook of Applied Cryptography<!--]</amazon>--> for brief introduction to theory and numerical example in radix 10. Individual chapters of the book [http://www.cacr.math.uwaterloo.ca/hac/ can be viewed online] as provided by the authors. The said algorithm can be found at [http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf] at page 600 (page 11 of pdf file)
Algorithm:
A ← T (temporary variable)
For i from 0 to (n-1) do the following:
u<sub>i</sub> ← a<sub>i</sub>* m' mod b <span style="color: gray">// a<sub>i</sub> is the ith digit of A, u<sub>i</sub> is a single digit number in radix b</span>
A ← A + ui*m*b<sup>i</sup>
A ← A/b<sup>n</sup>
if A >= m,
A ← A - m
Return (A)
| |||