 Fixed-exponent exponentiation algorithms

There are numerous situations in which a number of exponentiations by a fixed exponent must be performed. Examples include RSA encryption and decryption, and ElGamal decryption. This subsection describes selected algorithms which improve the repeated square- and-multiply algorithms of §14.6.1 by reducing the number of multiplications.

The purpose of an addition chain is to minimize the number of multiplications required for an exponentiation.

• 14.97 Definition An addition chain V of length s for a positive integer e is a sequence щ, «г. ... , us of positive integers, and an associated sequence wi,... ,ws of pairs wt = {ii.iz), 0
• (i) uo = l and us = e; and
• (ii) for each щ, 1 < i < s, щ = Uix + щ2.
• 14.98 Algorithm Addition chain exponentiation
• INPUT: a group element g, an addition chain V = (w0, u,... ,us) of length s for a positive integer e, and the associated sequence wi,... , ws, where w, = (4,12).

OUTPUT: ge.

• 1. g0^g.
• 2. For i from 1 to s do: gi^gil ■ gt2.
• 3. Retum(cjs).
• 14.99 Example (addition chain exponentiation) An addition chain of length 5 for e = 15 is и о = 1, «1 = 2, «2 = 3, «з = 6, «4 = 12, «5 = 15. The following table displays the values of w, and g, during each iteration of Algorithm 14.98 for computing g15.
 i 0 1 2 3 4 5 Wi - (0,0) (0Д) (2,2) (3,3) (2,4) 9i 9 92 g6 912 915
• 14.100 Remark (addition chains and binary representations) Given the binary representation of an exponent e, it is a relatively simple task to construct an addition chain directly from this representation. Chains constructed in this way generally do not provide the shortest addition chain possible for the given exponent. The methods for exponentiation described in §14.6.1 could be phrased in terms of addition chains, but this is typically not done.
• 14.101 Note (computational efficiency of addition chain exponentiation) Given an addition chain of length s for the positive integer e, Algorithm 14.98 computes ge for any gG, g Ф 1, using exactly s multiplications.
• 14.102 Fact If / is the length of a shortest addition chain for a positive integer e, then l > (lg e + lg wt(e) - 2.13), where wt(e) is the number of l’s in the binary representation of e. An upper bound of ([lg c + wt(e) - 1) is obtained by constructing an addition chain for e from its binary representation. Determining a shortest addition chain for e is known to be an NP-hard problem.

Algorithms 14.88 and 14.104 are useful for computing gly'g'y' ■ ■ ■ gkkGy where go,g,..., gk—i are arbitrary elements in a group G and eo, ey,... , ek~y are fixed positive integers. These algorithms can also be used to advantage when the exponents are not necessarily fixed values (see Note 14.91). Algorithm 14.104 makes use of vector-addition chains.

• 14.103 Definition Let .s and A be positive integers and let vy denote a A:-dimensional vector of non-negative integers. An ordered set V = {vy :к + 1 < i < s} is called a vector- addition chain of length s and dimension к if V satisfies the following:
• (i) Each Vi, -к + 1 < i < 0, has a 0 in each coordinate position, except for coordinate position i + k — 1, which is a 1. (Coordinate positions are labeled 0 through к — 1.)
• (ii) For each vy, 1 < i < s, there exists an associated pair of integers wy = (ii, *2) such that —A + 1 < iy, ?2 < i and vy = vyl + vi2 (iy = *2 is allowed).

Example 14.105 illustrates a sample vector-addition chain. Let V = {vy : — A + 1 < i < ,s} be a vector-addition chain of length s and dimension A with associated sequence wi,... ,ws. Algorithm 14.104computesg^'g'y • ■ • g'^Gy wherevs = (eo,ei,... ,e^_i).

INPUT: group elements go,gi,... , gk-i and a vector-addition chain V of length s and dimension A with associated sequence wy,... ,ws, where wy = (iy, *2).

OUTPUT: g^gl • • ge^y where = (e0, eb... , ek_y).

• 1. For i from (—A + 1) to 0 do: a,<—gi+k-i-
• 2. For i from 1 to s do: ■ ai2.
• 3. Retum(as).
• 14.105 Example (vector-addition chain exponentiation) A vector-addition chain V of length s = 9 and dimension A = 3 is displayed in the folio whig table.
 V-2 V-i uo Vy V2 v3 Vi vs V6 V7 vs V9 1 0 0 1 2 2 3 5 G 12 15 30 0 1 0 0 0 1 1 2 2 4 5 10 0 0 1 1 2 2 2 4 5 10 12 24

The following table displays the values of wy and a, during each iteration of step 2 in Algorithm 14.104 for computing Vo°5i°V24 • Nine multiplications are required. □

 г 1 2 3 4 5 G 7 8 9 U)i (-2,0) (1,1) (-1,2) (-2,3) (3,4) (1,5) (6,6) (4,7) (8,8) at         • 14.106 Note (computational efficiency of vector-addition chain exponentiation)
• (i) (multiplications) Algorithm 14.104 performs exactly s multiplications for a vector- addition chain of lengths. To compute • • • Vfc-Y using Algorithm 14.104, one

would like to find a vector-addition chain of length s and dimension A with vs =

(eo, ei,... , efc_i), where s is as small as possible (see Fact 14.107).

• (ii) (storage) Algorithm 14.104 requires intermediate storage for the elements at, -k + 1 < i < t, at the fth iteration of step 2. If not all of these are required for succeeding iterations, then they need not be stored. Algorithm 14.88 provides a special case of Algorithm 14.104 where the intermediate storage is no larger than 2fc - 1 vectors of dimension k.
• 14.107 Fact Tire minimum value of .s in Note 14.106(i) satisfies the following bound, where M = max{e, : 0 1} and c is a constant: 