Elliptic Curves: Number Theory and Cryptography (Discrete Mathematics and Its Applications)

Rating:
Summary: Excellent
Review: Anyone who writes a book on elliptic curves will never do a bad job, for these objects are so beautiful that it would be a sacrilege to do otherwise. Those who study elliptic curves fall under their spell, not only because of their beauty, but also because of their many applications: the spinning top in mechanics, cryptography, exactly solved models in statistical mechanics, precession of the Mercury perihelion in general relativity, the proof of Fermat's Last (Wiles) Theorem, control theory, and string theory, to name a few. This book is an excellent treatment of ECs and would be good for a graduate student starting out in the field. The author gives many concrete examples of the main theorems, and helpful exercises are found at the end of each chapter.

The author begins the book with two neat problems that motivate well the subject of elliptic curves: the pyramid of cannonballs and the right triangle problem, i.e. which integers can occur as areas of right triangles with integer sides? He then immediately begins the elementary theory of ECs in chapter 2. The treatment is pretty standard, although he proves Pascal's and Pappus's theorems using the associativity of the group operation on ECs, which is not usually done in books on ECs. Also somewhat non-standard this early in the game is the discussion of reduction of ECs modulo various primes, and the subsequent definitions of additive, split multiplicative, and non-split multiplicative reduction.

The study of torsion points is done in chapter 3 with the Weil pairing on the n-torsion of an EC taking center stage. A fairly short chapter, the author delays the proof of the properties of the Weil pairing until chapter 11, where it is done with divisors.

Chapter 4 deals with elliptic curves over finite fields, and is one of the most important in the book from the standpoint of cryptographic applications of ECs. Hasse's theorem, giving the bounds for the group of points on an EC over a finite field, is proven in detail. The Frobenius endomorphism is introduced, and a proof of Schoof's algorithm for computing the number of points on ECs over a finite field is given a detailed treatment. There are many symbolic computational software packages in both the open and commerical realm which will do the counting straightforwardly, and anyone interested in cryptography will need to be familiar with some of these. Supersingular curves in characteristic p are introduced, and the author gives a good discussion of the reason why they are named as such.

The discrete logarithm problem, a topic also very important for cryptographic applications, is discussed in chapter 5. The chapter beings with the index calculus, and, recognizing that it does not apply to general groups, the Pohlig-Hellman, baby step-giant step method, and Pollards rho and lambda methods are discussed in details. The author then shows that for supersingular and "anomalous" curves, that the discrete logarithm problem can be reduced to an easier discrete logarithm problem. Along the way, two important concepts are introduced: the p-adic valuation, and the Tate-Lichtenbaum pairing, the latter of which is related to the Weil pairing, but applies to situations where the Weil pairing does not.

Elliptic curve cryptography is then discussed in chapter 6, and the treatment is fairly thorough. The author shows to what extent the Decision Diffie-Hellman problem can be solved using the Weil pairing. He also shows how to represent a message on an elliptic curve, satisfying early on any reader's curiosity on just how this is done. The El Gamal and ECDSA are compared in terms of their computational efficiency. An EC generalization of RSA is also discussed in some detail, along with a cryptosystem based on the Weil pairing. Chapter 7 then gives other applications of ECs, such as factoring and primality testing.

Chapter 8 marks the beginning of the "heavy artillery" in the theory of ECs, for here the author begins the discussion of elliptic curves over the rational numbers, which can be viewed as an example of Diophantine geometry. The famous Mordell-Weil theorem is proved, and as a sign that one is definitely in the arena of modern mathematics, the proof is given in terms of Galois cohomology, which is an abstraction of the Fermat method of descent. The reader gets a taste of height functions, and via some good examples, gets insight into why the rank of the EC is so difficult to compute. A neat example is given of a nontrivial Shafarevich-Tate group.

I did not read the chapters 9, 10, or 11 on ECs over the complex numbers, complex multiplication, and divisors, so I will omit their review. Chapter 12 introduces the famous zeta functions, and their use in obtaining arithmetic information about an EC. Zeta functions motivate the definition of an L-function of an EC, these being tremendously important in modern developments in the theory of ECs, such as the Swinnerton-Dyer and Birch conjecture, the latter of which is motivated rather nicely in this chapter.

The last chapter of the book is an excellent introduction to the proof of Fermat's Last Theorem. Considering the level of the book, the author captures very well the essential ideas. Readers will be well prepared, after studying more algebraic number theory and the theory of Galois representations (which the author only skims in the book), to tackle the full proof if so desired.