Index calculus algorithm

In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in (\mathbb{Z}/q\mathbb{Z})^* where q is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.

In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in (\mathbb{Z}/q\mathbb{Z})^* where q is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes. The third stage searches for a power s of the generator g which, when multiplied by the argument h, may be factored in terms of the factor base g s h = (−1) f 0 2 f 1 3 f 2 ···p r f r . Finally, in an operation too simple to really be called a fourth stage, the results of the second and third stages can be rearranged by simple algebraic manipulation to work out the desired discrete logarithm x = f 0 log g (−1) + f 1 log g 2 + f 2 log g 3 + ··· + f r log g p r − s. The first and third stages are both embarrassingly parallel, and in fact the third stage does not depend on the results of the first two stages, so it may be done in parallel with them. The choice of the factor base size r is critical, and the details are too intricate to explain here. The larger the factor base, the easier it is to find relations in stage 1, and the easier it is to complete stage 3, but the more relations you need before you can proceed to stage 2, and the more difficult stage 2 is. The relative availability of computers suitable for the different types of computation required for stages 1 and 2 is also important. Output: x such that g^x=h \mod q . relations ← empty_list for k = 1, 2, \ldots Using an integer factorization algorithm optimized for smooth numbers, try to factor g^k \bmod q (Euclidean residue) using the factor base, i.e. find e_i 's such that g^k \bmod q= (-1)^{e_0}2^{e_1}3^{e_2}\cdots p_r^{e_r} Each time a factorization is found: Store k and the computed e_i 's as a vector (e_0,e_1,e_2,\ldots,e_r,k) (this is a called a relation) If this relation is linearly independent to the other relations: Add it to the list of relations If there are at least r+1 relations, exit loop Form a matrix whose rows are the relations Obtain the reduced echelon form of the matrix The first element in the last column is the discrete log of -1 and the second element is the discrete log of 2 and so on for s = 1, 2, \ldots Try to factor g^s h \bmod q= (-1)^{f_0}2^{f_1}3^{f_2}\cdots p_r^{f_r} over the factor base When a factorization is found: Output x = f_0 \log_g(-1) + f_1 \log_g2 + \cdots + f_r \log_g p_r - s. ==History== The basic idea of the algorithm is due to Western and Miller (1968), which ultimately relies on ideas from Kraitchik (1922). The first practical implementations followed the 1976 introduction of the Diffie-Hellman cryptosystem which relies on the discrete logarithm. Merkle's Stanford University dissertation (1979) was credited by Pohlig (1977) and Hellman and Reyneri (1983), who also made improvements to the implementation. Adleman optimized the algorithm and presented it in the present form. ==The Index Calculus family== Index Calculus inspired a large family of algorithms. In finite fields \mathbb{F}_{q} with q=p^n for some prime p , the state-of-art algorithms are the Number Field Sieve for Discrete Logarithms, L_{q}\left[1/3,\sqrt[3]{64/9}\,\right] , when p is large compared to q , the function field sieve, L_q\left[1/3,\sqrt[3]{32/9}\,\right] , and Joux, L_{q}\left[1/4+\varepsilon,c\right] for c>0 , when p is small compared to q and the Number Field Sieve in High Degree, L_q[1/3,c] for c>0 when p is middle-sided. Discrete logarithm in some families of elliptic curves can be solved in time L_q\left[1/3,c\right] for c>0 , but the general case remains exponential. ==Notes==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1314227833 under CC BY-SA 4.0; modifications have been made.