Cryptography Reference
In-Depth Information
Proof
Convert
g
to Montgomery representation
g
in
O
(log(
n
)
2
) bit operations. Algo-
rithm
2
then proceeds using Montgomery multiplication in lines 5 and 7, which requires
O
(log(
m
)
M
(log(
n
))) bit operations. Finally, Montgomery reduction is used to convert the
output to standard form.
The algorithm using Montgomery multiplication is usually better than the naive version,
especially when fast multiplication is available. An application of the above algorithm,
where Karatsuba multiplication would be appropriate, is RSA decryption (either the stan-
dard method, or using the CRT). Since log(
m
)
=
(log(
n
)) in this case, decryption requires
O
(log(
n
)
2
.
585
) bit operations.
Corollary 2.8.4
One can compute the Legendre symbol
(
p
)
using Euler's criterion in
O
(log(
p
)
M
(log(
p
)))
bit operations.
When storage for precomputed group elements is available there are many ways to speed
up exponentiation. These methods are particularly appropriate when many exponentiations
of a fixed element
g
are required. The methods fall naturally into two types: those that reduce
the number of squarings in Algorithm
2
and those that reduce the number of multiplications.
An extreme example of the first type is to precompute and store
u
i
=
g
2
i
(mod
n
)for2
≤
log(
n
). Given 2
l
m<
2
l
+
1
i
≤
≤
with binary expansion (1
m
l
−
1
...m
1
m
0
)
2
one computes
l
i
=
0:
m
i
=
1
u
i
(mod
n
). Obviously, this method is not more efficient than Algorithm
2
if
g
varies. An example of the second type is
sliding window methods
that we now briefly
describe. Note that there is a simpler but less efficient “non-sliding” window method, also
called the 2
k
-ary method, which can be found in many topics. Sliding window methods can
be useful even in the case where
g
varies (e.g., Algorithm
3
below).
Given a
window length
w
one precomputes
u
i
=
g
i
(mod
n
) for all odd integers 1
≤
i<
2
w
. Then one runs a variant of Algorithm
2
where
w
(or more) squarings are performed
followed by one multiplication corresponding to a
w
-bit substring of the binary expansion
of
m
that corresponds to an odd integer. One subtlety is that algorithms based on the “square-
and-multiply” idea and which use precomputation must parse the exponent starting with
the most significant bits (i.e., from left to right), whereas to work out sliding windows one
needs to parse the exponent from the least significant bits (i.e., right to left).
g
3
. Suppose
m
has
binary expansion (10011011)
2
. By parsing the binary expansion starting with the least
significant bits, one obtains the representation 10003003 (we stress that this is still a
representation in base 2). One then performs the usual square-and-multiply algorithm by
parsing the exponent from left to right; the steps of the sliding window algorithm are
(omitting the (mod
n
) notation)
Example 2.8.5
Let
w
=
2 so that one precomputes
u
1
=
g
and
u
3
=
b
2
;
b
b
2
,b
b
2
,b
b
2
,b
b
2
,b
b
2
,b
b
2
,b
=
=
=
=
=
=
=
=
=
=
b
u
1
,b
bu
3
,b
bu
3
.
Exercise 2.8.6
Write pseudocode for the sliding window method. Show that the precom-
putation stage requires one squaring and 2
w
−
1
−
1 multiplications.
