You are here

Elliptic Curves: Number Theory and Cryptography

Lawrence C. Washington
Chapman & Hall/CRC
Publication Date: 
Number of Pages: 
Discrete Mathematics and Its Applications 24
[Reviewed by
Robert Talbert
, on

The subject of elliptic curves is both well-known and rather mysterious. Most people who have a sense of recent developments in mathematics know that elliptic curves had something to do with Andrew Wiles' proof of Fermat's Last Theorem and that elliptic curves are somehow used to power sophisticated cryptographic systems. But here the typical understanding of elliptic curves stops, and questions begin. What is an elliptic curve, exactly? How can a curve do the kinds of things that elliptic curves apparently do? Lawrence Washington's book Elliptic Curves: Number Theory and Cryptography gives a comprehensive yet accessible survey of elliptic curves that will answer these kinds of questions with admirable depth and clarity.

Washington motivates the study of elliptic curves through the clever use of a simple problem: Suppose we are given a collection of cannonballs stacked in a pyramid with one ball on the top layer, four on the next layer, and so on. If the stack collapses, is it possible to rearrange the cannonballs in a flat, square array? The answer, of course, is "sometimes but not always"; the simple mathematics involved in finding out exactly when this can be accomplished gives rise quite naturally to the equation for an elliptic curve.

The first chapter is all about how this simple combinatorics problem leads to the concept of the elliptic curve and then to the methods employed in finding points on that curve. The mathematics here is engaging and yet very accessible, even to a student with only a second-year high school algebra background, with some fun algebra tricks and interesting historical notes along the way. And within the algebra we can find the beginnings of many of the more sophisticated methods that are developed later in the book, such as the use of derivatives to find locate points on an elliptic curve and just a hint of the group law for an elliptic curve. The use of elementary algebra and calculus to develop organically the concept of the elliptic curve and some of its methods, rather than simply dumping the Weierstrass equation and group properties in our laps like most treatments of the subject do, is a unique strength of this book.

The next three chapters are devoted to developing more formally the idea of the group structure of the points on an elliptic curve, starting with elliptic curves over the real numbers and then generalizing to other fields, especially finite fields. Chapter 2 does most of the heavy lifting in this area, including the most comprehensive and clear treatment of the associativity of the elliptic curve I have seen. (The fact that proving associativity takes a solid twelve pages of technical arguments ought to be a lesson unto itself for abstract algebra students: associativity is not always obvious!) Chapters 3 and 4 deal specifically with torsion points and elliptic curves over finite fields, respectively, again in a thorough and clear way.

The latter portions of the book consider elliptic curves from three different points of view. As the title of the book suggests, readers who have finished Chapters 1–4 can select material from the rest of the book to emphasize a number-theoretic approach (Chapters 8–12, 14, and 15) or a cryptographic approach (Chapters 5–7, 11, and 13). Washington also points out that an approach from the standpoint of complex analysis can be had by studying Chapters 9 and 10.

The cryptographic chapters focus on the discrete logarithm problem and the various methods contrived for solving it, followed by a comprehensive treatment of elliptic curve cryptography. Washington wisely does not restrict the treatment of cryptography to include only cryptosystems but also includes key exchange and digital signature protocols (including a nice treatment of the Digital Signature Algorithm using elliptic curves) as well as other crypto-related applications such as factoring and primality testing.

The later chapters also deal with topics such as hyperelliptic curves, a subject enjoying increasingly prominent applications in cryptography lately. These chapters are outstanding in terms of scope, detail, and clarity; for someone wishing to do a thorough study of elliptic curve cryptography, these chapters alone justify the purchase of the book.

The number theory chapters are equally detailed and quite extensive, using a treatment of elliptic curves over the rationals and over the complex numbers to develop all of the most up-to-date number-theoretic results pertaining to elliptic curves. In fact, checking some of the references in the book's extensive bibliography, students may be surprised to find many of the number-theoretic results to have been discovered just in the last 15 years. These recent results include a remarkable chapter that closes out this book: a fully-fledged sketch of Wiles' proof of Fermat's Last Theorem. I have not seen a book at this level which attempts to present the actual strategy and ideas behind Wiles' proof. For mathematicians and advanced students wishing to answer those questions about how elliptic curves could have been useful in this regard, Washington obliges. One wonders about the stir this book would have made if it were transported back in time 20 years ago.

While accessible and clearly written, the book does not pretend to be a surface-level treatment of elliptic curves for beginning undergraduates. Someone wishing to make a serious attempt at getting through even the introductory chapters will need a solid background in abstract algebra and nontrivial exposure to basic number theory. (There are appendices for number theory, group theory, and finite fields, but these are more like reviews than introductions.) Readers with that background, however, might use this book in several ways. The first four chapters by themselves would make a nice independent study or seminar course in the basics of elliptic curves that would be accessible to advanced undergraduates. The chapters on elliptic curve cryptography could be approached similarly, and readers interested only in elliptic curve cryptography might be able to skip or skim some of the more technical material in chapters 3 and 4 in order to get right to the cryptography. The number theory chapters could be sampled, if not taken in their entirety, for a very thorough second semester of number theory with some of the cryptography material sprinkled in for applications.

If this book is used for self-study, independent study, or classroom use, readers will be helped by the exercise sets at the end of the chapter and the guides on computer algebra system uses in elliptic curves given in an appendix. (Washington is to be applauded for detailing how free, open-source software such as Sage can be used for studying elliptic curves, but it would have been nice to see a few words about more popular systems such as Maple or Mathematica.) The extensive bibliography is also a great help for finding further sources of study in the subject.

This book is more like a small mathematics library than it is a single textbook, containing at least three different possible academic courses within its covers. Its style, being both thoroughly rigorous and engagingly clear, will make it a fine sourcebook for anyone wishing to demystify this important and useful subject. It deserves to be in the libraries of undergraduate institutions and interested students of mathematics everywhere.

Robert Talbert is Associate Professor of Mathematics and Computing Science at Franklin College in Franklin, Indiana. His interests include cryptography, geometry, evangelism for the Mac OS X operating system, and being at the beck and call of his wife and two daughters. He blogs on mathematics, education, and technology at Casting Out Nines and can be found on Twitter under the username RobertTalbert.

Weierstrass Equations
The Group Law
Projective Space and the Point at Infinity
Proof of Associativity
Other Equations for Elliptic Curves
The j-Invariant
Elliptic Curves in Characteristic
Singular Curves
Elliptic Curves mod n
Torsion Points
Division Polynomials
The Weil Pairing
The Frobenius Endomorphism
Determining the Group Order
A Family of Curves
Schoof's Algorithm
Supersingular Curves
The Index Calculus
General Attacks on Discrete Logs
The MOV Attack
Anomalous Curves
The Tate-Lichtenbaum Pairing
Other Attacks
The Basic Setup
Diffie-Hellman Key Exchange
Massey-Omura Encryption
ElGamal Public Key Encryption
ElGamal Digital Signatures
The Digital Signature Algorithm
A Public Key Scheme Based on Factoring
A Cryptosystem Based on the Weil Pairing
Factoring Using Elliptic Curves
Primality Testing
The Torsion Subgroup. The Lutz-Nagell Theorem
Descent and the Weak Mordell-Weil Theorem
Heights and the Mordell-Weil Theorem
The Height Pairing
Fermat's Infinite Descent
2-Selmer Groups; Shafarevich-Tate Groups
A Nontrivial Shafarevich-Tate Group
Galois Cohomology
Doubly Periodic Functions
Tori are Elliptic Curves
Elliptic Curves over C
Computing Periods
Division Polynomials
Elliptic Curves over C
Elliptic Curves over Finite Fields
Integrality of j-Invariants
A Numerical Example
Kronecker's Jugendtraum
Definitions and Examples
The Weil Pairing
The Tate-Lichtenbaum Pairing
Computation of the Pairings
Genus One Curves and Elliptic Curves
Elliptic Curves over Finite Fields
Elliptic Curves over Q
Galois Representations
Sketch of Ribet's Proof
Sketch of Wiles' s Proof
Number Theory