Montgomery reduction: Difference between revisions
Content added Content deleted
m (Tweak task description) |
m (correction) |
||
| Line 11: | Line 11: | ||
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 <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> |
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 + |
A ← A + u<sub>i</sub>*m*b<sup>i</sup> |
||
A ← A/b<sup>n</sup> |
A ← A/b<sup>n</sup> |
||
if A >= m, |
if A >= m, |
||