5

Discrete Logarithms

The Discrete Logarithm Problem (DLP) and the Elliptic Curve Discrete Logarithm Problem (ECDLP), along with the Integer Factorization Problem (IFP), are the three most important infeasible computational problems in computational number theory and modern cryptography. In this chapter we discuss several popular and widely used modern algorithms for DLP/ECDLP, including:

• Baby-step Giant-step Method for DLP
• Pohlig–Hellman Algorithm for DLP/ECDLP
• The index calculus for DLP
• The xedni calculus for ECDLP.

5.1 Basic Concepts

The Discrete Logarithm Problem (DLP) can be described as follows:

(5.1)

where the modulus n can either be a composite or a prime.

According to Adleman [1], the Russian mathematician Bouniakowsky developed a clever algorithm to solve the congruence , with the asymptotic complexity in 1870. Despite its long history, no efficient algorithm has ever emerged for the Discrete Logarithm Problem. It is believed to be hard, a little bit harder than the Integer Factorization Problem (IFP) even in the average case. The best known algorithm for DLP at present, using NFS and due to Gordon [2], requires an expected running time

There are essentially three different categories of algorithms in use for computing discrete logarithms:

1. Algorithms that work for arbitrary groups, that is, those that do not exploit any specific properties of groups; Shanks’ Baby-step Giant-step Method, Pollard’s Method (an analogue of Pollard’s Factoring Method) and the Method (also known as wild and tame Kangaroos) are in this category.

2. Algorithms that work well in finite groups for which the order of the groups has no large prime factors; more specifically, algorithms that work for groups with smooth orders. A positive integer is called smooth if it has no large prime factors; it is called y-smooth if it has no large prime factors exceeding y. The well-known Silver–Pohlig–Hellman algorithm based on the Chinese Remainder theorem is in this category.

3. Algorithms that exploit methods for representing group elements as products of elements from a relatively small set (also making use of the Chinese Remainder theorem); the typical algorithms in this category are Adleman’s index calculus algorithm and Gordon’s NFS algorithm.

In this chapter, we shall introduce the basic ideas of the algorithms in each of these three categories; more specifically, we shall introduce Shanks’ Baby-step Giant-step algorithm, the Silver–Pohlig–Hellman algorithm, Adleman’s index calculus algorithm, as well as Gordon’s NFS algorithm for computing discrete logarithms. In the last section of this chapter, we shall also deal with algorithms for ECDLP.

Problems for Section 5.1

1. What are the main differences between the familiar logarithms over and the discrete logarithms?

2. Let

then

Find the logarithm k over :

3. Use the exhaustive method to find the following discrete logarithms k over , if there exists:

1.

2. .

3. .

4. Use the exhaustive method to find the following elliptic curve discrete logarithms k over :

that is,

where E is the elliptic curve defined by

5.2 Baby-Step Giant-Step Method

The Baby-step Giant-step Method is a meet-in-the-middle algorithm for computing the discrete logarithm. It was first studied in 1968 to calculate the class number of an imaginary quadratic field [3]. Let G be a finite cyclic group of order n, a a generator of G and . The obvious algorithm for computing successive powers of a until b is found takes group operations. For example, to compute , we compute for until for some x is found, that is:

So . It is clear that when n is large, the algorithm is inefficient. In this section, we introduce a type of square root algorithm, called the baby-step giant-step algorithm, for taking discrete logarithms, which is better than the above mentioned obvious algorithm. The algorithm works for every finite cyclic group.

Let . The baby-step giant-step algorithm is based on the observation that if x = logab, then we can uniquely write x = i + jm, where . For example, if , then a = 2, b = 15, m = 5, so we can write 11 = i + 5j for . Clearly here i = 1 and j = 2 so we have . Similarly, for we can write , for we can write , etc. The following is a description of the algorithm:

Algorithm 5.1 (Shanks’ baby-step giant-step algorithm) This algorithm computes the discrete logarithm x of y to the base a, modulo n, such that :

1. (Initialization) Computes .

2. (Computing the Baby Step) Compute the first sequence (list), denoted by S, of pairs (yar, r), :

(5.2)

and sort S by yar, the first element of the pairs in S.

3. (Computing the Giant Step) Compute the second sequence (list), denoted by T, of pairs (ats, ts), :

(5.3)

and sort T by ats, the first element of the pairs in T.

4. (Searching, comparing and computing) Search both lists S and T for a match yar = ats with yar in S and ats in T, then compute x = ts−r. This x is the required value of .

This algorithm requires a table with entries (, where n is the modulus). Using a sorting algorithm, we can sort both the lists S and T in operations. Thus this gives an algorithm for computing discrete logarithms that uses time and space for group elements. Note that Shanks’ idea was originally for computing the order of a group element G in the group G, but here we use his idea to compute discrete logarithms. Note also that although this algorithm works on arbitrary groups, if the order of a group is larger than 1040, it will be infeasible.

Example 5.1 Suppose we wish to compute the discrete logarithm such that . According to Algorithm 12, we perform the following computations:

1. y = 6, a = 2 and n = 19, .

2. Computing the baby step:

3. Computing the giant step:

4. Matching and computing: The number 5 is the common value of the first element in pairs of both lists S and T with r = 2 and st = 16, so x = st−r = 16−2 = 14. That is, , or equivalently, .

Example 5.2 Suppose now we wish to find the discrete logarithm , such that . Again by Algorithm 5.1, we have:

1. y = 67, a = 59 and n = 113, .

2. Computing the baby step:

3. Computing the giant-step:

4. Matching and computing: The number 99 is the common value of the first element in pairs of both lists S and T with r = 9 and st = 20, so x = st−r = 20−9 = 11. That is, , or equivalently, .

Remark 5.1 Shanks’ baby-step giant-step algorithm is a type of Square Root Method for computing discrete logarithms. In 1978 Pollard [4] also gave two other types of Square Root Methods, namely the Method (an analogue of Pollard’s Factoring Method) and the Method (also known as the Wild Kangaroo Method) for computing discrete logarithms. Pollard’s methods are probabilistic but remove the necessity of precomputing the lists S and T, as with Shanks’ Baby-step Giant-step Method. Again, Pollard’s algorithm requires group operations and hence is infeasible if the order of the group G is larger than 1040.

Problems for Section 5.2

1. Use the baby-step giant-step algorithm to find the following DLP(k):

1.

2.

3.

2. Use the baby-step giant-step algorithm to find the following DLP(k):

1.

2.

3.

3. Use the baby-step giant-step algorithm to compute DLP(k):

4. Use the baby-step giant-step algorithm to compute DLP(k):

5. Use the baby-step giant-step algorithm to compute DLP(k):

6. Implement the baby-step giant-step algorithm to compute DLP(k) over a large finite field.

7. Explain how to modify the baby-step giant-step algorithm to find the order of an integer a modulo a prime number p.

5.3 Pohlig–Hellman Method

In 1978, Pohlig and Hellman [5] proposed an important special algorithm, now widely known as the Silver–Pohlig–Hellman algorithm for computing discrete logarithms over GF(q) with operations and a comparable amount of storage, where p is the largest prime factor of q−1. Pohlig and Hellman showed that if

(5.4)

where the pi are distinct primes and the are natural numbers, and if are any real numbers with , then logarithms over GF(q) can be computed in

field operations, using

bits of memory, provided that a precomputation requiring

field operations is performed first. This algorithm is very efficient if q is “smooth,” that is, all the prime factors of q−1 are small. We shall give a brief description of the algorithm as follows:

Algorithm 5.2 (Silver–Pohlig–Hellman Algorithm) This algorithm computes the discrete logarithm

(5.5)

1. Factor q−1 into its prime factorization form:

(5.6)

2. Precompute the table for a given field:

(5.7)

This only needs to be done once for any given field.

3. Compute the discrete logarithm of b to the base a modulo q, that is, compute :

3-1. Use an idea similar to that in the baby-step giant-step algorithm to find the individual discrete logarithms : To compute , we consider the representation of this number to the base pi:

(5.8)

where .

a. To find x0, we compute which equals for some j, and set x0 = j for which

(5.9)

This is possible because

(5.10)

b. To find x1, compute . If

(5.11)

then set x1 = j. This is possible because

c. To obtain x2, consider the number and compute

The procedure is carried on inductively to find all .

3-2. Use the Chinese Remainder theorem to find the unique value of x from the congruences .

We now give an example of how the above algorithm works:

Example 5.3 Suppose we wish to compute the discrete logarithm . Now we have a = 2, b = 62 and q = 181 (2 is a generator of ). We follow the computation steps described in the above algorithm:

1. Factor q−1 into its prime factorization form:

2. Use the following formula to precompute the table for the given field :

This only needs to be done once for this field.

a. Compute

b. Compute

c. Compute

Construct the table as follows:

This table is manageable if all pi are small.

3. Compute the discrete logarithm of 62 to the base 2 modulo 181, that is, compute . Here a = 2 and b = 62:

3–1. Find the individual discrete logarithms using

(a-1) Find the discrete logarithms , that is, :

i. To find x0, we compute

hence x0 = 0.

ii. To find x1, compute first , then compute

hence x1 = 0. So

(a-2) Find the discrete logarithms , that is, :

i. To find x0, we compute

hence x0 = 1.

ii. To find x1, compute first , then compute

hence x1 = 0. So

(a-3) Find the discrete logarithms , that is, :

To find x0, we compute

hence x0 = 0. So we conclude that

3.2. Find the x in

such that

To do this, we just use the Chinese Remainder theorem to solve the following system of congruences:

The unique value of x for this system of congruences is x = 100. (This can be easily done by using, for example, the Maple function chrem([0,1,0], [4,9,5]).) So the value of x in the congruence is 100. Hence x = log262 = 100.

Problems for Section 5.3

1. Use the Silver–Pohliq–Hellman algorithm to solve the DLP

such that

2. Use the Silver–Pohliq–Hellman algorithm to solve the DLP

such that

3. Use the Silver–Pohliq–Hellman algorithm to find the discrete logarithm k such that

4. Use the Silver–Pohliq–Hellman algorithm to find the discrete logarithm k:

5. Suppose that G and h are primitive roots modulo n. Show that

6. Let the prime factorization of n = p−1 be given. Give a complete computational complexity analysis of the Silver–Pohliq–Hellman algorithm for the DLP.

5.4 Index Calculus

In 1979, Adleman [1] proposed a general purpose, subexponential algorithm for computing discrete logarithms, called the index calculus, with the following expected running time:

The index calculus is, in fact, a wide range of methods, including CFRAC, QS, and NFS for IFP. In what follows, we discuss a variant of Adleman’s index calculus for DLP in .

Algorithm 5.3 (Index calculus for DLP) This algorithm tries to find an integer k such that

(5.12)

1. Precomputation

1-1. (Choose Factor Base) Select a factor base , consisting of the first m prime numbers,

(5.13)

with , the bound of the factor base.

1-2. (Compute ) Randomly choose a set of exponent , compute , and factor it as a product of prime powers.

1-3. (Smoothness) Collect only those relations that are smooth with respect to b. That is,

(5.14)

When such relations exist, get

(5.15)

1-4. (Repeat) Repeat [1-3] to find at least m such E in order to find m relations as in (5.15) and solve for .

2. Compute

2-1. For each E in (5.15), determine the value of for by solving the m modular linear equations with unknown .

2-2. (Compute ) Randomly choose exponent and compute .

2-3. (Factor over )

(5.16)

If (5.16) is unsuccessful, go back to to Step [2-2]. If it is successful, then

(5.17)

Example 5.4 (Index calculus for DLP) Find

such that

1. Precomputation

1-1. (Choose Factor Base) Select a factor base , consisting of the first 4 prime numbers,

with , the bound of the factor base.

1-2. (Compute ) Randomly choose a set of exponent , compute , and factor it as a product of prime powers:

1-3. (Smoothness) The above four relations are smooth with respect to B = 7. Thus

2. Compute

2-1. Compute

2-2. (Compute ) Randomly choose exponent and compute .

2-3. (Factor over )

Thus,

That is,

Example 5.5 Find such that .

1. (Factor Base) Let the factor base .

2. (Compute and Factor ) Randomly choose e<p, compute and factor as follows:

3. (Solve the systems of congruences for the quantities )

4. (Compute and Factor ) Randomly choose e<p, compute and factor as follows:

Thus

This is true since

For more than ten years since its invention, Adleman’s method and its variants were the fastest algorithms for computing discrete logarithms. But the situation changed in 1993 Gordon [2] proposed an algorithm for computing discrete logarithms in GF(p). Gordon’s algorithm is based on the Number Field Sieve (NFS) for integer factorization, with the heuristic expected running time

the same as that used in factoring. The algorithm can be briefly described as follows:

Algorithm 5.4 (Gordon’s NFS) This algorithm computes the discrete logarithm x such that with input a, b, p, where a and b are generators and p is prime:

1. (Precomputation): Find the discrete logarithms of a factor base of small rational primes, which must only be done once for a given p.

2. (Compute Individual Logarithms): Find the logarithm for each by finding the logarithms of a number of “medium-sized” primes.

3. (Compute the Final Logarithm): Combine all the individual logarithms (by using the Chinese Remainder theorem) to find the logarithm of b.

Problems for Section 5.4

1. Let the factor base . Use the index calculus method to find the discrete logarithm k:

2. Let the factor base . Use the index calculus method to find the discrete logarithm k:

3. Use the index calculus with factor base to solve the DLP problem

4. Let

Use Gordon’s index calculus method (Algorithm 5.4) to compute the k such that

5. Give a heuristic argument for the expected running time

of Gordon’s index calculus method (based on NFS) for DLP.

6. Let the group with p prime, let also such that . Use smooth numbers to show that the discrete logarithm can be computed in expected time .

5.5 Elliptic Curve Discrete Logarithms

The Elliptic Curve Discrete Logarithm Problem (ECDLP) is of fundamental importance to ECC (elliptic curve cryptography): Let be an elliptic curve over a finite field , say, given by a Weierstrass equation

(5.18)

p and q the two points in the elliptic curve group . Then the ECDLP is to find the integer k (assuming that such an integer k exists)

(5.19)

such that

(5.20)

Formally, the Elliptic Curve Discrete Logarithm Problem (ECDLP) could be defined as follows:

(5.21)

The ECDLP is little bit more difficult than the DLP, on which the elliptic curve digital signature algorithm/elliptic curve digital signature standard (ECDSA/ECDSS) [37] is based on. As ECDLP is the generalization of DLP, which extends, for example, the multiplicative group to the elliptic curve group , many methods for DLP, even for IFP, can be extended to ECDLP, for example, the Baby-step Giant-step for DLP, Pollard’s and Methods for IFP and DLP; the Silver–Pohlig–Hellman Method for DLP, can also be naturally extended to ECDLP. In what follows, we present an example of solving ECDLP by an analog of the Silver–Pohlig–Hellman Method for elliptic curves over .

Example 5.6 Let

where

Find k.

1. Find the individual logarithm modulo 2: as (530/2) = 265, we have

2. Find the individual logarithm modulo 5: as 530/5 = 106, we have

3. Find the individual logarithm modulo 53: as 530/53 = 10, we have

4. Use the Chinese Remainder theorem to combine the individual logarithms to get the final logarithm:

That is,

or alternatively,

The index calculus for DLP is however generally not suitable for ECDLP as it is not for general groups. In what follows, we introduce a method, called xedni calculus for ECDLP. The xedni calculus was first proposed by Joseph Silverman in [42] and [44], and analyzed in [45]. It is called xedni calculus because it “stands index calculus on its head.” The xedni calculus is a new method that might be used to solve the ECDLP, although it has not yet been tested in practice. It can be described as follows:

1. Choose points in and lift them to points in .

2. Choose a curve containing the lift points; use Mestre’s Method (in reverse) to make rank small.

Whilst the index calculus works in reverse:

1. Lift to ; use Mestre’s Method to make rank large.

2. Choose points in and try to lift them to points in .

A brief description of the xedni algorithm is as follows.

Algorithm 5.5 (Xedni calculus for the ECDLP) Let be a finite field with p elements (p prime), an elliptic curve over , say, given by

(5.22)

Np the number of points in , S and T the two points in . This algorithm tries to find an integer k

(5.23)

such that

(5.24)

1. Fix an integer and an integer m which is a product of small primes.

2. Choose r points:

(5.25)

having integer coefficients and satisfying

a. the first 4 points are [1, 0, 0], [0, 1, 0], [0, 0, 1], and [1, 1, 1].

b. for every prime , the matrix has maximal rank modulo l.

Further choose coefficients such that the points satisfy the congruence:

(5.26)

3. Choose r random pair of integers (si, ti) satisfying , and for each , compute the point Pp,i = (xp,i, yp,i) defined by

(5.27)

4. Make a change of variables in of the form

(5.28)

so that the first four points become

The equation for E will then have the form:

(5.29)

5. Use the Chinese Remainder theorem to find integers satisfying

(5.30)

for all .

6. Lift the chosen points to . That is, choose points

(5.31)

with integer coordinates satisfying

(5.32)

for all . In particular, take

7. Let be the matrix of cubic monomials defined earlier. Consider the system of linear equations:

(5.33)

Find a small integer solution to (5.33) which has the additional property

(5.34)

where are the coefficients computed in Step [5]. Let Cu denote the associated cubic curve:

(5.35)

8. Make a change of coordinates to put Cu into standard minimal Weierstrass form with the point P1 = [1, 0, 0] the point at infinity, . Write the resulting equation as

(5.36)

with , and let denote the images of under this change of coordinates (so in particular, ). Let c4(u), c6(u), and be the usual quantities in Silverman (2000) associated to the equation (5.36).

9. Check if the points are independent. If they are, return to Step [2] or [3]. Otherwise compute a relation of dependence

(5.37)

set

(5.38)

and continue with the next step.

10. Compute

(5.39)

If , go to Step [2] or [3]. Otherwise compute an inverse . Then

(5.40)

and the ECDLP is solved.

As can be seen, the basic idea in the above algorithm is that we first choose points in and lift them to points having integer coordinates, then we choose an elliptic curve that goes through the points , and finally check if the points are dependent. If they are, the ECDLP is almost solved. Thus, the goal of the xedni calculus is to find an instance where an elliptic curve has smaller than expected rank. Unfortunately, a set of points as constructed above will usually be independent. So, it will not work. To make it work, a congruence method, due to Mestre, is used in reverse to produce the lifted curve E having smaller than expected rank.1 Again unfortunately, Mestre’s Method is based on some deep ideas and unproved conjectures in analytic number theory and arithmetic algebraic geometry, it is not possible for us at present to give even a rough estimate of the algorithm’s running time. So, we know virtually nothing about the complexity of the xedni calculus. We also do not know if the xedni calculus will be practically useful; it may be completely useless from a practical point of view. Much needs to be done before we will have a better understanding of the xedni calculus.

The index calculus is probabilistic, subexponential-time algorithm applicable for both the Integer Factorization Problem (IFP) and the finite field Discrete Logarithm Problem (DLP). However, there is no known subexponential-time algorithm for the Elliptic Curve Discrete Logarithm Problem (ECDLP); the index calculus will not work for the ECDLP. The xedni calculus, on the other hand, is applicable to ECDLP (it is in fact also applicable to IFP and DLP), but unfortunately its complexity is essentially unknown. From a computability point of view, xedni calculus is applicable to IFP, DLP, and ECDLP, but from a complexity point of view, the xedni calculus may turn out to be useless (i.e., not at all practical). As for quantum algorithms, we now know that IFP, DLP, and ECDLP can all be solved in polynomial-time if a quantum computer is available for use. However, the problem with quantum algorithms is that a practical quantum computer is out of reach in today’s technology. We summarize various algorithms for IFP, DLP, and ECDLP in Table 5.1.

Table 5.1 Algorithms for IFP, DLP, and ECDLP

IFP	DLP	ECDLP
Trial divisions	Baby-step Giant-step	Baby-step Giant-step
Pollard’s Method	Pollard’s Methods	Pollard’s Mmethods
CFRAC/MPQS	Index calculus
NFS	NFS
Xedni calculus	Xedni calculus	Xedni calculus
Quantum algorithms	Quantum algorithms	Quantum algorithms

Finally, we conclude that we do have algorithms to solve the IFP, DLP, and ECDLP; the only problem is that we do not have an efficient algorithm, nor has any one proved that such an efficient algorithm exists. From a computational complexity point of view, a -type problem is easy to solve, whereas an -type problem is easy to verify [7], so the IFP, DLP, and ECDLP are clearly in . For example, it might be difficult (indeed, it is difficult at present) to factor a large integer, but it is easy to verify whether or not a given factorization is correct. If , then two types of the problems are the same, the factorization is difficult only because no one has yet been clever enough to find an easy/efficient algorithm (it may turn out that the integer factorization problem is indeed -hard, regardless of the cleverness of the human beings). Whether or not is one of the biggest open problems in both mathematics and computer science, and it is listed in the first of the seven Millennium Prize Problems by the Clay Mathematics Institute in Boston of May 24 2000 [6]. The struggle continues and more research needs to be done before we can say anything about whether or not !

Problems for Section 5.5

1. As Shank’s Baby-step Giant-step Method works for arbitrary groups, it can be extended, of course, to elliptic curve groups.

1. Develop an elliptic curve analog of Shank’s algorithm to solve the ECDLP.

2. Use the analog algorithm to solve the following ECDLP, that is, to find k such that

where , P = (0, 1) and Q = (30, 40).

2. Poland’s and Methods for IFP/DLP can also be extended to ECDLP.

1. Develop an elliptic curve analog of Poland algorithm to solve the ECDLP.

2. Use the analog algorithm to solve the following ECDLP: Find k such that

where , P = (0, 1) and Q = (413, 959).

3. (Extend the Silver–Pohlig–Hellman Method)

1. Develop an elliptic curve analog of Silver-Pohlig-Hellman method for ECDLP.

2. Use this analog method to solve the following ECDLP: Find k such that

where , P = (60, 19) and Q = (277, 239).

4. In 1993, Menezes, Okamota, and Vanstone developed an algorithm for ECDLP over with pm prime power. Give a description and complexity analysis of this algorithm.

5. Let be the elliptic curve E over with p prime, where E is defined by

1. Let with are two points on E. Find the addition formula for computing P + Q.

2. Let with . Find the addition formula for computing 2P.

3. Let be as follows:

Find all the points, , including the point at infinity, on the E.

4. Let P = (7, 20) and Q = (17, 14) be in defined above, find P + Q and 2P.

5. Let Q = (13, 11) and P = (0, 2) such that . Find , the discrete logarithm over .

6. Let the elliptic curve be as follows:

with order 152. A point P = (97, 26) with order 19 is given. Let also Q = (43, 4) such that

Find , the discrete logarithm over .

7. Let the elliptic curve be as follows:

with order 43. Find the ECDLP

where P = (0, 16) and Q = (42, 32).

8. Let the elliptic curve be as follows:

Find the ECDLP

in

in the subgroup of order 53 generated by .

9. In November 1997, Certicom, a computer security company in Waterloo, Canada (see the official webpage:

http://www.certicom.com/index.php?action=ecc,ecc_challenge) introduced the Elliptic Curve Cryptosystem (ECC) Challenge. These problems aim at increasing industry understanding and appreciation of the difficulty of ECDLP and encouraging and stimulating further research in the security analysis of ECC. The challenge is to compute the ECC private keys from the given list of ECC public keys and associated system parameters. This is the type of problem facing an adversary who wishes to attack ECC. These problems are defined on curves either over or over with p prime (see Table 5.2 and Table 5.3). Also there are three levels of difficulty associated with the curves: Exercise level (with bits less than 109), rather easy level (with bits 109–131), and very hard level (with bits 163–359). Readers who are interested in solving real-world ECDLP problems are suggested to try to solve the problems listed in Table 5.2 and Table 5.3, particularly those with the question marks “?” as they are still open.

10. In ECCp-109, given

show that the following value of k

is the correct value satisfying

11. In ECCp-131, given

find the correct value of k such that

Table 5.2 Elliptic curves over

Table 5.3 Elliptic curves over

5.6 Bibliographic Notes and Further Reading

In this chapter, we presented some important modern algorithms for the Discrete Logarithm Problem (DLP) and the Elliptic Curve Discrete Logarithm Problem (ECDLP).

For general references on DLP and methods for solving DLP, it is suggested that readers consult: [8–26].

The Baby-step and Giant-step Method for DLP was originally proposed by Shanks in 1971 [3]. Pohlig–Hellman method of DLP was proposed in [5]. The and Methods were proposed by Pollard in [4].

The currently most powerful method, the index calculus, for DLP is discussed in many references such as [1,2, 27,28]. Generally speaking, the index calculus belongs to a wide range of methods, such as the Continued FRACtion Method (CFRAC), Quadratic Sieve (QS), and Number Field Sieve (NFS). As far as Number Field Sieve is concerned, there is an analog method, called Function Field Sieve, based on the algebraic function field which is just an analog of the number field. FFS, just the as NFS, can be used for solving both IFP and DLP. For more information on FFS, see [29,30].

The ECDLP and methods for ECDLP are discussed in, for example, [31–43]. In particular, the xedni calculus for ECDLP was proposed in [44] and analyzed in [45].

References

1. L. M. Adleman, “A Subexponential Algorithmic for the Discrete Logarithm Problem with Applications to Cryptography”, Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, 1979, pp. 55–60.

2. D. M. Gordon, “Discrete Logarithms in GF(p) using the Number Field Sieve”, SIAM Journal on Discrete Mathematics, 6, 1, 1993, pp. 124–138.

3. D. Shanks. “Class Number, A theory of Factorization and Genera”. In: Proceedings of Symposium of Pure Mathematics 20, AMS, Providence, R.I., 1971, pp. 415–440.

4. J. M. Pollard, “Monte Carlo Methods for Index Computation ”, Mathematics of Computation, 32, 1980, pp. 918–924.

5. S. C. Pohlig and M. Hellman, “An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance”, IEEE Transactions on Information Theory, 24, 1978, pp. 106–110.

6. S. Cook, “The P versus NP Problem”, The Millennium Prize Problems. Edited by J. Carlson, A. Jaffe, and A. Wiles, Clay Mathematical Institute and American Mathematical Institute, 2006, pp. 87–104.

7. M. R. Gary and D. S. Johnson, Computers and Intractability – A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.

8. H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, Springer-Verlag, 1993.

9. H. Cohen and G. Frey, Handbook of Elliptic and Hyperelliptic Curve Cryptography, CRC Press, 2006.

10. R. Crandall and C. Pomerance, Prime Numbers – A Computational Perspective, 2nd Edition, Springer-Verlag, 2005.

11. T. Hayashi, N. Shinohara, L. Wang, et al., “Solving a 676-Bit Discrete Logarithm Problem in GF(36n)”, Public Key Cryptography – PKC 2010, Lecture Notes in Computer Science 6056, Springer, 2010, pp. 351–367.

12. T. ElGamal, “A Public Key Cryptosystem and a Signature Scheme based on Discrete Logarithms”, IEEE Transactions on Information Theory, 31, 1985, pp. 496–472.

13. N. Koblitz, A Course in Number Theory and Cryptography, 2nd Edition, Graduate Texts in Mathematics 114, Springer-Verlag, 1994.

14. N. Koblitz, Algebraic Aspects of Cryptography, Algorithms and Computation in Mathematics 3, Springer, 1998.

15. K. S. McCurley, “The Discrete Logarithm Problem”, Cryptology and Computational Number Theory. Edited by C. Pomerance, Proceedings of Symposia in Applied Mathematics 42, American Mathematics Society, 1990, pp. 49–74.

16. K. S. McCurley, “Odds and Ends from Cryptology and Computational Number Theory”, Cryptology and Computational Number Theory. Edited by C. Pomerance, Proceedings of Symposia in Applied Mathematics 42, American Mathematics Society, 1990, pp. 49–74.

17. A. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptosystems, CRC Press, 1996.

18. A. M. Odlyzko, “Discrete Logarithms in Finite Fields and their Cryptographic Significance”, Advances in Cryptography, EUROCRYPT ’84, Proceedings, Lecture Notes in Computer Science 209, Springer, 1984, pp. 225–314.

19. A. M. Odlyzko, “Discrete Logarithms: the Past and the future”, Design, Codes, and Cryptography, 19, (2000), pp. 129–145.

20. C. Pomerance, “Elementary Thoughts on Discrete Logarithms”, Algorithmic Number Theory. Edited by J. P. Buhler and P. Stevenhagen, Cambridge University Press, 2008, pp. 385–395.

21. H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhäuser, Boston, 1990.

22. O. Schirokauere, “The Impact of the Number Field Sieve on the Discrete Logarithm Problem in Finite Fields”, Algorithmic Number Theory. Edited by J. P. Buhler and P. Stevenhagen, Cambridge University Press, 2008, pp. 421–446.

23. V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005.

24. S. S. Wagstaff, Jr., Cryptanalysis of Number Theoretic Ciphers, Chapman & Hall/CRC Press, 2002.

25. S. Y. Yan, “Computing Prime Factorization and Discrete Logarithms: From Index Calculus to Xedni Calculus”, International Journal of Computer Mathematics, 80, 5, 2003, pp. 573–590.

26. S. Y. Yan, Primality Testing and Integer Factorization in Public-Key Cryptography, Advances in Information Security 11, 2nd Edition, Springer, 2009.

27. D. M. Gordon and K. S. McCurley, “Massively Parallel Computation of Discrete Logarithms”, Advances in Cryptology – Crypto ’92, Lecture Notes in Computer Science 740, Springer, 1992, pp. 312–323.

28. O. Schirokauer, D. Weber and T. Denny, “Discrete Logarithms: The Effectiveness of the Index Calculus Method”, Algorithmic Number Theory (ANTS-II), Lecture Notes in Computer Science 1122, Springer, 1996, pp. 337–362.

29. L. M. Adleman, “The Function Field Sieve”, Algorithmic Number Theory (ANTS-I), Lecture Notes in Computer Science 877, Springer, 1994, pp. 108–121.

30. L. M. Adleman, “Function Field Sieve Method for Discrete Logarithms over Finite Fields”, AInformation and Computation, 151, 1999, pp. 5–16.

31. I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, Cambridge University Press, 1999.

32. I. Blake, G. Seroussi, and N. Smart, Advances in Elliptic Curves Cryptography, Cambridge University Press, 2005.

33. H. Cohen and G. Frey, Handbook of Elliptic and Hyperelliptic Curve Cryptography, CRC Press, 2006.

34. R. Crandall and C. Pomerance, Prime Numbers – A Computational Perspective, 2nd Edition, Springer, 2005.

35. D. Hankerson, A. J. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2004.

36. J. Hoffstein, J. Pipher, and J. H. Silverman, An Introduction to Mathematical Cryptography, Springer, 2008.

37. D. Johnson, A. Menezes, and S. Vanstone, “The Elliptic Curve Digital Signatures Algorithm (ECDSA)”, International Journal of Information Security, 1, 1, 2001, pp. 36–63.

38. N. Koblitz, A Course in Number Theory and Cryptography, 2nd Edition, Graduate Texts in Mathematics 114, Springer, 1994.

39. N. Koblitz, Algebraic Aspects of Cryptography, Algorithms and Computation in Mathematics 3, Springer, 1998.

40. A. Menezes, T. Okamoto, and S. A. Vanstone, “Reducing Elliptic Curve Logarithms in a Finite Field”, IEEE Transactions on Information Theory, 39, 5, 1993, pp. 1639–1646.

41. J. H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, 2nd Edition, Springer, 2010.

42. J. H. Silverman and J. Suzuki, “Elliptic Curve Discrete Logarithms and the Index Calculus”, Advances in Cryptology – ASIACRYPT ’98, Lecture Notes in Computer Science 1514, Springer, 1998, pp. 110–125.

43. L. Washington, Elliptic Curves: Number Theory and Cryptography, 2nd Edition, Chapman & Hall/CRC, 2008.

44. J. H. Silverman, “The Xedni Calculus and the Elliptic Curve Discrete Logarithm Problem”, Designs, Codes and Cryptography, 20, 2000, pp. 5-40.

45. M. J. Jacobson, N. Koblitz, J. H. Silverman, et al. “Analysis of the Xedni Calculus Attack”, Designs, Codes and Cryptography, 20, 2000, pp. 41-64.

1 Mestre’s original method is to produce elliptic curves of large rank.