Montgomery reduction: Difference between revisions
Content added Content deleted
No edit summary |
(Added back online viewing book link (shouldn't expect readers to fork over $70 just to work on this task. Unless the Amazon link carries commissions for this site, it needs not to exist); restore subscript i as in the book) |
||
| Line 5: | 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. |
* 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. |
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. |
||
Algorithm: |
Algorithm: |
||
A ← T (temporary variable) |
A ← T (temporary variable) |
||
For i from 0 to (n-1) do the following: |
For i from 0 to (n-1) do the following: |
||
u<sub>i</sub> ← a<sub>i</sub>* m' mod b // a<sub>i</sub> is the ith digit of A, u<sub>i</sub> is a single digit number in radix b |
|||
A ← A + ui*m*b<sup>i</sup> |
A ← A + ui*m*b<sup>i</sup> |
||
A ← A/b<sup>n</sup> |
A ← A/b<sup>n</sup> |
||