You are here

A Course in Computational Algebraic Number Theory

Henri Cohen
Publication Date: 
Number of Pages: 
Graduate Texts in Mathematics
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Russel Jay Hendel
, on

This book is intended to provide material for a three-semester sequence, introductory, graduate course in computational algebraic number theory. Chapters 1–6 could also be used as the text for a senior-level two semester undergraduate course. The book is self contained but should follow an introductory number theory course with standard texts such as Hardy-Wright or Borevich-Shafarevich.

The book is excellent. Its goals are to (A) provide a broad overview of computational number theory and (B) to emphasize and provide help in the implementation phase of algorithms. Regarding (A), the book is about computational number theory, and consequently the more analytic aspects of the theory — for example, modular forms or L functions — are not extensively dealt with and results are sometimes stated without proofs (the book however does have sub-sections treating Zeta functions of varieties, L functions of elliptic curves, and the j function). Regarding (B), the author points out that of the four major phases in the birth cycle of an algorithm — algorithm definition, mathematical analysis, complexity and practical aspects of implementation — the practical aspects are the most ignored and therefore in most need of attention. The book in fact presents 150 tested PARI algorithms covering all aspects of the subject.

The book has 75 sections, making it suitable for a three-semester sequence. There are numerous exercises at all levels of complexity and challenge (though unlike in, say, Knuth, the exercises are not labeled, so the student does not know if they are doing a hard, easy, implementation or research exercise). The author also provides an ftp site where one can obtain a regularly updated errata file. The bibliography is quite comprehensive and therefore has intrinsic value in its own right.

The book has an amazing attention to detail. For example, although the book's algorithms are written in PARI, Appendix A provides copious detail, including ftp sites and contact information, for a dozen current packages, several of which are free. That would be sufficient for excellence in any text, but the author goes a step further and provides exercises on writing one's own computational packages. For example, exercise section 1.8, problems #1, #2, #3 are

(#1) Write a multiprecision package.

(#2) Improve your package by adding a squaring operation that operates faster than multiplication.

(#3) Improve your package further by writing an algorithm that computes v2(x) (the highest power of 2 dividing a 32-bit integer x) based on a lookup table with 37 values. Show that 37 is the smallest integer with this property and find a corresponding algorithm for 64-bit integers.

The book's major energies are devoted to the current hot topics in computational number theory — elliptic curves, Hermite normal forms, sub-exponential algorithms, number field sieves, factoring and primality testing, LLL algorithms, and the bread-and-butter number field computations including computations of regulators, fundamental units and class numbers.

The first six chapters of the book are an introduction while the last four chapters deal with current topics. The first six chapters present basic algorithms in: elementary number theory (e.g. the Euclidean algorithm, Chapter 1), linear algebra (e.g. the LLL algorithm, Chapter 2), polynomial factorization (Chapter 3), Hermite Normal form representation of modules and ideals, Chapter 4) and number field computations (class groups and regulators, Chapters 5 and 6). The author correctly provides separate chapters for Quadratic fields vs. general number fields. In Appendix B, the author provides classical tables of class numbers and units for complex and real Quadratic and Cubic fields as well as a table of elliptic curves.

As mentioned earlier, the last four chapters bring the student to the frontiers of the field, covering elliptic curves, modern primality testing and modern factoring methods. The last chapter involves complex algorithms which the author recommends for "potential three month student projects in writing algorithms."

My only problem with the book, as mentioned earlier, is the lack of "grades" on exercises — perhaps a fix for a future edition.

I particularly like the author's sense of humor, something one does not find in advanced texts. For example:

  1. pre-1960 methods for factoring are called the dark ages (Chapter 8);
  2. Shank's incredible identity, exercise #8 in section 4.10. Shank's identity is

    (5) + (22+2(5)) = (11+2(29)) + (16-2(29)+2(55-10(99)))
  3. the amusing fact that exp(π(163)) is almost exactly an integer.

Russell Jay Hendel holds a PhD. in theoretical mathematics and an Associateship from the Society of Actuaries. He teaches at Towson University. His interests include discrete number theory, applications of technology to education, problem writing, actuarial science and the interaction between mathematics, art and poetry. 

The table of contents is not available.