Multi-exponentiation for a New Base g1 . Let us now consider the com-

d e

putation of g1 · g2 for d = 205802 = (110010001111101010)2 and e = 245153 =

(111011110110100001)2 where g1 is a new base, i.e. no cached precomputed data based

on g1 is available. Before the actual multi-exponentiation, we compute the powers

(g1 , g1 , . . . , g1 ) and save these in fast read/write memory. Encoding e1 := d using B1

3 15

yields

e1 = (3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 15, 0, 0, 5, 0, 1, 0)2 .

Encoding e using B2 and then splitting into three parts e2 , e3 , e4 yields

e4 = (7, 0, 0, 0)2 ,

e3 = (7, 0, 0, 5, 0, 0)2 ,

e2 = (5, 0, 0, 0, 0, 1)2 .

É

The following table shows what happens while performing the multi-exponentiation

ei

i=1 gi

4

as described in Section 3.1, based on interleaved multi-exponentiation as

explained in Section 2.1:

Faster Multi-exponentiation through Caching 53

j A Cache entry (so far)

17 1 (g1 )

g13

16

¡

33

(g1 )2 g1 = g125

13

¡

(g1 )2 = g1 g1 , (50, g1 )

25 50 50

12

50 6 15

(g1 )2 g1 = g1 g1 , (3215, g1 ), (50, g1 )

3215 3215 50

6

(g1 ) g2 g3 = g1 g2 g3

3215 2 5 7 6430 5 7

5

6430 5 7 2 5 7

(g1 g2 g3 )2 g1 g4 = g1 g2 g3 g4

25725 20 28 7

3

g2 g3 g4 ) g3 = g1 g2 g3 g4

25725 20 28 7 2 5 51450 40 61 14

2 (g1

g2 g3 g4 ) g1 = g1 g2 g3 g4

51450 40 61 14 2 102901 80 122 28

1 (g1

g2 g3 g4 ) g2 = g1 g2 g3 g4

102901 80 122 28 2 205802 161 244 56

0 (g1

As we can see here, until and including round j = 6, the variable A contains no powers

of bases other than g1 . Intermediate powers of g1 for caching are available at the points

j = 12 and j = 6 of the computation.

d e

Multi-exponentiation for an Old Base g1 . Let us compute g1 · g2 for d =

73660 = (10001111110111100)2 , e = 236424 = (111001101110001000)2 where g1 is

an old base for which the cache entry (g1 , (»1 = 3215, G1 = g1 ), (»2 = 50, G2 =

3215

g1 )) as created above is available. First, the powers (g1 , g1 , G1 , G3 , G5 , G2 , G3 , G5 )

50 3

1 1 2 2

are precomputed and stored in fast read/write memory. Next, we perform modular

exponent splitting as described in Section 3.2:

¤¥

d0 = d = 73660,

¤¥

d

E1 = »0 = 22 and d1 = d0 ’ E1 »1 = 2930,

1

d

E2 = »1 = 58 and d2 = d1 ’ E2 »2 = 30,

2

E3 = d2 = 30

Encoding E1 , E2 and E3 using BG1 , BG2 and B1 yields

E1 = (10110)2 = (5, 1, 0)2 ,

E2 = (111010)2 = (3, 0, 0, 5, 0)2 ,

E3 = (11110)2 = (3, 0, 3, 0)2 .

By encoding e using B2 and then splitting into 3 parts e2 , e3 , e4 (using radix-2 exponent

splitting), we obtain

e4 = (7, 0, 0, 0)2 ,

e3 = (3, 0, 0, 0, 7, 0)2 ,

e2 = (1, 0, 0, 0)2 .

The table below shows what happens in the interleaved multi-exponentiation to com-

pute GE1 GE2 g1 3 g22 g33 g44 :

E e e e

1 2

j A

g3

3

5

(g3 )2 G3 = G3 g3

3 6

4 2 2

(G3 g3 )2 g1 g2 g4 = G6 g1 g2 g3 g4

6 3 7 3 12 7

3 2 2

(G6 g1 g2 g3 g4 )2 G5 = G5 G12 g1 g2 g3 g4

3 12 7 6 2 24 14

2 2 1 12

(G5 G12 g1 g2 g3 g4 )2 G1 G5 g1 g3 = G11 G29 g1 g2 g3 g4

6 2 24 14 37 15 4 55 28

1 12 2 1 2

(G1 G2 g1 g2 g3 g4 ) = G1 G2 g1 g2 g3 g4

11 29 15 4 55 28 2 22 58 30 8 110 56

0

54 B. M¨ller and A. Rupp

o

B Implementation Aspects

On-The-Fly Signed-Digit Conversions. In our descriptions of multi-

exponentiation algorithms, we have employed radix-2 representations of exponents by

referring to their individual digits. However, this by no means is meant to imply that

these digits need to be explicitly obtained and stored in advance, which would be quite

inconvenient if memory is scarce. Left-to-right signed fractional window representa-

tions [11,23,16] are very convenient for our purposes since (for any given maximum

digit value m) there is a ¬nite-state machine that transforms the binary representation

into the corresponding signed-digit representation. As the name suggests, this conver-

sion machine starts at the most signi¬cant digit (“left”) and continues towards the

least signi¬cant digit (“right”). Since interleaved multi-exponentiation is a left-to-right

technique as well, this often means that the signed digits can be obtained on the ¬‚y.

To make this work with radix-2 exponent splitting, we need to add an additional

¬rst left-to-right pass through the binary representation. This is essentially a dry run of

the signed fractional window conversion, used to determine the ¬rst binary digits that

will a¬ect each of the segments of the signed-digit representation. For s-fold radix-2

exponent splitting, such a dry run can be used to initialize each of s ¬nite-state ma-

chines, which afterwards can be used to obtain the digits of the individual segments

(exactly as in the case of the on-the-¬‚y conversion using just a single such machine

that we would use in the case without splitting).

A simpler alternative would be to ¬rst split the binary representation, and then

generate the signed-digit representations individually. This could be done truly on

the ¬‚y, i.e., without the additional left-to-right pass. However, this strategy often will

increase the total weight of the resulting representations [15], so the two-pass technique