Algorithmic number theory. 2nd revised and extended ed.
(Algorithmische Zahlentheorie.)

*(German)*Zbl 1304.11002
Heidelberg: Springer Spektrum (ISBN 978-3-658-06539-3/pbk; 978-3-658-06540-9/ebook). viii, 314 p. (2015).

The author’s popular German textbook on computational number theory first appeared almost twenty years ago [Algorithmische Zahlentheorie. Braunschweig: Vieweg (1996; Zbl 0870.11001)]. As the reviewer of the original edition (J. Wolfart) pointed out, this monograph was the first introductory text on number theory that successfully combined the theoretical and the computational aspects of the subject, thereby reflecting the recent tendencies in number theory in a highly original manner.

The book under review is the second, revised and substantially amplified edition of this unique text, the aim of which is to provide a presentation of the basics of elementary number theory from the abstract algebraic viewpoint, on the one hand, and via the constructive, algorithmic approach on the other. As for the latter, a special feature of the book is the description of many algorithms by the interactive, multi-precision interpreter ARIBAS with PASCAL-like syntax, which was developed by the author himself. A short introduction to ARIBAS is given in an appendix, and this should enable the reader to test the concrete arithmetic algorithms effectively on her/his own personal computer, thereby deepening her/his understanding of the matter through active explorations and experiments.

Concerning the prerequisites for studying this outstanding primer on both abstract and algorithmic number theory, the basic knowledge of the elementary abstract algebra of groups, rings, and fields as well as a little familiarity with programming techniques (perhaps in PASCAL or C) should absolutely suffice for this purpose.

Compared to the first edition of the book from 1996, various communicated errors and misprints have been corrected. Moreover, and even more importantly, three new chapters have been added, and the text as a whole has been slightly revised here and there. Among the new topics taken up in the current edition are the following: 8mm

Altogether, the present second edition of the author’s textbook now comprises thirty chapters, in which the reader is led from elementary divisibility theory for integers up to the arithmetic in quadratic number fields, with particular emphasis on concrete algorithmic methods, instructive examples, and applications in cryptography. More precisely, the following chapters form the contents of the book:

1. The Peano axioms; 2. The arithmetic operations; 3. The Fibonacci numbers; 4. The Euclidean algorithm; 5. The prime decomposition; 6. The ring \(\mathbb{Z}/m\mathbb{Z}\); 7. The theorems of Fermat, Euler and Wilson; 8. The structure of the group \((\mathbb{Z}/m\mathbb{Z})^\ast\) and primitive roots of unity; 9. Pseudo-random generators; 10. The inverse of Fermat’s theorem; 11. Quadratic residues and the quadratic reciprocity law; 12. Probabilistic primality tests; 13. The Pollard Rho-method; 14. The \((p-1)\)-factorization method; 15. The RSA-cryptography method; 16. Quadratic field extensions; 17. The \((p+1)\)-primality test and Mersenne primes; 18. The \((p+1)\)-factorization method; 19. The fast Fourier transform; 20. Factorization with the quadratic sieve (new!); 21. The discrete logarithm (new!); 22. Elliptic curves; 23. Factorization using elliptic curves; 24. Quadratic number fields; 25. Lagrange’s four squares theorem; 26. Continued fractions; 27. Pell’s equation; 28. Ideal classes in quadratic number fields; 29. Factorization via the class group of an imaginary-quadratic number field; 30. The AKS-primality test (new!).

Apart from the already mentioned short introduction to the multi-precision interpreter ARIBAS, there is a rich bibliography concerning related textbooks, monographs, conference proceedings, and research articles. With regard to the new, updating chapters of the book, the list of references has been updated, too, and a few recent textbooks have been added as well.

Summing up, the unique character of this utmost lucid and inviting textbook on elementary number theory has been further augmented through the current second, revised and enlarged edition. Now as before, the guiding principle of the entire approach is the treatment of effective algorithms for factorization and primality testing, and many classical concepts and results in number theory are reconsidered from this methodological point of view.

Without any doubt, this fine textbook certainly (and finally) deserves a translation into English, which would be for the benefit of much more interested students and instructors worldwide.

The book under review is the second, revised and substantially amplified edition of this unique text, the aim of which is to provide a presentation of the basics of elementary number theory from the abstract algebraic viewpoint, on the one hand, and via the constructive, algorithmic approach on the other. As for the latter, a special feature of the book is the description of many algorithms by the interactive, multi-precision interpreter ARIBAS with PASCAL-like syntax, which was developed by the author himself. A short introduction to ARIBAS is given in an appendix, and this should enable the reader to test the concrete arithmetic algorithms effectively on her/his own personal computer, thereby deepening her/his understanding of the matter through active explorations and experiments.

Concerning the prerequisites for studying this outstanding primer on both abstract and algorithmic number theory, the basic knowledge of the elementary abstract algebra of groups, rings, and fields as well as a little familiarity with programming techniques (perhaps in PASCAL or C) should absolutely suffice for this purpose.

Compared to the first edition of the book from 1996, various communicated errors and misprints have been corrected. Moreover, and even more importantly, three new chapters have been added, and the text as a whole has been slightly revised here and there. Among the new topics taken up in the current edition are the following: 8mm

- (1)
- a modern arithmetic factorization method based on the multi-polynomial quadratic sieve (after [C. Pomerance, EUROCRYPT ‘84, Lect. Notes Comput. Sci. 209, 169–182 (1985; Zbl 0596.10006)]);
- (2)
- the discrete logarithm problem in arithmetic and cryptography, including effective algorithms in this context;
- (3)
- the deterministic AKS-primality test in polynomial running time (after [M. Agrawal et al., Ann. Math. (2) 160, No. 2, 781–793 (2004; Zbl 1071.11070)]).

Altogether, the present second edition of the author’s textbook now comprises thirty chapters, in which the reader is led from elementary divisibility theory for integers up to the arithmetic in quadratic number fields, with particular emphasis on concrete algorithmic methods, instructive examples, and applications in cryptography. More precisely, the following chapters form the contents of the book:

1. The Peano axioms; 2. The arithmetic operations; 3. The Fibonacci numbers; 4. The Euclidean algorithm; 5. The prime decomposition; 6. The ring \(\mathbb{Z}/m\mathbb{Z}\); 7. The theorems of Fermat, Euler and Wilson; 8. The structure of the group \((\mathbb{Z}/m\mathbb{Z})^\ast\) and primitive roots of unity; 9. Pseudo-random generators; 10. The inverse of Fermat’s theorem; 11. Quadratic residues and the quadratic reciprocity law; 12. Probabilistic primality tests; 13. The Pollard Rho-method; 14. The \((p-1)\)-factorization method; 15. The RSA-cryptography method; 16. Quadratic field extensions; 17. The \((p+1)\)-primality test and Mersenne primes; 18. The \((p+1)\)-factorization method; 19. The fast Fourier transform; 20. Factorization with the quadratic sieve (new!); 21. The discrete logarithm (new!); 22. Elliptic curves; 23. Factorization using elliptic curves; 24. Quadratic number fields; 25. Lagrange’s four squares theorem; 26. Continued fractions; 27. Pell’s equation; 28. Ideal classes in quadratic number fields; 29. Factorization via the class group of an imaginary-quadratic number field; 30. The AKS-primality test (new!).

Apart from the already mentioned short introduction to the multi-precision interpreter ARIBAS, there is a rich bibliography concerning related textbooks, monographs, conference proceedings, and research articles. With regard to the new, updating chapters of the book, the list of references has been updated, too, and a few recent textbooks have been added as well.

Summing up, the unique character of this utmost lucid and inviting textbook on elementary number theory has been further augmented through the current second, revised and enlarged edition. Now as before, the guiding principle of the entire approach is the treatment of effective algorithms for factorization and primality testing, and many classical concepts and results in number theory are reconsidered from this methodological point of view.

Without any doubt, this fine textbook certainly (and finally) deserves a translation into English, which would be for the benefit of much more interested students and instructors worldwide.

Reviewer: Werner Kleinert (Berlin)

##### MSC:

11-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to number theory |

11Axx | Elementary number theory |

11B39 | Fibonacci and Lucas numbers and polynomials and generalizations |

11R11 | Quadratic extensions |

11Y05 | Factorization |

11Y11 | Primality |

11Y16 | Number-theoretic algorithms; complexity |

11Y40 | Algebraic number theory computations |

11Y65 | Continued fraction calculations (number-theoretic aspects) |