Suggestions for Further Reading

The basic algorithmic issues discussed in Section 3.2 can be found in any text-book on data structure and algorithms. One can, for example, look at [7, 8, 61]. However, most of these elementary books do not talk about randomization and parallelization issues. We refer to [214] for a recent treatise on randomized algorithm. Also see Rabin’s papers [247, 248].

Complexity theory deals with classifying computational problems based on the known algorithms for solving them and on reduction of one problem to another. A simple introduction to complexity theory is the book [280] by Sipser. Chapter 2 of Koblitz’s book [154] is also a compact introduction to computational complexity meant for cryptographers. Also see [113].

Knuth’s book [147] is seemingly the best resource to look at for a comprehensive treatment on multiple-precision integer arithmetic. The proofs of correctness of many algorithms, that we omitted in Section 3.3, can be obtained in this book. This can be supplemented by the more advanced algorithms and important practical tips compiled in the book [56] by Cohen who designed a versatile computational number theory package known as PARI. Montgomery’s multiplication algorithm appeared in [210]. Also see Chapter 14 of Menezes et al. [194] for more algorithms and implementation issues.

Most of the important papers on primality testing [3, 4, 5, 116, 175, 204, 248, 287] have been referred in Section 3.4.1. Also see the survey [164] due to Lenstra and Lenstra. Gordon’s algorithm for generating strong primes appeared in [118]. The book [69] by Crandall and Pomerance is an interesting treatise on prime numbers, written with a computational perspective. The modular square-root Algorithm 3.16 is essentially due to Tonelli (1891). Algebraic number theory is treated from a computation perspective in Cohen [56] and Pohst and Zassenhaus [235].

Arithmetic on finite fields is discussed in many books including [179, 191]. Finite fields find recent applications in cryptography and coding theory and as such it is necessary to have efficient software and hardware implementations of finite field arithmetic. A huge number of papers have appeared in the last two decades, that talk about these implementation issues. Chapter 5 of Menezes [191] talks about optimal normal bases (Section 2.9.3 of the current book) which speeds up exponentiation in finite fields.

Factoring univariate polynomials over finite fields is a topic that has attracted a lot of research attention. Berlekamp’s Q-matrix method [21] is the first modern algorithm for this purpose. Computationally efficient versions of the algorithm discussed in Section 3.5.4 have been presented in Gathen and Shoup [104] and Kaltofen and Shoup [143]. The best-known running time for a deterministic algorithm for univariate factorization over finite fields is due to Shoup [272]. Shparlinski shows [274] that Shoup’s algorithm on a polynomial in of degree d uses O(q^1/2(log q)d^2+ε) bit operations. This is fully exponential in log q.

The book [103] by von zur Gathen and Gerhard is a detailed treatise on many topics discussed in Sections 3.2 to 3.5 of the current book. Mignotte’s book [203] and the one by [108] by Geddes et al. also have interesting coverage. Also see Chapter 1 of Das [72] for a survey of algorithms for various computational problems on finite fields.

For elliptic curve arithmetic, look at Blake et al. [24], Hankerson et al. [123] and Menezes [192]. The first polynomial-time algorithm for counting points in elliptic curves over a finite field has been proposed by Schoof. The original version of this algorithm runs in time O(log⁸ q). Later Elkies improved this running time to O(log⁶ q) for most of the elliptic curves. Further modifications due to Atkin gave rise to what we call the SEA algorithm. Schoof’s paper [264] talks about this point-counting algorithm and includes the modifications due to Elkies and Atkin. Also look at the article [85] by Elkies.

The Satoh–FGH algorithm is originally due to Satoh [256]. Fouquet et al. [94] have proposed a modification of Satoh’s algorithm to work for fields of characteristic 2. They also report large-scale implementations of the modified algorithm. Also see Fouquet et al. [95] and Skjernaa [281].

Recently, there has been lot of progress in point counting algorithms, in particular, for fields of characteristic 2. The most recent account of this can be found in Lercier and Lubicz [177]. The authors of this paper later reported implementation of their algorithm for counting points in an elliptic curve over . This computation took nearly 82 hours on a 731 MHz Alpha EV6 processor. With these new developments, the point counting problem is practically solved for fields of small characteristics. However, for prime fields the known algorithms require further enhancements in order to be useful on a wide scale.

Finding good random elliptic curves for cryptographic purposes has also been an area of active research recently. With the current status of solving the elliptic curve discrete-log problem, the strategy we mentioned in Algorithm 3.33 is quite acceptable as long as good point-counting algorithms are at our disposal (they are now). For further discussions on this topic, we refer the reader to two papers [95, 176].

The appendix in Koblitz’s book [154] is seemingly the best source for learning hyperelliptic curve arithmetic. This is also available as a CACR technical report [195]. Gaudry and Harley’s paper [106] has more on the hyperelliptic curve point-counting algorithms we discussed in Section 3.7.2. Hess et al. [126] discuss methods for computing hyperelliptic curves for cryptographic usage.

Chapter 5 of Menezes et al. [194] is devoted to the generation of pseudorandom bits and sequences. This chapter lists the statistical tests for checking the randomness of a bit sequence. It also describes two cryptographically secure pseudorandom bit generators other than the BBS generator (Algorithm 3.37). The BBS generator was originally proposed by Blum et al. [26]. Also see Chapter 3 of Knuth [147].