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.
(i) Addition chains
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 щ, «г. ... , u_{s} of positive integers, and an associated sequence wi,... ,w_{s} of pairs w_{t} = {ii.iz), 0
- (i) uo = l and u_{s} = e; and
- (ii) for each щ, 1 < i < s, щ = Ui_{x} + щ_{2}.
INPUT: a group element g, an addition chain V = (w_{0}, u,... ,u_{s}) of length s for a positive integer e, and the associated sequence wi,... , w_{s}, where w, = (4,12).
OUTPUT: g^{e}.
- 1. g_{0}^g.
- 2. For i from 1 to s do: gi^gi_{l} ■ gt_{2}.
- 3. Retum(cj_{s}).
- 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 g^{15}. □
i |
0 |
1 |
2 |
3 |
4 |
5 |
Wi |
- |
(0,0) |
(0Д) |
(2,2) |
(3,3) |
(2,4) |
9i |
9 |
9^{2} |
g^{6} |
9^{12} |
9^{15} |
- 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 g^{e} for any g € G, 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.
(ii) Vector-addition chains
Algorithms 14.88 and 14.104 are useful for computing gly'g'y' ■ ■ ■ g_{k}^{k}Gy where go,g,..., gk—i are arbitrary elements in a group G and eo, ey,... , e_{k}~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 = vy_{l} + v_{i2} (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,... ,w_{s}. Algorithm 14.104computesg^'g'y • ■ • g'^Gy wherev_{s} = (eo,ei,... ,e^_i).
14.104 Algorithm Vector-addition chain exponentiation
INPUT: group elements go,gi,... , gk-i and a vector-addition chain V of length s and dimension A with associated sequence wy,... ,w_{s}, where wy = (iy, *2).
OUTPUT: g^g^{l} ■ • • g^{e}^y where = (e_{0}, e_{b}... , e_{k}_y).
- 1. For i from (—A + 1) to 0 do: a,<—gi_{+k}-i-
- 2. For i from 1 to s do: ■ a_{i2}.
- 3. Retum(a_{s}).
- 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 |
v_{3} |
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°V2^{4} • 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 v_{s} =
(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 a_{t}, -k + 1 < i < t, at the f^{th} 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 2^{fc} - 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:
14.108 Example (vector-addition chains from binary representations) The vector-addition chain
implicit in Algorithm 14.88 is not necessarily of minimum length. The vector-addition chain associated with Example 14.89 is displayed in Table 14.18. This chain is longer than the one used in Example 14.105. The advantage of Algorithm 14.88 is that the vector- addition chain does not have to be explicitly provided to the algorithm. In view of this, Algorithm 14.88 can be applied more generally to situations where the exponents are not necessarily fixed. □
V-2 |
V-l |
vo |
Vl |
V2 |
V3 |
V_{4} |
Vs |
V6 |
V7 |
Vs |
V9 |
t’10 |
1 |
0 |
0 |
1 |
1 |
1 |
2 |
3 |
6 |
7 |
14 |
15 |
30 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
2 |
2 |
4 |
5 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
2 |
3 |
6 |
6 |
12 |
12 |
24 |
Table 14.18: Binary vector-addition chain exponentiation (see Example 14.108).