A course in computational algebraic number theory.

*(English)*Zbl 0786.11071
Graduate Texts in Mathematics. 138. Berlin: Springer-Verlag. xxi, 534 p. (1993).

“A course in computational algebraic number theory” contains 148 algorithms, which were all up-to-date when the book came out. Hence, this book is the source for number theorists wishing to learn about a special method and/or implement an algorithm without studying the theory in greater detail. Among these algorithms, many are new or improved. In most cases, their analysis and their complexity are given (not the complexity of the problem, as stated in the preface) and, most importantly, valuable remarks on implementations. Here one sees the great experience of the author, the founder of the package PARI.

The book begins with a chapter devoted to the most important routines from elementary number theory. It is followed by one on algorithms from linear algebra and lattice theory. Especially important are the sections on Hermite and Smith normal forms and lattice basis reduction algorithms.

Chapter 3 treats polynomials over various fields from an algorithmic point of view. While factorization routines are outlined in great detail the reader will wonder why Cohen spared two pages to explain, why this task is polynomial time over \(\mathbb{Q}\), even though he has all prerequisites at hand.

In Chapter 4, basic arithmetic of algebraic number fields is discussed, with special attention given to the representation of algebraic numbers and ideals.

Chapter 5 contains the highly developed theory of quadratic fields, Shanks’ Baby Step Giant Step method, and recent ideas of McCurley, Atkin for speeding up the computation of the class groups in those fields. It closes with Cohen-Lenstra heuristics.

In Chapter 6 algorithms for the computation of the Galois group, an integral basis, the unit group and the class group of a general algebraic number field are presented. For the Galois group the field degree is bounded by 7. The integral basis calculations are exclusively done by the Round 2 Method. Finally, the unit and class group algorithms work only under suitable assumptions (at least GRH), without the reader learning how or from where to get those invariants unconditionally.

Chapter 7 is a nice survey on (some of) the theory of elliptic curves from an algorithmic viewpoint. It contains all important recent results and conjectures (except Wiles’).

The final three chapters contain primality testing and factoring algorithms. Nearly all important methods are described, especially the primality test of Atkin and Morain in Chapter 9 and MPQS and the number field sieve in Chapter 10.

The book concludes with two appendices, one presenting a variety of packages for number theory (Cohen’s choice), the other with tables of class numbers and units in fields of degree 2, 3 (and small absolute discriminant) and one of elliptic curves.

There are more than 500 pages, most of them being fun to read. As usual, the choice of contents is disputable in some sections, but the book itself is a nice piece of (hard) work. There is just one item where I disagree with the author. It is hard for me to imagine how to use this book as a textbook for a course. No prerequisites are stated. For most proofs, the reader is referred to a textbook. This is a little difficult in practice because of different notations. For example, the Chinese Remainder Theorem is stated in Chapter 1 without proof, a proof for a prerequisite of it (\(ab=a\cap b\) for comaximal ideals \(a\), \(b\)) is presented on page 180, and prime ideals are defined on page 182.

Besides these personal remarks, I heartily recommend this book to the computational (algebraic) number theory community. With Cohens’ words: for them, “It’s a must”.

The book begins with a chapter devoted to the most important routines from elementary number theory. It is followed by one on algorithms from linear algebra and lattice theory. Especially important are the sections on Hermite and Smith normal forms and lattice basis reduction algorithms.

Chapter 3 treats polynomials over various fields from an algorithmic point of view. While factorization routines are outlined in great detail the reader will wonder why Cohen spared two pages to explain, why this task is polynomial time over \(\mathbb{Q}\), even though he has all prerequisites at hand.

In Chapter 4, basic arithmetic of algebraic number fields is discussed, with special attention given to the representation of algebraic numbers and ideals.

Chapter 5 contains the highly developed theory of quadratic fields, Shanks’ Baby Step Giant Step method, and recent ideas of McCurley, Atkin for speeding up the computation of the class groups in those fields. It closes with Cohen-Lenstra heuristics.

In Chapter 6 algorithms for the computation of the Galois group, an integral basis, the unit group and the class group of a general algebraic number field are presented. For the Galois group the field degree is bounded by 7. The integral basis calculations are exclusively done by the Round 2 Method. Finally, the unit and class group algorithms work only under suitable assumptions (at least GRH), without the reader learning how or from where to get those invariants unconditionally.

Chapter 7 is a nice survey on (some of) the theory of elliptic curves from an algorithmic viewpoint. It contains all important recent results and conjectures (except Wiles’).

The final three chapters contain primality testing and factoring algorithms. Nearly all important methods are described, especially the primality test of Atkin and Morain in Chapter 9 and MPQS and the number field sieve in Chapter 10.

The book concludes with two appendices, one presenting a variety of packages for number theory (Cohen’s choice), the other with tables of class numbers and units in fields of degree 2, 3 (and small absolute discriminant) and one of elliptic curves.

There are more than 500 pages, most of them being fun to read. As usual, the choice of contents is disputable in some sections, but the book itself is a nice piece of (hard) work. There is just one item where I disagree with the author. It is hard for me to imagine how to use this book as a textbook for a course. No prerequisites are stated. For most proofs, the reader is referred to a textbook. This is a little difficult in practice because of different notations. For example, the Chinese Remainder Theorem is stated in Chapter 1 without proof, a proof for a prerequisite of it (\(ab=a\cap b\) for comaximal ideals \(a\), \(b\)) is presented on page 180, and prime ideals are defined on page 182.

Besides these personal remarks, I heartily recommend this book to the computational (algebraic) number theory community. With Cohens’ words: for them, “It’s a must”.

Reviewer: M.Pohst (Berlin)

##### MSC:

11Y40 | Algebraic number theory computations |

11-02 | Research exposition (monographs, survey articles) pertaining to number theory |

11Y16 | Number-theoretic algorithms; complexity |

11Y05 | Factorization |

11Y11 | Primality |

11Rxx | Algebraic number theory: global fields |