{Now ge = d∈{1,3,...,2k ’1} Bd .}

d

[1] Reitwiesner, G.W. (1960). “Binary arithmetic.” Ad-

vances in Computers, 1, 231“308.

for d = 2k ’ 1 to 3 step ’ 2 do [2] Solinas, J.A. (2000). “Ef¬cient arithmetic on Koblitz

curves.” Designs, Codes and Cryptography, 19, 195“

Bd’2 ← Bd’2 —¦ Bd

249.

B1 ← B1 —¦ (Bd —¦ Bd )

return B1

SIMULTANEOUS

For both the left-to-right and the right-to-left

EXPONENTIATION

variant, it remains to be considered how signed

digit representations of exponents e using the digit

set {0} ∪ Bk with Bk = {±1, ±3, . . . , ±(2k ’ 1)} can Various schemes for public-key cryptography in-

be obtained. An algorithm for the simplest case volve computing power products in some com-

k = 1 is due to Reitwiesner [1]; the representation mutative group (or commutative semigroup). A

obtained by it (using digits {’1, 0, 1}) is known straightforward way to compute a power product

as the nonadjacent form (NAF) of e. The general- n

e

ization for an arbitrary parameter k was simul- gjj

taneously suggested by multiple researchers; the j=1

following algorithm is from [2]: e

is to compute the individual powers g j j using

c←e binary exponentiation or some other exponenti-

ation method, and perform n ’ 1 applications of

i←0

the group operation to multiply these partial re-

while c > 0 do sults. However, specialized algorithms for comput-

if c is odd then ing power products are often faster. The task of

d ← c mod 2k+1 computing a power product is sometimes called

multi-exponentiation, and performing a multiex-

if d > 2k then

ponentiation by a procedure that does not in-

d ← d ’ 2k+1 e

volve computing the partial results g j j is known

c ←c’d as simultaneous exponentiation. Two methds for

else multiexponentiation that both generalize left-to-

right sliding window exponentiation are simulta-

d←0

neous sliding window exponentiation, which is

ei ← d; i ← i + 1

due to Yen, Laih. and Lenstra [3] (based on

c ← c/2 the simultaneous 2k -ary exponentiation method

return ei’1 , . . . , e0 from Straus [2]), and interleaved sliding window

Simultaneous exponentiation 585

available without any computation; once g j —¦ g j for

exponentiation [1]. Like the sliding window

j = 1, . . . , n have been computed as temporary val-

method for single exponentiations, these meth-

ues, each of the 2nk ’ 2n(k’1) ’ n remaining table

ods use the binary representation of exponents,

on which nonoverlapping windows are placed such values can be obtained by using the group oper-

that every nonzero bit is covered by one of the win- ation once). The multi-exponentiation result then

dows. Simultaneous sliding window exponentia- is computed using the table of small powers:

tion and interleaved sliding window exponentia-

A ← G(e1,l’1 ,...,en,l’1 )

tion use different approaches for placing windows;

for i = l ’ 2 down to 0 do

sometimes the former is faster, sometimes the

A ← A—¦ A

latter.

Simultaneous sliding window exponentiation if (e1,l , . . . , en,l ) = (0, . . . , 0) then

uses windows up to some maximum width k that

A ← A —¦ G(e1,i ,...,en,i )

span across all n exponents; e.g., for exponents

return A

e1 , e2 , e3 with binary representations 1011010,

0011001, and 1001011 and k = 2: For random b-bit exponents, this requires at most

another b ’ 1 squaring operations and on average

e1 101 101 0 approximately another

e2 001 100 1

1

e3 100 101 1

b·

k+ 1

2n ’1

Such windows can be found by left-to-right scan-

general group operations. Note that in practice it

ning: look at the binary representations of the ex-

is not necessary to completely derive the represen-

ponents simultaneously, going from left to right,

tation

starting a new window whenever a nonzero bit is

encountered, choosing the maximum width up to (e1,l’1 , . . . , en,l’1 ), . . . , (e1,0 , . . . , en,0 )

k for this particular window such that one of the

before starting the exponentiation; instead, left-

rightmost bits is also nonzero. The result of col-

to-right scanning can be used to determine it win-

lapsing the window values into the right-most row

dow by window when it is needed.

of each window can be considered a base-two rep-

In interleaved sliding window exponentiation,

resentation

each single exponent has independent windows

l’1

up to some maximum width k; e.g., for exponents

(e1 , . . . , en ) = (e1,i , . . . , en,i )2i

e1 , e2 , e3 with binary representations 1011010,

i=0

0011001, and 1001011 and k = 3:

of the vector of exponents, e.g.

e1 101101 0

e1 1003002

e2 0003001 e2 001100 1

e3 1001003

e3 100101 1

for the above example. Assume we have such a

representation with l chosen minimal, i.e. (e1,l , . . . , For each exponent, such windows can be found by

en,l ) = (0, . . . , 0). To perform a simultaneous slid- left-to-right scanning: look at the binary represen-

ing window exponentiation, ¬rst products tation of the respective exponent, going from left to

right, starting a new window whenever a nonzero

n

d

G(d1 ,...,dn ) = gj j bit is encountered, choosing the maximum width

up to k for this particular window such that the

j=1

rightmost bit is also nonzero. To perform an in-

of small powers are computed and stored for

terleaved sliding window exponentiation, ¬rst for

all possible window values, namely for the tu-

each g j, the powers for odd exponents 1 up to 2k ’ 1

ples (d1 , . . . , dn ) with d j ∈ {0, 1, . . . , 2k ’ 1} for j =

are computed and stored:

1, . . . , n such that at least one of the d j is odd.

There are 2nk ’ 2n(k’1) such tuples, and comput- for j = 1 to n do

ing the table of those products can be done with G j,1 ← g

2nk ’ 2n(k’1) A← g—¦g

for d = 3 to 2k ’ 1 step 2 do

applications of the group operation, n of which are

squarings (g1 , . . . , gn appear in the table and are G j,d ← G j,d’2 —¦ A

586 Skipjack

Rule A Rule B

w 1+1 = G k(w 1) • w 4 • counter k w 1+1 = w 4

k k k k k

w 2+1 = G k(w 1) w 2+1 = G k(w 1)

k k k k

w 3+1 = w 1 • w 2 • counter k

w 3+1 = w 2 k k k

k k