Cryptography Reference
In-Depth Information
Exercise 2.8.7
Show that the expected number of squarings between each multiply in
the sliding window algorithm is
w
1. Hence, show that (ignoring the precomputa-
tion) exponentiation using sliding windows requires log(
m
) squarings and, on average,
log(
m
)
/
(
w
+
+
1) multiplications.
Exercise 2.8.8
Consider running the sliding window method in a group, with varying
g
and
m
(so the powers of
g
must be computed for every exponentiation) but with unlimited
storage. For a given bound on len(
m
) one can compute the value for
w
that minimises the
total cost. Verify that the choices in the following table are optimal.
len(
m
)
80
160
300
800
2000
34 5 6 7
.
w
Exercise 2.8.9
Algorithm
2
processes the bits of the exponent
m
from left to right. Give
pseudocode for a modular exponentiation algorithm that processes the bits of the exponent
m
from right to left.
[Hint: Have two variables in the main loop; one that stores
g
2
i
in the
i
th iteration, and
the other that stores the value
g
i
j
=
0
a
j
2
j
.]
Exercise 2.8.10
Write pseudocode for a right to left sliding window algorithm for com-
puting
g
m
(mod
n
), extending Exercise
2.8.9
. Explain why this variant is not so effective
when computing
g
m
(mod
n
) for many random
m
but when
g
is fixed.
One can also consider the opposite scenario where one is computing
g
m
(mod
n
)fora
fixed value
m
and varying
g
. Again, with some precomputation, and if there is sufficient
storage available, one can get an improvement over the naive algorithm. The idea is to
determine an efficient
addition chain
for
m
. This is a sequence of squarings and multipli-
cations, depending on
m
, that minimises the number of group operations. More precisely,
an addition chain of length
l
for
m
is a sequence
m
1
,m
2
,...,m
l
of integers such that
m
1
=
1,
m
l
=
m
and for each 2
≤
i
≤
l
we have
m
i
=
m
j
+
m
k
for some 1
≤
j
≤
k<i
.
One computes each of the intermediate values
g
m
i
for 2
l
with one group operation.
Note that
all
these intermediate values are stored. The algorithm requires
l
group operations
and
l
group elements of storage.
It is conjectured by Stolarsky that every integer
m
has an addition chain of length
log
2
(
m
)
≤
i
≤
log
2
(wt(
m
)) where wt(
m
)isthe
Hamming weight
of
m
(i.e., the number of
ones in the binary expansion of
m
). There is a vast literature on addition chains, we refer
to Section C6 of [
246
], Section 4.6.3 of [
308
] and Section 9.2 of [
16
] for discussion and
references.
+
Exercise 2.8.11
Prove that an addition chain has length at least log
2
(
m
).
