Suggestions for Further Reading

The integer factorization problem is one of the oldest computational problems. Though the exact notion of computational complexity took shape only after the advent of computers, the apparent difficulty of solving the factorization problem has been noticed centuries ago. Crandall and Pomerance [69] call it the fundamental computational problem of arithmetic. Numerous books and articles provide discussions on this subject at varying levels of coverage. Crandall and Pomerance [69] is perhaps the most extensive in this regard. The reader can also take a look at Bressoud’s (much simpler) book [36] or the (compact, yet reasonably detailed) Chapter 10 of Henri Cohen’s book [56]. The articles by Lenstra et al. [164] and by Montgomery [211] are also worth reading.

John M. Pollard has his name attached to three modern inventions in the arena of integer factorization. In [238, 239], he introduces the rho and p – 1 methods. (Later he has been part of the team that has designed the number-field sieve factoring algorithm.) Williams’ p + 1-method appears in 1982 in [305].

The continued fraction method (CFRAC) is apparently the first known subexponential-time integer factoring algorithm. It is based on the work of Lehmer and Powers [162] and first appears in the currently used form in Morrison and Brillhart’s paper [213]. CFRAC happens to be the most widely used integer factoring algorithm used during late 1970s and early 1980s.

The quadratic sieve method, invented by Carl Pomerance [241] in 1984, supersedes the CFRAC method. The multiple-polynomial QSM appears in Silverman [279]. Hendrik Lenstra’s elliptic curve method [174] is proposed almost concurrently as the QSM. Nowadays, the QSM and the ECM are the most commonly used factoring methods. Reyneri’s cubic sieve method is described in Lenstra and Lenstra [165].

The theoretically superior number field sieve method follows from Pollard’s factoring method using cubic integers [240]. The initial proposal for the NFS method is that of the simple NFS and appears in Lenstra et al. [167]. It is later modified to the general NFS method in Buhler et al. [41]. Lenstra and Lenstra [165] is a compilation of papers on the NFS method. Though the NFS method is the asymptotically fastest factoring method, its fairly complicated implementation makes the algorithm superior to QSM or ECM, only when the bit size of the integer to be factored is reasonably large.

Shamir’s factoring engine TWINKLE is proposed in [269]. A. K. Lenstra and Shamir analyse and optimize its design in [168]. Shamir and Tromer [270] have proposed a device called TWIRL (The Weizmann Institute Relation Locator) that is geared to the NFS factoring method. It is estimated that a TWIRL implementation costing US$10K can complete the sieving for a 512-bit RSA modulus in less than 10 minutes, whereas one that does the same for a 1024-bit RSA modulus costs US$10–50M and takes a time of one year. Lenstra et al. [163] provide a more detailed analysis of these estimates. See Lenstra et al. [169] to know about Bernstein’s factorization circuit which is another implementation of the NFS factoring method.

The (finite field) discrete logarithm problem also invoked much research in the last few decades. The older square-root methods are described well in the book [191] by Menezes. Donald Knuth attributes the baby-step–giant-step method to Daniel Shanks. See Stein and Teske [290] for various optimizations of the baby-step–giant-step method. Pollard’s rho method is an adaptation of the same method for integer factorization. See Pohlig and Hellman [234] for the Pohlig–Hellman method.

The first idea of the index calculus method appears in Western and Miller [302]. Coppersmith et al. [59] describe three variants of the index calculus method: the linear sieve method, the residue list sieve method and the Gaussian integer method. The same paper also proposes the cubic sieve method (CSM). LaMacchia and Odlyzko [158] describe an implementation of the linear sieve and the Gaussian integer methods. Das and Veni Madhavan [73] make an implementation study of the CSM. Also look at the survey [189] by McCurley.

Gordon [119] uses number field sieves for computing discrete logarithms over prime fields. Weber et al. [261, 299, 300, 301] have implemented and proved the practicality of the number field sieve method. Also see Schirokauer’s paper [260].

Odlyzko [225] surveys the algorithms for computing discrete logs in the fields . The best algorithm for these fields is Coppersmith’s algorithm [57]. No analog of this algorithm is known for prime fields. Gordon and McCurley [120] use Coppersmith’s algorithm for the computation of discrete logarithms in and .

The article [226] by Odlyzko and the one [242] by Pomerance are two recent surveys on the finite field discrete logarithm problem. Also see Buchmann and Weber [40].

The elliptic curve discrete logarithm problem seems to be a very difficult computational problem. A direct adaptation of the index calculus method is expected to lead to a running time worse than that of brute-force search (Silverman and Suzuki [278] and Blake et al. [24].) Menezes et al. [193] reduce the problem of computing discrete logs in an elliptic curve over to computing discrete logs in the field for some k. For supersingular elliptic curves, this k can be chosen to be small. For a general curve, the MOV reduction takes exponential time (Balasubramanian and Koblitz [16]). The SmartASS method is due to Smart [282], Satoh and Araki [257] and Semaev [265]. Joseph H. Silverman proposes the xedni calculus method in [277]. This method has been experimentally and heuristically shown to be impractical by Jacobson et al. [139].

Adleman et al. [2] propose the first subexponential algorithm for the hyperelliptic curve discrete log problem. This algorithm is applicable for curves of high genus over prime fields. The analysis of its running time is based on certain heuristic assumptions. Enge [86] provides a subexponential algorithm which has a rigorously provable running time and which works for curves over any arbitrary field . Again, the algorithm demands curves of high genus. An implementation of the Adleman–DeMarrais–Huang algorithm is given by Gaudry [105]. Also see Enge and Gaudry [87].

Gaudry et al. [107] propose a Weil-descent attack for the hyperelliptic curve discrete log problem. This is modified in Galbraith [100] and Galbraith et al. [101].

Coppersmith et al. [59] describe sparse system solvers. LaMacchia and Odlyzko [159] implement these methods. For further details, see Montgomery [212], Coppersmith [58], Wiedemann [303], and Yang and Brent [306].

That public-key cryptosystems can be based on the subset-sum problem (or the knapsack problem) was considered at the beginning of the era of public-key cryptography. Historically the first realization of a public-key system is based along this line and is due to Merkle and Hellman [196]. But the Merkle–Hellman system and several variants of it are broken; see Shamir [266], for example. At present, most public-key systems based on the subset-sum problem are known to be insecure.

The lattice-basis reduction algorithm and the associated L³ algorithm for factoring polynomials appear in the celebrated work [166] of Lenstra, Lenstra and Lovasz. Mignotte’s book [203] also describes these topics in good details.