Cryptography Reference
In-Depth Information
This principle of carrying out reduction modulo
n
is called
Montgomery
reduction
. Below, we shall institute Montgomery reduction for the express
purpose of speeding up modular exponentiation significantly in comparison to
our previous results. Since the procedure requires that
n
and
r
be relatively prime,
we must take
n
to be odd. First we have to deal with a couple of considerations.
We can clarify the correctness of the previous congruence with the help
of some simple checking. Let us replace
m
on the left-hand side of (6.8) by
the expression
tn
mod
r
, which is (6.9), and further, replace
tn
mod
r
by
tn
− r
tn
/r
∈
Z
to get (6.10), and then in (6.10) for
n
the integer expression
r
r −
1
/n
for a certain
r
∈
Z
and obtain (6.11). After reduction modulo
n
we
obtain the result (6.12):
t
+
n
tn
mod
r
r
t
+
mn
r
≡
(6.9)
− n
tn
r
t
+
ntn
r
≡
(6.10)
t
+
t
rr
−
1
≡
(6.11)
r
≡ tr
−
1
mod
n.
(6.12)
To summarize equation (6.8) we record the following: Let
n, t, r
∈
Z
with
gcd(
n, r
)=1
,
n
:=
−n
−
1
mod
r
.For
f
(
t
):=
t
+
tn
mod
r
n
(6.13)
we have
f
(
t
)
≡ t
mod
n,
(6.14)
f
(
t
)
≡
0mod
r.
(6.15)
We shall return to this result later.
To apply Montgomery reduction we shift our calculations modulo
n
into a
complete residue system (cf. Chapter 5)
R
:=
R
(
r, n
):=
{
ir
mod
n
|
0
≤
i<n
}
with a suitable
r
:= 2
s
>
0
such that
2
s
−
1
n<
2
s
. Then we define the
≤
” of two numbers
a
and
b
in
R
:
a × b
:=
abr
−
1
mod
n,
with
r
−
1
representing the multiplicative inverse of
r
modulo
n
.Wehave
a × b ≡
(
ir
)(
jr
)
r
−
1
×
Montgomery product
“
≡
(
ij
)
r
mod
n ∈ R,
to members of
R
is again in
R
. The Montgomery
product is formed by applying Montgomery reduction, where again
n
:=
−
×
and thus the result of applying
n
−
1
mod
r
.From
n
we derive the representation
1 = gcd(
n, r
)=
r
r
n
n
,
−
