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.
 
Search WWH ::




Custom Search