Cryptography Reference
In-Depth Information
which we calculate in anticipation of Section 10.2 with the help of the extended
Euclidean algorithm. From this representation of
1
we immediately obtain
1
≡ r
r
mod
n
and
1
≡−n
n
mod
r,
so that
r
=
r
−
1
mod
n
is the multiplicative inverse of
r
modulo
n
,and
n
=
−n
−
1
mod
r
the negative of the inverse of
n
modulo
r
(we are anticipating
somewhat; cf. Section 10.2). The calculation of the Montgomery product now
takes place according to the following algorithm.
Calculation of the Montgomery product
a
×
b
in
R
(
r, n
)
1.
Set
t
←
ab
.
tn
mod
r
.
2.
Set
m
←
3.
Set
u ←
(
t
+
mn
)
/r
(the quotient is an integer; see above).
4.
If
u ≥ n
, output
u − n
, and otherwise
u
. Based on the above selection of
the parameter we have
a, b < n
as well as
m, n < r
and finally
u<
2
n
;cf.
(6.21).
The Montgomery product requires three long-integer multiplications, one in
step 1 and two for the reduction in steps 2 and 3. An example with small numbers
will clarify the situation: Let
a
= 386
,
b
= 257
,and
n
= 533
. Further, let
r
=2
10
.
Then
n
=
n
−
1
mod
r
= 707
,
m
=6
,
t
+
mn
= 102400
,and
u
= 100
.
A modular multiplication
ab
mod
n
with odd
n
can now be carried out by
first transforming
a
← ar
mod
n
and
b
← br
mod
n
to
R
, there forming
the Montgomery product
p
← a
× b
=
a
b
r
−
1
mod
n
and then with
p ← p
×
1=
p
r
−
1
=
ab
mod
n
obtaining the desired result. However, we
can spare ourselves the reverse transformation effected in the last step by setting
p ← a
× b
at once and thus avoid the transformation of
b
, so that in the end we
have the following algorithm.
−
Calculation of
p
=
ab
mod
n
(
n
odd) with the Montgomery product
1.
Determine
r
:= 2
s
with
2
s
−
1
≤ n<
2
s
. Calculate
1=
r
r − n
n
by means
of the extended Euclidean algorithm.
2.
Set
a
← ar
mod
n
.
3.
Set
p ← a
× b
and output
p
.
