Thursday, October 1, 2015

Modular arithmetic in Montgomery form

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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...