Mongomery Arithmetic
a
b
N
Completion time (msec):
Montgomery parameters
N
16
bits(N) = k
R=2
k
R-1
R
-1
(mod N)
N' =
(R*R
-1
- 1)/N
Calculate
Montgomery value
integer value
a
a
-1
b
b
-1
a + b
a * b
a
b