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.)
1 Answer
$\def\redc{\mathrm{redc}}$ Throughout this post, the parameters $N$, $R$, and $R'$ will be implicit in function calls.
What is the operation?
The arithmetic primitive $\redc$ is meant to perform the operation:
$\redc(x) \equiv x R^{-1} \pmod N$. Additionally, if $x$ is large, then $\redc(x)$ will be smaller than $x$.
It's primary advantage over a more direct modular reduction algorithm is that the only divisions this algorithm does is division by $R$. When $R$ is a power of 2, this can be especially convenient for computer implementation. $R = 2^{32}$ and $R=2^{64}$ are popular choices, since the corresponding division operations are essentially free due to how the processor stores and manipulates integers in registers.
