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




Custom Search