Cryptography Reference
In-Depth Information
Algorithm 7
Basic multi-exponentiation
INPUT:
g
1
,...,g
n
∈
G,a
1
,...,a
n
∈ N
OUTPUT:
i
=
1
g
a
i
1:
Precompute all
u
b
1
,...,b
n
=
i
=
1
g
b
i
i
for
b
i
∈{
0
,
1
}
i
2:
Set
l
=
max
1
≤
i
≤
n
{
log
2
(
a
i
)
}
3:
h
=
u
a
1
,l
,...,a
n,l
4:
j
=
l
−
1
5:
while
j
≥
0
do
h
2
h
=
6:
h
=
hu
a
1
,j
,...,a
n,j
7:
=
−
j
j
1
8:
9:
end while
10:
return
h
Example 11.2.1
One can compute
g
1
g
2
by setting
h
=
u
1
,
1
=
g
1
g
2
and then computing
g
1
g
2
.
Exercise 11.2.2
Show that one can perform the precomputation in Algorithm
7
in 2
n
h
2
g
1
g
2
,
h
g
1
g
2
,
h
h
2
g
1
g
2
,
h
h
=
=
=
hu
1
,
0
=
=
=
=
hu
1
,
1
=
−
n
1 multiplications. Show that the main loop of Algorithm
7
performs
l
squarings and
l
multiplications.
−
Exercise 11.2.3
(Yen, Laih and Lenstra [
571
]) Show that, by performing further precom-
putation, one can obtain a sliding window multi-exponentiation algorithm that still requires
l
squarings in the main loop, but fewer multiplications. Determine the precomputation cost.
An alternative approach
3
to multi-exponentiation is called
interleaving
. The basic idea
is to replace line 7 in Algorithm
7
by
hg
a
i,
i
end for
=
=
for
i
1
to
n
do
h
and to omit the precomputation. This version is usually less efficient than Algorithm
7
unless
n
is rather large. However, the benefit of interleaving comes when using sliding windows:
since the precomputation cost and storage requirements for the method in Exercise
11.2.3
are so high, it is often much more practical to use a sliding window version in the setting
of interleaving. We refer to [
387
] and Section 3.3.3 of [
248
] for further discussion of this
method.
Exercise 11.2.4
Write pseudocode for multi-exponentiation using interleaving and sliding
windows.
Another approach, when signed expansions are being used, is to find a representation
for the exponents
a
1
,...,a
n
so that the
j
th component of the representations of all
a
i
is
3
Independently discovered by M oller [
387
] and Gallant, Lambert and Vanstone [
216
].