You are here

A Computational Introduction to Number Theory and Algebra

Victor Shoup
Publisher: 
Cambridge University Press
Publication Date: 
2009
Number of Pages: 
580
Format: 
Hardcover
Edition: 
2
Price: 
70.00
ISBN: 
9780521516440
Category: 
Textbook
[Reviewed by
Felipe Zaldivar
, on
06/4/2009
]

The last three or four decades have seen an interesting array of applications of algebra and number theory to computer science and related areas, from securing the interchange of information (public key cryptography) to error-correcting codes (widely used in the storage, retrieval and transmission of information). Conversely, the increasing capacity of computers has given rise to a vast area of algebra (including number theory and algebraic geometry) that emphasizes the algorithmic aspects of these branches of mathematics that somehow were at best latent.

The book under review, now in its Second Edition, weaves together both aspects of algebra and number theory summarized above, balancing the exposition between the purely theoretical developments and the straight-forward applications to cryptography and coding theory, including algorithms and pseudo-codes that could be easily implemented by the interested reader. For example, the first four chapters, devoted to elementary number theory, divisibility, unique factorization of integers, congruences, Euler’s and Fermat’s theorem, Euclid’s algorithm for the greatest common divisor of two integers, allow the author to discuss computational aspects of these topics, e.g., How fast are the corresponding algorithms? What is the running time of a program implementing these algorithms?

A whole chapter is dedicated to introducing the necessary elements for the analysis of some of these algorithms; it could be useful for the reader not acquainted with the language and practice of computing with large integers. This part of the book ends with the now familiar application to RSA public key cryptosystem and an application of the Chinese remainder theorem to an example of an error-correcting code analog to the Reed-Solomon code.

Having introduced the standard notations for comparing the growth of real-valued functions to discuss the running time of algorithms, the author can use them to study the question of how many prime numbers are there, with certain conditions, for example proving Chebyshev’s theorem on the distribution of primes. The author also formulates, with no proofs, the prime number theorem and Dirichlet’s theorem on primes in an arithmetic progression, introduces the Riemann zeta function, and discusses some famous conjectures in analytic number theory.

The second part of the book is an introduction to the elements of abstract algebra, from abelian groups (up to the proof of the structure theorem for finite abelian groups), commutative rings (ideals, quotient rings, homomorphisms, including as an example the structure of group of units of the ring of integers modulo n, to be used later in the Diffie-Hellman protocol), algebras over a commutative ring, the field of fractions of an integral domain, unique factorization domains, field extensions, finite fields and elementary function fields.

All these theoretical aspects of algebra are then studied from an algorithmic point of view, starting with polynomial algebra, emphasizing the similarities between the ring of rational integers and the ring of polynomials with coefficients in a given field, with many of the algorithms for polynomials being the corresponding analogs for the algorithms for integers and with some applications, such as polynomial interpolation with errors, the Fast Fourier Transform, and Reed-Solomon codes. Two chapters are devoted to finding generators for the group of units modulo p and computing discrete logarithms, with applications such as the Diffie-Hellman key-exchange, which is the algorithm used, for example, in the ssh protocol.

A third part of the book is devoted to primality testing, especially for its application to cryptography, and since probabilistic primality testing is such an efficient algorithm, there are three chapters devoted to introduce the elements of probability theory that are immediately applied to probability algorithms able to generate random numbers and to primality testing, e.g, the Miller-Rabin test. The book’s last chapter is devoted to the celebrated Agrawal, Kayal, and Saxena deterministic algorithm that, in polynomial time, decides whether a given integer is prime.

This is a well-written book that balances theory and applications with elegance without sacrificing formality. The book is easy to read and is self-contained although not elementary. It could be used as a textbook selecting the topics that are to be covered in the course, or for self-study by the interested student.

The author has put a free PDF copy of the Second Edition to his book on his site where you could also find errata lists for the Second and First editions.


See also our review of the first edition.


Felipe Zaldivar is Professor of Mathematics at the Universidad Autonoma Metropolitana-I, in Mexico City. His e-mail address is fzc@oso.izt.uam.mx.

 

Preface; Preliminaries; 1. Basic properties of the integers; 2. Congruences; 3. Computing with large integers; 4. Euclid’s algorithm; 5. The distribution of primes; 6. Abelian groups; 7. Rings; 8. Finite and discrete probability distributions; 9. Probabilistic algorithms; 10. Probabilistic primality testing; 11. Finding generators and discrete logarithms in Z*p; 12. Quadratic reciprocity and computing modular square roots; 13. Modules and vector spaces; 14. Matrices; 15. Subexponential-time discrete logarithms and factoring; 16. More rings; 17. Polynomial arithmetic and applications; 18. Linearly generated sequences and applications; 19. Finite fields; 20. Algorithms for finite fields; 21. Deterministic primality testing; Appendix: Some useful facts; Bibliography; Index of notation; Index.