I am trying to apply an algorithm that requires significant modular arithmetic, but in such a way as to avoid as many costly mod
or division operations as possible.
I found the Montgomery multiplication method and its form of integer residues (via wikipedia and thus the original paper), but I am having difficulty understanding how to apply it practically.
Using the example in the wikipedia writeup, with $n = 17$ and an $R^{-1} = 8$, I can do very simple arithmetic with an implementation of redc
that matches the expected value $mod\ n$:
$ (7 * 15) `mod` n
3
$ redc (3 * 4 * r')
3
$ (7 + 15) `mod` n
5
$ redc (3 + 4)
5
However, while the original paper and the wikipedia page say explicitly that most arithmetic operations can be applied over residues as "normally used", I'm not seeing that borne out:
$ (7 * 15 * 15) `mod` n
11
$ redc (3 * 4 * 4 * r')
12
(I know this might be on the edge of this being a stackoverflow question, but I suspect I'm suffering from a formal misunderstanding here, rather than a simple programming error.)
No comments:
Post a Comment