The Discrete Logarithm Problem

Abstract

For large prime numbers p, computing discrete logarithms of elements of the multiplicative group (Z∕p Z)^∗ is at present a very difficult problem. The security of certain cryptosystems is based on the difficulty of this computation. In this expository paper we discuss several generalizations of the discrete logarithm problem and we describe various algorithms to compute discrete logarithms.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

For a prime number p, the multiplicative group (Z∕p Z)^∗ is cyclic of order p − 1. Generators of (Z∕p Z)^∗ are called primitive roots mod p. Let p be a prime and let g denote a primitive root modulo p. Then for every x ∈ (Z∕p Z)^∗ we have

$$\displaystyle{x\, =\, g^{a},}$$

for some integer a. This integer is called the discrete logarithm of x and is denoted by $\log x$. Since it depends on the primitive root g, one often writes $\log _{g}x$ rather than $\log x$. Since the discrete logarithm is only unique modulo p − 1, we view it as an element of the additive group $\mathbf{Z}/(p - 1)\mathbf{Z}$. Just as for the usual logarithm, we have for x, y ∈ (Z∕p Z)^∗ that

$$\displaystyle{\log xy\,\, =\,\,\log x +\log y.}$$

Here is an explicit example. Let p = 10000000259. Since $(p - 1)/2$ is prime, it is easy to see that g = 2 is a primitive root modulo p. We have

$$\displaystyle\begin{array}{rcl} \log 3& =& 9635867242, {}\\ \log 5& =& \,\,\,\,227891530, {}\\ \log 7& =& 1803320787, {}\\ & \,\,\,\vdots & {}\\ \end{array}$$

illustrating the fact that there is no simple minded formula for $\log x$ in terms of x. Indeed, the discrete logarithms of the first few primes appear like random numbers in the interval from 0 to p − 1.

Given a prime number p, a primitive root g ∈ (Z∕p Z)^∗ and an exponent a in $\mathbf{Z}/(p - 1)\mathbf{Z}$, the element x = g ^a can be computed efficiently by repeated squarings and multiplications. On the other hand, given a large prime number p and a primitive root g ∈ (Z∕p Z)^∗, there are at present no good methods to compute the discrete logarithm of a given element x ∈ (Z∕p Z)^∗. In other words, computing the exponent $a \in \mathbf{Z}/(p - 1)\mathbf{Z}$ for which x = g ^a, is a very difficult problem. In particular, there is no polynomial time algorithm known to perform this calculation. There do, however, exist subexponential algorithms.

Designing good algorithms to compute discrete logarithms is a problem that is of interest in itself. It is also relevant for applications in cryptography. The security of the Diffie-Hellmann key exchange protocol [6] relies on the assumption that computing discrete logarithms is very hard. More precisely, the working hypothesis of this protocol is that given a prime number p, a primitive root g modulo p and elements x and y in (Z∕p Z)^∗, but not their discrete logarithms a and b, it is very hard to compute the element g ^ab.

In this expository paper we describe some methods for computing discrete logarithms. We do not pretend to present the best known ones, but merely try to give the main ideas behind the most commonly used algorithms. In Sect. 2 we describe a natural generalization of the discrete logarithm problem and we discuss the baby-step-giant-step method due to Dan Shanks and a probabilistic method due to John Pollard. Section 3 is dedicated to the subexponential index calculus algorithm. In Sect. 4 we discuss the discrete logarithm problem for multiplicative groups of finite fields of relatively small characteristic. In particular, we describe recent work of Antoine Joux and others. Finally in Sect. 5, we discuss the discrete logarithm problem for groups of points of elliptic curves over finite fields. This is relevant for applications in cryptography.

I thank Hendrik Lenstra for several useful comments on an earlier version of this paper.

2 Exponential Algorithms

Following ideas in [11, Sect. 7], we consider the following general problem. It is a natural extension of the discrete logarithm problem.

Problem.

Given a finite set S, a finite abelian group A and a group homomorphism

$$\displaystyle{f: \mathbf{Z}^{S}\longrightarrow A,}$$

determine the kernel of f.

In applications, the group A is the multiplicative group of a finite field or the multiplicative group (Z∕n Z)^∗ of the finite ring Z∕n Z. It can also be an ideal class group of a number field, or the group of points of an elliptic curve or of an abelian variety over a finite field. In general, we assume that A is given to us in such a way that we can efficiently compose elements, calculate inverses and test for equality. Usually we even require that every element in A has a unique, easily computable “reduced” representative. But in general we do not suppose that we know the structure or even the cardinality of A. In most applications we know an upper bound for # A. Since Hom(Z ^S, A) is naturally isomorphic to A ^S, the map f can be specified by giving # S elements in A indexed by s ∈ S. The kernel of f is a free group of the same rank as Z ^S. It can be described by giving # S generators.

If S consists of one element, then f is determined by f(1) = x ∈ A. Determining the kernel of f is the same problem as determining the order of the element x ∈ A. An algorithm that solves this problem for the group $A = (\mathbf{Z}/n\mathbf{Z})^{{\ast}}$ can be used to factor the integer n. See [13, Lemma 5]. If # S = 2 and f is therefore given by two elements x, y ∈ A, determining the kernel of f is the same as finding all relations between x and y that are of the form x ^k y ^m = 1 with (k, m) ∈ Z ². In particular, if A is a cyclic group of order m generated by x, so that y = x ^a for some a ∈ Z, then the kernel of f is the subgroup generated by (m, 0) and (a, −1) ∈ Z ². Determining $\ker f$ is therefore the same problem as computing the ‘discrete logarithm’ a of y.

In general, the difficulty in computing the kernel of a group homomorphism f: Z ^S ⟶ A does not depend on the group structure of the finite abelian group A, but rather on the way it is presented. For instance, if A is the additive group Z∕n Z of integers modulo n, presented in the usual way, the problem is very easy. It can be solved using at most O(# S) gcd computations in the ring Z, which can be efficiently calculated by means of the Euclidean algorithm. Indeed, when # S = 1 the kernel of f: Z ⟶ Z∕n Z is generated by n∕d, where d = gcd(f(1), n). For larger S one proceeds inductively, dealing in a similar way with one element of S at the time. On the other hand, if A is the cyclic multplicative group F _p ^∗ or the group E(F _p ) of an elliptic curve over F _p for some large p, there are no methods known to compute the kernel of a homomorphism f: Z ^S ⟶ A that are of a comparable efficiency.

Let f: Z ^S ⟶ A be a homomorphism. Since both A and S are finite sets, the problem of determining the kernel of f is a finite issue. The straightforward naive algorithm to solve it, runs as follows. First assume that # S = 1. In other words, we are given an element in x ∈ A and we wish to compute its order. This can be done by computing the powers 1, x, x ², … of x until x ⁱ is equal to the neutral element 1 ∈ A. The exponent i is then the order of x and generates $\ker f$. When S is larger and f is determined by elements x, y, z, … ∈ A, we first list the elements of the subgroup H generated by x as above. Next we list all elements in the cosets y ⁱ H for i = 0, 1, 2, … The smallest exponent i for which y ⁱ H = H gives rise to a relation of the form y ⁱ = x ^j and hence to an element in the kernel of f. Next one puts $H =\langle x,y\rangle$ and lists all elements of the cosets z ⁱ H … etc. This method uses O(# A # S) operations in A. Since eventually all elements of A may be listed, the amount of memory required is O(# A).

If we can compute a proper non-trivial subgroup B of A, then the problem of computing the kernel K of f: Z ^S ⟶ A can be reduced to two similar problems involving the subgroup B and the quotient group $B' = A/B$. More precisely, writing π for the canonical map A ⟶ B′ and K′ for the kernel of the composite map π ⋅ f: Z ^S ⟶ A ⟶ B, we have the following commutative diagram with exact rows and columns

The group K′ is isomorphic to Z ^S′ for some finite set S′ having the same cardinality as S. The map f maps K′ to B. Since the kernel of the homomorphism f: K′ ⟶ B, is isomorphic to K, we can compute K by first computing the kernel K′ of π ⋅ f: Z ^S ⟶ B′ and then the kernel of f: K′ ⟶ B.

The groups B and B′ are smaller than A. Since B is contained in A, one can efficiently compose elements, calculate inverses and test for equality in B. Therefore, if one is also able to do this in the group $B' = A/B$, then it is usually a good idea to make this reduction. This observation is due to Pohlig-Hellmann [16]. It applies for instance, if one knows a section j: B′ ⟶ A of π so that $A\mathop{\cong}B \times B'$. In this case equality tests in B′ can be performed in A. Another example is the case when A is cyclic and we know a proper divisor d of the order of n = # A. Then we can take B = dA and compute in $B' = A/dA$ exploiting the isomorphism $B'\mathop{\cong}(n/d)A$ given by multiplication by n∕d. It follows that computing the kernel of f: Z ^S ⟶ A is relatively easy when all prime divisors of # A are small. Therefore, in this paper one should keep in mind groups A, for which # A is divisible by at least one large prime number.

Next we describe a more efficient algorithm to compute the kernel of a homomorphism f: Z ^S ⟶ A. It is the baby-step-giant-step algorithm due to Dan Shanks [20]. It is deterministic and uses $O(\#S\sqrt{\#A})$ operations and equality tests in the group A. It also requires the storage of $O(\sqrt{\#A})$ elements of A. We explain the algorithm in the case # S = 1. For larger S, the idea remains the same, but, as in our description above of the naive algorithm, the details are more cumbersome to write down [3]. Any homomorphism f: Z ⟶ A is determined by the element x = f(1) of A. Let a be the integer part of $\sqrt{\#A} + 1$. We first make baby-steps. This means that we make a list of the elements x ⁱ for 0 ≤ i < a. If for some i in this range, x ⁱ is the neutral element of A, we are done: the smallest such i is the order of x and generates the kernel of f. If this is not the case, we make giant steps: we put y = x ^a and compute y ^j for 1 ≤ j ≤ a. Each time we check whether y ^j is in the list that we made. In order to be able to do this efficiently, we assume that the elements in A are presented in some unique “reduced” way and that the list of the elements x ⁱ for 0 ≤ i ≤ a is sorted with respect to this presentation. Since the order of x is at most # A < a ², it is bound to happen that for some j, the element y ^j is in the list. If it does, we have $x^{i} = y^{j} = x^{aj}$ for some i = 0, 1, …, a. The first value of j for which this happens has the property that aj − i is the order of x and hence generates the kernel of f.

There are also probabilistic algorithms to compute the kernel of f: Z ^S ⟶ A. They have the same running time as the baby-step-giant-step algorithm. The advantage of the probabilistic algorithms is, that they do not require making lists of size $\sqrt{\#A}$. We describe the so-called ϱ-algorithm, due to John Pollard [17]. Once again we explain the algorithm only in the case # S = 1. In this case, we put x = f(1) and make a random, or rather pseudorandom, walk by evaluating elements of the form $x^{n_{i}}$ for i = 0, 1, 2, … with 1 = n ₀ < n ₁ < n ₂ …. This means that for each i, the next element $x^{n_{i+1}}$ is computed in a pseudorandom fashion from the element $x^{n_{i}} \in A$. By the birthday paradox, one expects that $x^{n_{i}} = x^{n_{j}}$ for two distinct values of i, j that are $O(\sqrt{\#A})$. Moreover, this can be detected efficiently using the cycle detection algorithm, attributed to R.W. Floyd by Knuth [9, p. 7]. The order of x divides n _i − n _j . In practice the quotient is small, so that the order of x can be computed easily.

3 Index Calculus

Index calculus is a method to compute discrete logarithms and, more generally, to determine kernels of homomorphisms f: Z ^S ⟶ A, that applies when A is the multiplicative group of a finite field. In this section we assume that A = F _p ^∗ for some large prime p. In the next section we consider the case where A is the multiplicative group of a finite field of small characteristic.

Before considering the map f, we do a precomputation and use the index calculus algorithm to compute the kernel of

$$\displaystyle{h: \mathbf{Z}^{T}\longrightarrow \mathbf{F}_{ p}^{{\ast}},}$$

where T is the set of the primes l ≤ X for some bound X < p and h is the homomorphism that, for any prime l ≤ X, maps the lth basis vector of Z ^T to l (mod p). The kernel of h consists of the vectors (x _l ) _l ∈ T  ∈ Z ^T that satisfy

$$\displaystyle{\prod _{l\in T}l^{x_{l} } = 1\,\,\mbox{ in $\mathbf{Z}_{p}^{{\ast}}$}}$$

and hence

$$\displaystyle{\sum _{l\in T}x_{l}\log l \equiv 0\,\,(\mathrm{mod}\,\,p - 1),}$$

where $\log l$ denotes the discrete logarithm of l with respect to any fixed primitive root in F _p ^∗. The algorithm to determine $\ker h$ runs as follows. Pick random exponents e(l) ≥ 0 with $\sum _{l\in T}e(l)$ bounded by some power of $\log p$, that is sufficiently large in the sense that the products $\prod _{l\in T}l^{e(l)}$ exceed p. Then check whether the remainder modulo p of $\prod _{l\in T}l^{e(l)}$ is “X-smooth”. In other words, check whether its factorization in the ring Z is of the form $\prod _{l\in T}l^{f(l)}$. If it is, we obtain the relation

$$\displaystyle{\prod _{l\in T}l^{e(l)}\,\, =\,\,\prod _{ l\in T}l^{f(l)},\qquad \mbox{ in $\mathbf{F}_{ p}^{{\ast}}$}.}$$

It follows that the vector (e(l) − f(l)) _l ∈ S is in the kernel of h:

$$\displaystyle{\sum _{l\in T}(e(l) - f(l))\log l = 0,\qquad \mbox{ in $\mathbf{Z}/(p - 1)\mathbf{Z}$}.}$$

Repeating this procedure, we occasionally find that $\prod _{l\in T}l^{e(l)}$ is X-smooth, hence obtain a non-trivial relation and thus a non-zero vector in the kernel of h. Once we have obtained a bit more than # T vectors, it is reasonable to expect that the vectors that we found, generate the kernel.

It remains to choose the value of X. If X is very small with respect to p, there are very few X-smooth numbers in the set {1, 2, …, p − 1}. Since the remainders of the products $\prod _{l\in T}l^{e(l)}$ appear to be distributed randomly in this set, it is difficult to obtain relations and the algorithm may be time consuming. On the other hand, if X is very large, it is much easier to find X-smooth numbers and vectors in $\ker h$. However, since we need more than # T relations, we need to find many more of them and the algorithm may also be time consuming.

The optimal value of X is somewhere in the middle. It depends on the probability that a random natural number less than p is X-smooth. Writing $X = p^{1/u}$ for some u > 1, this probability is roughly u ^−u. See [4]. A back of an envelope computation shows that the optimal value for u is approximately $u = 2\sqrt{\log p/\log \log p}$. With this choice of u, computing the kernel of f involves

$$\displaystyle\begin{array}{rcl} \exp (2\sqrt{\log p\log \log p})& & {}\\ \end{array}$$

elementary operations with numbers that have $O(\log p)$ digits. Therefore this is a subexponential algorithm.

With this choice of u, the set of primes l ≤ X almost certainly generates F _p ^∗, so that f is surjective. Therefore the induced map

$$\displaystyle{\overline{h}: (\mathbf{Z}/(p - 1)\mathbf{Z})^{T}\longrightarrow \mathbf{F}_{ p}^{{\ast}}}$$

is also surjective and hence split. This means that the kernel of $\overline{h}$ is the zero set of a single linear equation $\sum _{l\in T}a_{l}X_{l} \equiv 0\,\,(\mathrm{mod}\,\,p - 1)$, with coefficients a _l equal to $\log l$ with respect to the primitive root g that is given by $g =\prod _{l\in T}l^{y_{l}}$. Here (y _l ) _l ∈ T is any vector for which one has $\sum _{l\in T}a_{l}y_{l} = 1$ in $\mathbf{Z}/(p - 1)/\mathbf{Z}$. The equation can be computed efficiently using linear algebra over the ring $\mathbf{Z}/(p - 1)\mathbf{Z}$. This completes the description of the precomputation.

In order to explain how to determine the kernel of the given homomorphism

$$\displaystyle{f: \mathbf{Z}^{S}\longrightarrow \mathbf{F}_{ p}^{{\ast}},}$$

we consider first the case that # S = 1. In this case f is determined by the element x = f(1) ∈ F _p ^∗ and the kernel of f is generated by the order of x in the group F _p ^∗. To compute the kernel, pick random products $x\prod _{l\in T}l^{e(l)}$ with T as above and check whether the factorization in Z of the remainder modulo p is of the form $\prod _{l\in T}l^{f(l)}$. If this happens, we obtain the relation

$$\displaystyle{x\prod _{l\in T}l^{e(l)}\,\, =\,\,\prod _{ l\in T}l^{f(l)},\qquad \mbox{ in $\mathbf{F}_{\mathit{ p}}^{{\ast}}$}.}$$

This implies that

$$\displaystyle{\log x\,\, =\,\,\sum _{l\in T}(f(l) - e(l))\log l,\quad \mbox{ in $\mathbf{Z}/(\mathit{p} - 1)\mathbf{Z}$.}}$$

Since we already have computed $\log l$ for every l ∈ T, we can now evaluate $\log x$. The order of x in the group F _p ^∗ is equal to the order of $\log x$ in the additive group $\mathbf{Z}/(p - 1)\mathbf{Z}$. It is therefore equal to p − 1 divided by $\mathrm{gcd}(p - 1,\log x)$.

The method for # S > 1 is based on this. One computes the discrete logarithm of f(s) for each element s ∈ S. Composing f: Z ^S ⟶ F _p ^∗ with the discrete logarithm gives a homomorphism from Z ^S to the additive group $\mathbf{Z}/(p - 1)\mathbf{Z}$. As remarked above, determining the kernel of such a homomorphism is easy and can be done by means of linear algebra over Z.

4 Finite Fields

Recently there has been great progress in solving the discrete logarithm problem for finite fields of small characteristic. Indeed, in [1, 5, 7, 8] algorithms are described that almost run in polynomial time. As in the previous section, the algorithms proceed by first computing the logarithms of a set of elements—the factor base—that are, in some sense, small. Next one uses this to solve the problem of computing the discrete logarithm of an individual element that is not in the factor base. Here we describe the first phase following Antoine Joux and his collaborators [1]. For the second phase we refer to the papers mentioned above for more details.

As a typical example of the method, we discuss the case of a finite field of Q = q ^2k elements, where q is a prime power and k is of the same order of magnitude as q. See [1] for a precise description of the range of finite fields for which the algorithm is effective. Let $\mathbf{F}_{q^{2}}$ denote the subfield of q ² elements of F _Q . Note that if k and q are approximately equal, q ² is small with respect to Q = q ^2k. Therefore, making a list of all elements of $\mathbf{F}_{q^{2}}$ can be done in time polynomial in $\log Q$. As a consequence, computing discrete logarithms of elements in $\mathbf{F}_{q^{2}}^{{\ast}}$ can be done in time polynomial in $\log Q$ as well. Therefore, the Pohlig-Hellmann argument of Sect. 2 reduces the problem of computing discrete logarithms in the group F _Q ^∗ to the problem of computing discrete logarithms in the group $A = \mathbf{F}_{Q}^{{\ast}}/\mathbf{F}_{q^{2}}^{{\ast}}$.

We assume that the field with Q = q ^2k elements is represented as $\mathbf{F}_{q^{2}}[X]/(\phi (X))$, where ϕ(X) is an irreducible degree k polynomial in $\mathbf{F}_{q^{2}}[X]$. In order to have an efficient algorithm, the polynomial ϕ(X) in $\mathbf{F}_{Q} = \mathbf{F}_{q^{2}}[X]/(\phi (X))$ is supposed to have a special shape: we want that

$$\displaystyle{X^{q} \equiv r(X)\,\,\text{mod}\,\,\phi (X),}$$

for some rational function $r(X) \in \mathbf{F}_{q^{2}}(X)$ whose numerator and denominator have very small degrees. Examples are provided by the polynomials $\phi (X) = X^{q-1} - g$ or $X^{q+1} - g$, where g is a generator of the cyclic group $\mathbf{F}_{q^{2}}^{{\ast}}$. In the first case we have r(X) = gX and in the second $r(X) = g/X$. See [23]. Numerical experiments suggest [1] that when k is close to q, one can find a rational function r(X) with denominator and numerator of degree at most 2, for which X ^q − r(X) is divisible by an irreducible degree k polynomial ϕ(X). Since an algorithm of Lenstra [10] allows one to compute an isomorphism between any presentation of the finite field F _Q and $\mathbf{F}_{q^{2}}[X]/(\phi (X))$ in polynomial time, requiring ϕ(X) to have this special shape, is not a serious restriction.

In the first phase of the algorithm we compute the discrete logarithms of the elements in a factor base, which in this case consists of the images of all monic linear polynomials in $\mathbf{F}_{q^{2}}[X]$ in the group $A = \mathbf{F}_{q^{2}}[X]/(\phi (X))^{{\ast}}/\mathbf{F}_{q^{2}}^{{\ast}}$. Putting $T = \mathbf{F}_{q^{2}}$, this means that we compute the kernel of the homomorphism

$$\displaystyle{h: \mathbf{Z}^{T}\longrightarrow A,}$$

that maps the basisvector e _u corresponding to u ∈ T to the image of X − u in the group $A = (\mathbf{F}_{q^{2}}[X]/(\phi (X)))^{{\ast}}/\mathbf{F}_{q^{2}}^{{\ast}}$.

The identity

$$\displaystyle{X^{q} - X\, =\,\prod _{ u\in \mathbf{F}_{q}}(X - u)}$$

implies that

$$\displaystyle{r(X) - X\, =\,\prod _{u\in \mathbf{F}_{q}}(X - u),\qquad \text{in}\ \mathbf{F}_{\mathit{q}^{2}}[X]/(\phi (X)).}$$

The denominator of the rational function r(X) − X is equal to the one of r(X). For the sake of exposition, we suppose that it factors into a product of linear polynomials in $\mathbf{F}_{q^{2}}[X]$. Its numerator has degree at most 3 and may or may not factor into a product of linear polynomials in $\mathbf{F}_{q^{2}}[X]$. If it does, we obtain a multiplicative relation in the group A between the elements of our factor base. The relation gives then rise to an element in the kernel of the homomorphism h: Z ^T ⟶ A.

In order to get more relations, we apply automorphisms of the fraction field $\mathbf{F}_{q^{2}}(X)$ of $\mathbf{F}_{q^{2}}[X]$. The group $\mathrm{PGL}_{2}(\mathbf{F}_{q^{2}})$ acts on the right on $\mathbf{F}_{q^{2}}(X)$ as follows:

$$\displaystyle{f^{\sigma }(X)\, =\, f(\frac{aX + b} {cX + d}),\qquad \text{for any}\ \sigma = \left (\begin{array}{*{10}c} a&b\\ c &d\\ \end{array} \right ) \in \mathrm{ PGL}_{2}(\mathbf{F}_{q^{2}}).}$$

Applying $\sigma \in \mathrm{ PGL}_{2}(\mathbf{F}_{q^{2}})$ to the identity above, we obtain the equality

$$\displaystyle{(X^{\sigma })^{q} - X^{\sigma }\, =\, (X^{q} - X)^{\sigma }\, =\,\prod _{ u\in \mathbf{F}_{q}}(X^{\sigma } - u),\qquad \text{in}\ \mathbf{F}_{ q^{2}}(X).}$$

The group $\mathrm{PGL}_{2}(\mathbf{F}_{q^{2}})$ acts via linear fractional transformations on the left on the projective line P ₁ and preserves the set of $\mathbf{F}_{q^{2}}$-points $\mathbf{P}_{1}(\mathbf{F}_{q^{2}})$. We view $\mathbf{F}_{q^{2}}$ as a subset of $\mathbf{P}_{1}(\mathbf{F}_{q^{2}})$. So we have $\mathbf{P}_{1}(\mathbf{F}_{q^{2}}) = \mathbf{F}_{q^{2}} \cup \{\infty \}$. For a function $f \in \mathbf{F}_{q^{2}}(X)$, a point $u \in \mathbf{P}_{1}(\mathbf{F}_{q^{2}})$ and an automorphism $\sigma \in \mathrm{ PGL}_{2}(\mathbf{F}_{q^{2}})$, we have $f^{\sigma }(u) = f(\sigma (u))$.

The above identity for $\sigma = \left (\begin{array}{*{10}c} a&b\\ c &d\\ \end{array} \right ) \in \mathrm{ PGL}_{2}(\mathbf{F}_{q^{2}})$ then becomes

$$\displaystyle{(cX + d)(aX + b)^{q} - (aX + b)(cX + d)^{q} =\prod _{ u\in \sigma ^{-1}(\mathbf{P}_{1}(\mathbf{F}_{q}))-\{\infty \}}(X - u).}$$

It holds in the function field $\mathbf{F}_{q^{2}}(X)$ up to multiplication by some $\lambda \in \mathbf{F}_{q^{2}}^{{\ast}}$. Note that the set $\sigma ^{-1}(\mathbf{P}_{1}(\mathbf{F}_{q}))$ consists of q + 1 points and may or may not contain the point $\infty$. Since X ^q ≡ r(X) modulo ϕ(X), we have

$$\displaystyle{(aX + b)^{q} \equiv \overline{a}r(X) + \overline{b}\quad \text{and}\quad (cX + d)^{q} \equiv \overline{c}r(X) + \overline{d}}$$

in $\mathbf{F}_{q^{2}}[X]/(\phi (X))$. Here we put $\overline{t} = t^{q}$ for $t \in \mathbf{F}_{q^{2}}$. This leads to the following relation

$$\displaystyle{ (cX + d)(\overline{a}r(X) + \overline{b}) - (aX + b)(\overline{c}r(X) + \overline{d}) =\prod _{u\in \sigma ^{-1}(\mathbf{P}_{1}(\mathbf{F}_{q}))-\{\infty \}}(X - u). }$$

(*)

It holds in the ring $\mathbf{F}_{q^{2}}[X]/(\phi (X))$ up to multiplication by some $\lambda \in \mathbf{F}_{q^{2}}^{{\ast}}$. The denominator of the left hand side of this equation is equal to the one of r(X). The numerator has degree at most 3 and it seems reasonable to expect that it varies randomly when we vary $\sigma$. Numerical experiments have confirmed this [1]. Under this assumption a positive proportion factors into a product of linear polynomials in $\mathbf{F}_{q^{2}}[X]$. Indeed, this proportion is approximately 1∕6. For other choices of r(X), see [15]. A positive proportion of the relations (∗) are therefore multiplicative relations between the elements X − u of the factor base in the group $A = (\mathbf{F}_{q^{2}}[X]/(\phi (X)))^{{\ast}}/\mathbf{F}_{q^{2}}^{{\ast}}$. They give rise to elements in the kernel of the homomorphism h: Z ^T ⟶ A.

The question is how many independent multiplicative relations between the elements X − u of the factor base we obtain in this way. The discrete logarithms of the elements X − u of the factor base are a solution of the system of linear equations that we obtain from the relations (∗). There is at present no proof that we obtain sufficiently many relations for the linear system to have a unique solution over Z∕M Z, where M = # A. However, there are some heuristic arguments in this direction that seem to be confirmed by experiments [1].

The subgroup of $\mathrm{PGL}_{2}(\mathbf{F}_{q^{2}})$ that preserves the subset P ₁(F _q ) of $\mathbf{P}_{1}(\mathbf{F}_{q^{2}})$, is equal to PGL₂(F _q ). Therefore, the set $\sigma ^{-1}(\mathbf{P}_{1}(\mathbf{F}_{q}))$ and hence the right hand side of the relation (∗), depends only on the left coset $\sigma ^{-1}\mathrm{PGL}_{2}(\mathbf{F}_{q})$ rather than on $\sigma ^{-1}$ itself. The number of cosets is equal to $\#\mathrm{PGL}_{2}(\mathbf{F}_{q^{2}})/\#\mathrm{PGL}_{2}(\mathbf{F}_{q}) = q^{3} + q$. It follows that there are q ³ + q different subsets $\sigma ^{-1}(\mathbf{P}_{1}(\mathbf{F}_{q}))$ and hence q ³ + q possibilities for the right hand sides of the relations (∗). For a positive proportion the left hand sides of (∗) factor into products of linear polynomials in $\mathbf{F}_{q^{2}}[X]$. Therefore one expects many more than q ² relations between the elements X − u of the factor base, at least when q is not very small. As a consequence we obtain many more than q ² elements in the kernel of the homomorphism h: Z ^T ⟶ A.

The subsets $\sigma ^{-1}(\mathbf{P}_{1}(\mathbf{F}_{q}))$ and therefore the right hand sides of the relations, are very different from one another. Indeed, it easy to see that any two distinct subsets $\sigma ^{-1}(\mathbf{P}_{1}(\mathbf{F}_{q}))$ intersect in at most two points. Moreover, when $\sigma$ runs over representatives of the cosets of PGL₂(F _q ) in $\mathrm{PGL}_{2}(\mathbf{F}_{q^{2}})$ and P runs over the points of $\mathbf{P}_{1}(\mathbf{F}_{q^{2}})$, the q ³ + q by q ² + 1 matrix $m_{\sigma,P}$ given by

$$\displaystyle\begin{array}{rcl} m_{\sigma,P}& =& \left \{\begin{array}{l l} 1,&\text{when}\ P \in \sigma ^{-1}(\mathbf{P}_{ 1}(\mathbf{F}_{q})); \\ 0,&\text{otherwise.}\\ \end{array} \right.{}\\ \end{array}$$

has maximal rank q ² + 1. See [1]. In fact, it is not difficult to show that its rows span a subgroup of index q + 1 in $\mathbf{Z}^{q^{2}+1 }$. The matrix of the homogeneous linear system we want to solve consists of the subset of rows of the matrix $m_{\sigma,P}$ for which the left hand side of (∗) factors completely, somewhat perturbed by the few non-zero coefficients that come from the left hand side of (∗). Since the matrix $m_{\sigma,P}$ has maximal rank, it is perhaps not unreasonable to expect that our linear system has a unique solution over Z∕M Z, where M = # A.

It was pointed out by Wan et al. [5] that there is a problem with linear polynomials X − u that divide $(X^{q} - r(X))/\phi (X)$. Indeed, the relations that we find, not only hold modulo ϕ(X), but also modulo X − u. Typically the multiplicity of X − u is the same on both sides of the relations (∗). This cancellation implies that the logarithm of X − u does not appear in the linear system. Therefore it cannot be computed this way. For instance, in the case $\phi (X) = X^{q-1} - g$, we have r(X) = gX and $X^{q} - gX = X\phi (X)$. In this case, the logarithm of X may not at all appear in the linear system. In this special case however, computing the logarithm of X is easy since its order in the group A is q − 1, which is very small. See the original papers [1, 8] for ways to get around this problem in general.

5 Elliptic Curves

Elliptic curve cryptography is based on the difficulty of solving the discrete logarithm problem in the finite group E(F _q ) of points of an elliptic curve E over a finite field F _q . More generally, determining the kernel of a homomorphism

$$\displaystyle{f: \mathbf{Z}^{S}\longrightarrow E(\mathbf{F}_{ q}),}$$

is a difficult problem. Apart from some exceptional situations that we describe below, the only methods that are available at present, are the baby-step-giant-step method and the Pollard ϱ-method that were discussed in Sect. 2. Since # E(F _q ) ≈ q, both methods require $O(\sqrt{q})$ operations in the group E(F _q ). This is much more than the number of operations required by the subexponential index calculus algorithm that was described in Sect. 3. Therefore, in cryptographical systems based on elliptic curves, key sizes can be made smaller, so that encryption and decryption algorithms are faster.

Suppose that E is an elliptic curve over a finite field F _q given by a Weierstrass equation

$$\displaystyle{Y ^{2} + a_{ 1}XY + a_{3}\, =\, X^{3} + a_{ 2}X^{2} + a_{ 4}X + a_{6},}$$

with coefficients a _i  ∈ F _q . See [21] for the basic properties of elliptic curves. We let $E(\overline{\mathbf{F}}_{q})$ denote the group of points on E with coordinates in an algebraic closure $\overline{\mathbf{F}}_{q}$ of F _q . It is an infinite torsion group. The set E(F _q ) of points on E with coordinates in F _q is a finite subgroup. For every natural number n, we let E[n] denote the group of points on E that are annihilated by n. In other words, we have

$$\displaystyle{E[n]\, =\,\{ P \in E(\overline{\mathbf{F}}_{q}): nP = 0\}.}$$

If n is not divisible by the characteristic p of F _q , the group E[n] is isomorphic to $\mathbf{Z}/n\mathbf{Z} \times \mathbf{Z}/n\mathbf{Z}$. The Weil pairing is a bilinear, antisymmetric and non-degenerate pairing

$$\displaystyle{e_{n}: E[n] \times E[n]\longrightarrow \mu _{n}.}$$

Here μ _n denotes the subgroup of nth roots of unity of $\overline{\mathbf{F}}_{q}^{{\ast}}$. The pairing e _n is Galois equivariant.

Suppose now that the group E(F _q ) is cyclic of order n, coprime to p. Let Q ∈ E[n] be a point of order n with the property that the subgroup it generates has trivial intersection with E(F _q ). Then the map

$$\displaystyle{g: E(\mathbf{F}_{q})\longrightarrow \mu _{n}}$$

given by g(P) = e _n (P, Q) is an injective group homomorphism. It can be efficiently computed by means of an algorithm invented by Victor Miller [14]. In this way the kernel of f: Z ^S ⟶ E(F _q ) can be calculated by computing the kernel of the composite homomorphism

$$\displaystyle{\mathbf{Z}^{S}\mathop{ \longrightarrow }\limits ^{f}E(\mathbf{F}_{ q})\mathop{\longrightarrow }\limits ^{g}\mu _{ n}\hookrightarrow \mathbf{F}_{q^{d}}^{{\ast}}.}$$

Here d is the order of q modulo n. This approach is due to Menezes et al. [12]. It reduces the problem of computing the kernel of a homomorphism Z ^S ⟶ E(F _q ) to a similar problem involving the multiplicative group $\mathbf{F}_{q^{d}}^{{\ast}}$ rather than E(F _q ).

Since the Weil pairing is Galois equivariant, the field of definition of the point Q contains $\mathbf{F}_{q^{d}}$. Since d is typically very large, computing in the group $E(\mathbf{F}_{q^{d}})$ is very costly and this approach is usually not very successful. However, in certain special cases it can be very effective. An important example is provided by supersingular elliptic curves over prime fields F _p . When p ≡ 1 (mod 4), the group E(F _p ) of a supersingular curve E is cyclic of order p + 1. In this case μ _p+1 is contained in an extension of F _p that has only degree d = 2. Therefore this method is very efficient. With small modifications it also works when p ≡ 3 (mod 4) and more generally when the order of q modulo n = # E(F _q ) is small. In this situation, this use of the Weil pairing is an efficient way to compute discrete logarithms or, more generally, to compute the kernels of homomorphisms f: Z ^S ⟶ E(F _q ).

An even faster algorithm was invented by Semaev [19] for elliptic curves E over prime fields F _p , for which the group E(F _p ) has order p. In this case an isomorphism

$$\displaystyle{g: E[p]\longrightarrow \mathbf{Z}/p\mathbf{Z}}$$

is constructed as follows. We fix a non-zero point Q in E(F _p ). For P ∈ E(F _p ) we put

$$\displaystyle{g(P)\, =\, \frac{f_{P}'} {f_{P}}(Q).}$$

Here f _P is a function on E whose divisor is equal to $p(Q -\infty )$. We let f _P ′ denote the function for which we have the following equality of Kähler differentials: df _P  = f _P ′dX. The map g can be efficiently computed by means of Miller’s algorithm. In this way we can compute the kernel of f: Z ^S ⟶ E(F _p ) by computing the kernel of

$$\displaystyle{\mathbf{Z}^{S}\mathop{ \longrightarrow }\limits ^{f}E(\mathbf{F}_{ p})\mathop{\longrightarrow }\limits ^{g}\mathbf{Z}/p\mathbf{Z}.}$$

Similar related algorithms have been proposed by Satoh and Araki [18] and by Smart [22]. See Belding’s paper [2] for a relation between the algorithms described in this section.