Cryptography Reference
In-Depth Information
If not all
1
-windows are odd, then steps 3 through 6 are replaced by the
following, and there is no step 7:
mod
m
=
2
p
2
2
2
3
.
If
ω
k
−
1
=0
, set
p ← p
2
l
k
−
1
···
···
(
l
k
−
1
times)
=0
, factor
ω
k
−
1
=2
t
u
with odd
u
; set
p
a
u
mod
m
,
mod
m
.If
ω
k
−
1
←
and then
p ← p
2
t
mod
m
. In each case set
i ← k −
2
.
mod
m
=
2
p
2
2
2
4
.
If
ω
i
=0
, set
p ← p
2
l
i
···
···
(
l
i
times) mod
m
.
=0
,factor
ω
i
=2
t
u
with odd
u
; set
p ← p
2
l
i
−
t
mod
m
, and then
If
ω
i
p
2
t
mod
m
.
pa
u
mod
m
; now set
p
p
←
←
5
.
Set
i
0
, go to step
4
.
←
i
−
1
;if
i
≥
6
.
Output
p
.
6.4 Montgomery Reduction and Exponentiation
Now we are going to abandon addition chains and turn our attention to another
idea, one that is interesting above all from the algebraic point of view. It makes it
possible to replace multiplications modulo an odd number
n
by multiplications
modulo a power of
2
,thatis,
2
k
, which requires no explicit division and is
therefore more efficient than a reduction modulo an arbitrary number
n
. This
useful method for modular reduction was published in 1985 by P. Montgomery
[Mont] and since then has found wide practical application. It is based on the
following observation.
Let
n
and
r
be relatively prime integers, and let
r
−
1
be the multiplicative
inverse of
r
modulo
n
; and likewise let
n
−
1
be the multiplicative inverse of
n
modulo
r
; and furthermore, define
n
:=
−n
−
1
mod
r
and
m
:=
tn
mod
r
.For
integers
t
we then have
t
+
mn
r
tr
−
1
mod
n.
≡
(6.8)
Note that on the left side of the congruence we have taken congruences
modulo
r
andadivisionby
r
(note that
t
+
mn
0mod
r
, so the division has
no remainder), but we have not taken congruences modulo
n
. By choosing
r
as a
power of
2
in the form
2
s
we can reduce a number
x
modulo
r
simply by slicing
off
x
at the
s
th bit (counting from the least-significant bit), and we can carry out
the division of
x
by
r
by shifting
x
to the right by
s
bit positions. The left side of
(6.8) thus requires significantly less computational expense than the right side,
which is what gives the equation its charm. For the two required operations we
can invoke the functions
mod2_l()
(cf. Section 4.3) and
shift_l()
(cf. Section 7.1).
≡
