Cryptography Reference
In-Depth Information
Lemma 2.5.1
Let a,b
∈ Z
/n
Z
.
1. Computing a
b
(mod
n
)
can be done in O
(log(
n
))
bit operations.
2. Computing ab
(mod
n
)
can be done in O
(log(
n
)
2
)
bit operations.
3. Computing a
−
1
±
(mod
n
)
can be done in O
(log(
n
)
2
)
bit operations.
4. For a
∈ Z
, computing a
(mod
n
)
can be done in O
(log(
n
)(log(
a
)
−
log(
n
)
+
1))
bit
operations.
Montgomery multiplication
This method
5
is useful when one needs to perform an operation such as
a
m
(mod
n
) when
n
is odd. It is based on the fact that arithmetic modulo 2
s
is easier than arithmetic modulo
n
.Let
R
2
s
>n
(where
s
is typically a multiple of the word size).
=
Definition 2.5.2
Let
n
∈ N
be odd and
R
=
2
s
>n
.The
Montgomery representation
of
a
∈
(
Z
/n
Z
)is
a
=
aR
(mod
n
) such that 0
≤
a<n
.
To transform
a
into the Montgomery representation requires a standard modular mul-
tiplication. However, Lemma
2.5.3
shows that transforming back from the Montgomery
representation to standard representation may be performed more efficiently.
2
s
>n. Let n
=
Lemma 2.5.3
(Montgomery reduction) Let n
∈ N
be odd and R
=
n
−
1
n
<R. Let a be a
n
element of
(
−
(mod
R
)
be such that
1
≤
Z
/n
Z
)
in Mont-
an
(mod
R
)
. Then w
gome
r
y representation. Let u
=
=
(
a
+
un
)
/R lies in
Z
and satisfies
aR
−
1
w
≡
(mod
n
)
.
Proof
Write
w
=
un
. Clearly,
w
≡
w
≤
a
+
0(mod
R
)so
w
∈ Z
. Further, 0
≤
(
n
−
aR
−
1
1)
+
(
R
−
1)
n
=
Rn
−
1 and hence
w<n
. Finally, it is clear that
w
≡
(mod
n
).
The reason why this is efficient is that division by
R
is easy. The computation of
n
is also easier than a general modular inversion (see Algorithm II.5 of [
60
]) and, in many
applications, it can be precomputed.
We now sketch the
Montgomery multiplication
algorithm. If
a
and
b
are in Mont-
gomery r
epr
esentation then we want to
co
mpute the Montgomery representation of
ab
,
which is
abR
−
1
=
∈ Z
≤
x<n
2
<nR
, then compute
(mod
n
). Compute
x
ab
so that 0
xn
(mod
R
) and
w
=
. As in L
e
mma
2.5.3
,wehave
w
≡
u
=
x
+
nu
∈ Z
0(mod
R
) a
nd
w
/R
. It follows that
w
abR
−
1
can compute
w
=
≡
(mod
n
) and 0
≤
w<
2
n
so
ab
is
either
w
or
w
−
n
.
Lemma 2.5.4
The complexity of the Montgomery multiplication modulon is O
(
M
(log(
n
)))
bit operations.
For further details see Section 9.2.1 of [
150
], Section II.1.4 of [
60
], Section 11.1.2.b
of [
16
] or Section 2.2.4 of [
248
].
5
Credited to Montgomery [
391
], but apparently a similar idea was used by Hensel.