Anonymous user
Montgomery reduction: Difference between revisions
no edit summary
(Go solution) |
No edit summary |
||
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 <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:
| |||