Montgomery reduction: Difference between revisions
Content added Content deleted
No edit summary |
m (Tweak task description) |
||
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. 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) |
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: |
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 |
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 + ui*m*b<sup>i</sup> |
||
A ← A/b<sup>n</sup> |
A ← A/b<sup>n</sup> |
||
if A >= m, |
if A >= m, |
||
A ← A - m |
|||
Return (A) |
Return (A) |
||