# Index-calculus algorithm

The index-calculus algorithm is the most powerful method known for computing discrete logarithms. The technique employed does not apply to all groups, but when it does, it often gives a subexponential-time algorithm. The algorithm is first described in the general setting of a cyclic group *G* (Algorithm 3.68). Two examples are then presented to illustrate how the index-calculus algorithm works in two kinds of groups that are used in practical applications, namely Z* (Example 3.69) and Fg,,, (Example 3.70).

The index-calculus algorithm requires the selection of a relatively small subset *S* of elements of *G,* called the *factor base,* in such a way that a significant fraction of elements of *G* can be efficiently expressed as products of elements from *S.* Algorithm 3.68 proceeds to precompute a database containing the logarithms of all the elements in *S,* and then reuses this database each time the logarithm of a particular group element is required.

The description of Algorithm 3.68 is incomplete for two reasons. Firstly, a technique for selecting the factor base 5 is not specified. Secondly, a method for efficiently generating relations of the form (3.5) and (3.7) is not specified. The factor base *S* must be a subset of *G* that is small (so that the system of equations to be solved in step 3 is not too large), but not too small (so that the expected number of trials to generate a relation (3.5) or (3.7) is not too large). Suitable factor bases and techniques for generating relations are known for some cyclic groups including Z* (see §3.6.5(i)) and FJjm (see §3.6.5(h)), and, moreover, the multiplicative group F* of a general finite field F_{g}.

3.68 Algorithm Index-calculus algorithm for discrete logarithms in cyclic groups

INPUT: a generator a of a cyclic group *G* of order *n,* and an element *,3 e G.*

OUTPUT: the discrete logarithm *у* = log_{Q} /3.

- 1.
*(Select a factor base S)*Choose a subset*S =*{pi, p_{2}, • • • •*pt}*of*G*such that a “significant proportion” of all elements in*G*can be efficiently expressed as a product of elements from*S.* - 2.
*(Collect linear relations involving logarithms of elements in S*)

- 2.1 Select a random integer
*к,*0 <*к < n -*1, and compute*a*^{k}. - 2.2 Try to write
*a*as a product of elements in^{k}*S*:

If successful, take logarithms of both sides of equation (3.5) to obtain a linear relation

- 2.3 Repeat steps 2.1 and 2.2 until
*t + c*relations of the form (3.6) are obtained (c is a small positive integer, e.g. c = 10, such that the system of equations given by the*t + c*relations has a unique solution with high probability). - 3.
*(Find the logarithms of elements in S*) Working modulo*n,*solve the linear system of*t*+ c equations (in*t*unknowns) of the form (3.6) collected in step 2 to obtain the values of log_{Q}p,, 1*< i* - 4. (
*Compute у*) - 4.1 Select a random integer
*к,*0 <*к < n -*1, and compute*(3 ■ a*^{k}. - 4.2 Try to write
*0 ■ a*as a product of elements in^{k}*S*:

*
*

If the attempt is unsuccessful then repeat step 4.1. Otherwise, taking logarithms of both sides of equation (3.7) yields log_{a} *0* = log_{Q} *p,* — *k)* mod n;

thus, compute *у =* (Xw=i *&* log_{Q} *p, - k)* mod n and retum(y).

(i) Index-calculus algorithm in Z*

For the field Z_{p}, *p* a prune, the factor base *S* can be chosen as the first *t* prime numbers. A relation (3.5) is generated by computing *a ^{k}* mod

*p*and then using trial division to check whether this integer is a product of primes in

*S.*Example 3.69 illustrates Algorithm 3.68 in Z* on a problem with artificially small parameters.

- 3.69 Example
*(Algorithm 3.68 for logarithms in*Z^q)*Let p*= 229. The element a = 6 is a generator of Z229 of order*n*= 228. Consider*3 =*13. Then log_{G}13 is computed as follows, using the index-calculus technique. - 1. The factor base is chosen to be the first 5 primes:
*S =*{2.3,5,7,11}. - 2. The following six relations involving elements of the factor base are obtained (unsuccessful attempts are not shown):

These relations yield the following six equations involving the logarithms of elements in the factor base:

- 3. Solving the linear system of six equations in five unknowns (the logarithms ж, = logo
*Pi)*yields the solutions log_{G}2 = 21, log_{G}3 = 208, log_{6}5 = 98, log_{6}7 = 107, and log_{G}11 = 162. - 4. Suppose that the integer
*к =*77 is selected. Since*3 ■ a*13 • 6^{k}=^{77}mod 229 = 147 = 3 • 7^{2}, it follows that

□

(ii) Index-calculus algorithm in F_{2}m

The elements of the finite field F_{2}™ are represented as polynomials in Z_{2} [ж] of degree at most *m* — 1, where multiplication is performed modulo a fixed irreducible polynomial /(ж) of degree *m* in Z_{2} [ж] (see §2.6). The factor base 5 can be chosen as the set of all irreducible polynomials in Z_{2} [ж] of degree at most some prescribed bound *b.* A relation (3.5) is generated by computing *a ^{k}* mod /(ж) and then using trial division to check whether this polynomial is a product of polynomials in 5. Example 3.70 illustrates Algorithm 3.68 in F

_{2},„ on a problem with artificially small parameters.

- 3.70 Example
*(Algorithm 3.68 for logarithms in*F_{2}?) The polynomial /(ж) = ж^{7}+ ж + 1 is irreducible over Z_{2}. Hence, the elements of the finite field F_{2}t of order 128 can be represented as the set of all polynomials in Z_{2}[ж] of degree at most 6, where multiplication is performed modulo /(ж). The order of F_{2}t is n = 2^{7}- 1 = 127, and a = ж is a generator of F_{2}7. Suppose*0*= ж^{4}+ ж^{3}+ ж^{2}+ ж + 1. Then*у =*log_{x}*0*can be computed as follows, using the index-calculus technique. - 1. The factor base is chosen to be the set of all irreducible polynomials in Z
_{2}[ж] of degree at most 3:*S*= {ж, ж + 1, ж^{2}+ ж + 1, ж^{3}+ ж + 1. ж^{3}+ ж^{2}+ 1}. - 2. The following five relations involving elements of the factor base are obtained (unsuccessful attempts are not shown):

These relations yield the following five equations involving the logarithms of elements in the factor base (for convenience of notation, let *pi =* log_{x} ж, *p**2* = log^-l

- 3. Solving the linear system of five equations in five unknowns yields the values pi = 1, P2
*=*7,рз*=*56,*pi =*31, andps = 90. - 4. Suppose
*к =*66 is selected. Since

it follows that

- 3.71 Note (
*running time of Algorithm 3.68*) To optimize the running time of the index-calculus algorithm, the size*t*of the factor base should be judiciously chosen. The optimal selection relies on knowledge concerning the distribution of smooth integers in the interval [1, p — 1] for the case of Z*, and for the case of F^m on the distribution of*smooth polynomials*(that is, polynomials all of whose irreducible factors have relatively small degrees) among polynomials in F_{2}[:r] of degree less than*m.*With an optimal choice of*t,*the index-calculus algorithm as described above for Z* and F^m has an expected miming time of*L*c] where_{q}[,*q = p*or*q*= 2^{m}, and c > 0 is a constant. - 3.72 Note
*(fastest algorithms known for discrete logarithms in*Z**and*F^m) Currently, the best algorithm known for computing logarithms in F^,,, is a variation of the index-calculus algorithm called*Coppersmith’s algorithm,*with an expected miming tune of L_{2}m [|, c] for some constant c < 1.587. The best algorithm known for computing logarithms in Z* is a variation of the index-calculus algorithm called the*number field sieve,*with an expected running time of*L*_{p}[|, 1.923]. The latest efforts in these directions are surveyed hi the Notes section (§3.12). - 3.73 Note
*(parallelization of the index-calculus algorithm)* - (i) For the optimal choice of parameters, the most time-consuming phase of the index- calculus algorithm is usually the generation of relations involving factor base logarithms (step 2 of Algorithm 3.68). The work for this stage can be easily distributed among a network of processors by simply having the processors search for relations independently of each other. The relations generated are collected by a central processor. When enough relations have been generated, the corresponding system of linear equations can be solved (step 3 of Algorithm 3.68) on a single (possibly parallel) computer.
- (ii) The database of factor base logarithms need only be computed once for a given finite field. Relative to this, the computation of individual logarithms (step 4 of Algorithm 3.68) is considerably faster.

# Discrete logarithm problem in subgroups of Z*p

The discrete logarithm problem in subgroups of Z* has special interest because its presumed intractability is the basis for the security of the U.S. Government NIST Digital Signature Algorithm (§11.5.1), among other cryptographic techniques.

Let *p* be a prime and *q* a prime divisor of *p -* 1. Let *G* be the unique cyclic subgroup of Z* of order *q,* and let q be a generator of *G.* Then the discrete logarithm problem in *G* is the following: given*p, q,* a, and */3 € G,* find the unique integer *x,* 0 < *x < q* -1, such that *a ^{x} = (3* (mod

*p).*The powerful index-calculus algorithms do not appear to apply directly in

*G.*That is, one needs to apply the index-calculus algorithm in the group Z* itself in order to compute logarithms in the smaller group

*G.*Consequently, there are two approaches one could take to computing logarithms in

*G:*

- 1. Use a “square-root” algorithm directly in
*G,*such as Pollard’s rho algorithm (Algorithm 3.60). The miming time of this approach is*O(ffq).* - 2. Let 7 be a generator of Z
_{p}, and let*l = (p -*1*)/q.*Use an index-calculus algorithm in Z* to find integers*у*and г such that a =*-y*and^{y}*3*= 7*. Then*x =*log_{Q}*0 = {z/l)(y/l)~*mod^{l}*q.*(Since*у*and 2 are both divisible by /,*y/l*and*z/l*are indeed integers.) The running time of this approach is L_{p}[|, c] if the number field sieve is used.

Which of the two approaches is faster depends on the relative size of *ffq* and L_{p}[|, с].