Modern Cryptography and Elliptic Curves

I spent my junior and senior years as an undergraduate very happily taking nothing but mathematics courses — four consecutive semesters of five or six math courses each, some of them graduate courses or special topics courses. And yet, despite these two years of total immersion into mathematics, I graduated, as far as I can remember, without ever having heard the phrase “elliptic curve”. This may be due to the fact that the value of these objects was not yet fully realized — this was, after all, two decades before Wiles used them to prove Fermat’s Last Theorem — but I suspect the more likely explanation is that there simply was not much in the way of textbook literature available that made this subject accessible to undergraduates.

Students today are a little better off. There are at least two textbooks (Rational Points on Elliptic Curves by Silverman and Tate, and Washington’s Elliptic Curves: Number Theory and Cryptography) that are entirely devoted to elliptic curves and are, in large measure, reasonably comprehensible to good undergraduates. In addition, there are other undergraduate-level books that spend some time discussing elliptic curves in the context of other material. Examples here include two other books (A Friendly Introduction to Number Theory and An Introduction to Mathematical Cryptography) with Silverman as author or co-author, both of which contain fairly extensive discussions, as well as briefer expositions in Bauer’s Secret History: The Story of Cryptology and An Introduction to Number Theory with Cryptography by Kraft and Washington. And now there is the book under review, which is really not quite like any of these books.

Unlike the last four books listed above, elliptic curves are not just a supporting player in this text; in fact, they may reasonably be described as its raison d’être. As the author states in the preface, the “focal point for this text is to lead students to understand the arithmetic of elliptic curves over a finite field and some applications of elliptic curves to modern cryptography.” However, unlike the first two books mentioned in the previous paragraph, elliptic curves do not appear throughout the text. The reason is that this text is intended for a much less sophisticated audience; indeed, the author has set himself the goal (about which, more later) of writing a text that should be comprehensible to a student with nothing more than a background in single-variable calculus. These minimal prerequisites require that a great deal of preliminary material be discussed before the text gets around to talking seriously about elliptic curves, so as a result this serious discussion doesn’t start until chapter 7 (although they are briefly mentioned early on, and some uses of them sketched informally).

The book begins with a nice motivational chapter, which defines elliptic curves and sketches some of their applications, specifically to Fermat’s Last Theorem, the theory of congruent numbers, and cryptography. The five chapters following this, though largely prefatory for what is to come, are of considerable interest themselves, in that they discuss material that all mathematics majors should see.

Chapter 2 begins, as does Rational Points, with a discussion of Pythagorean triples and their connection with rational points on the unit circle. A geometric method for finding such points is sketched. This discussion helps motivate a number of ideas that will pop up later in the text, including, of course, the connections between geometry and algebra of curves.

Chapters 3 and 4 introduce number theory, with an emphasis on modular arithmetic, done from a basic algebraic standpoint. (The fundamental notions of group and ring are introduced from scratch.) As we proceed, the subject of cryptography is brought up and some applications of this material to elementary cryptography (e.g., affine ciphers) is discussed. Cryptography is then developed a little more in the next chapter, which talks about public key cryptography and RSA.

The next chapter returns to abstract algebra and looks a little more deeply at that subject, including more on group theory. The fundamental theorem of abelian groups is stated without proof and applied to the study of primitive roots modulo a prime. Applications to cryptography are then provided in the form of sections on Diffie-Hellman Key Exchange and ElGamal encryption.

Chapter 7 begins with a discussion of affine and projective space and proceeds from there to examine rational points on elliptic curves and the group structure of such curves. Applications of elliptic curves to factoring and cryptography are explored in more detail in the next chapter, and following that there is an Appendix that discusses, in a largely expository way and with very few proofs, some more advanced topics in the theory, including the Birch and Swinnerton-Dyer conjecture. A little bit of complex analysis is developed as needed in this Appendix.

Exercises (unfortunately, unnumbered) are scattered throughout the book, embedded throughout the text itself rather than collected at the end of a section or chapter. Solutions to a substantial number of these exercises appear in a second Appendix.

I spoke earlier of the author’s claim that the book does not require any mathematical background beyond single-variable calculus. Over the years I have come to be very skeptical of such statements, which are often made and almost as often disregarded. But here, Shemanske is being truthful, at least literally: no technical knowledge beyond calculus is required to understand the text. But that elusive quality, “mathematical maturity”, cannot be downplayed here, and I have to wonder if a student who literally has no prior exposure to proofs will be very comfortable plunging into this material, particularly in the last third or so of the book.

Given that this book is to be used as a text, an obvious question is: for what kind of course? The author suggests that this text might serve well as (a) an attempt to entice students into taking more mathematics, or (b) as an alternative to a traditional introduction-to-proofs course. The problem with proposal (b) is that the book does not provide the extent of hand-holding that I think is necessary to introduce a student into the world of proofs. There are no extended discussions of the converse and contrapositive, what a proof by contradiction is, how to negate a statement, and so on. (Proofs by contradiction are used, of course, but without much in the way of prior discussion of what they are.) Also, the material in this book is certainly not trivial, and it is my experience is that it is hard enough to teach a truly beginning student how to do very easy proofs; getting him or her to understand facts about elliptic curves seems to add an extra level of difficulty to the mix.

As for proposal (a) above, one practical consideration is that not many universities have the resources to offer courses that are designed to entice students to take more mathematics; it is hard enough to find time and manpower just to run enough standard courses in abstract and linear algebra, analysis, geometry, combinatorics, number theory, math history, topology, etc. In addition, a student taking a course based on this book early in his or her career will likely experience considerable repetition in later courses in algebra and number theory.

One additional difficulty that is inherent in using the book in either of the ways described above is time. In a typical semester, allowing times for exams, it may not be easy to get to, or at least very far into, the “good stuff” at the end of the book, particularly if the class consists of people with no background beyond calculus.

The author also suggests that this book could be used as a text for a course in cryptography for computer-science majors who want to learn some of the mathematical underpinnings of the subject. Here, I think, Shemanske is on much firmer ground, although I think a course in cryptography for mathematics majors could also make productive use of this text, assuming a prior course in number theory was not a prerequisite. The text is somewhat less demanding than, say, the cryptography book by Hoffstein, Pipher and Silverman that was mentioned earlier, and some supplementation on the part of the instructor would be necessary: I don’t recall seeing the Hill or Viginière ciphers mentioned, for example, and there is also a dearth of information about famous historical ciphers that students find interesting, such as the Enigma cipher. A book like Secret History contains a wealth of information along these lines that an instructor could use to spice up lectures. With these caveats, I think an interesting cryptography course could be put together.

Another possible use, not explicitly advocated by the author, would be as a text for a somewhat nontraditional course in number theory, one with a heavy focus on cryptographic applications and elliptic curves. Certainly the very basic material (divisibility, congruences, modular arithmetic, etc.) of such a course is covered, and the relatively early inclusion of elliptic curves might well seem, to an instructor, to compensate for the exclusion of some traditionally standard number theory topics such as continued fractions, sums of four squares, or the law of quadratic reciprocity.

The book might also prove to be valuable to more experienced students, who already have, say, a semester of abstract algebra under their belts. These students could skip quickly over the algebra chapters, proceed through the material on number theory if necessary, and then get a nice introduction to elliptic curves. Many universities offer a second semester abstract algebra course, or perhaps a “special topics” course; this book would make an excellent text for a course of this nature.

In any event, this is a nice book to have on one’s shelf. I don’t know of any other text that offers a student as painless an introduction to the subject of elliptic curves as does this one. It is certainly the book that I would recommend to any student of mine who asked me where he or she could learn what an elliptic curve is.

Buy Now

Mark Hunacek (mhunacek@iastate.edu) teaches mathematics at Iowa State University.