The early portions of this text are an interesting collage of mathematical facts that suffers from lack of cohesion. While this may suggest opportunities to skip ahead, the text as a whole can be treated that way, as each chapter stands very well on its own as an exploration of a specific topic with algorithms ready for implementation. The algorithms are presented with supporting theorems and proofs and running time analysis in big-O notation.
Shoup ably guides the reader through approaches to computing GCDs, Euclid’s algorithm, the Chinese remainder theorem, etc. Always the motivation for and basic approach to implementation is presented, often with clear ideas for improved efficiency. Speeding up computations via modular arithmetic is one approach taken.
Because number theory and algebra play such a role in computing and communications through cryptography and coding, it is natural that a large part of this work is given to practical overview of calculating key elements, such as Legendre and Jacobi symbols. This includes primality testing, finding discrete logarithms, working in finite fields and more.
A “Notes” section at the end of the chapters offers a mix of source material and suggestions for future research. This helps to round out the work as both a guide to computational mathematics and reference work.
0. Preliminaries; 1. Basic properties of the integers; 2. Congruences; 3. Computing with large integers; 4. Euclid’s algorithm; 5. The distribution of primes; 6. Finite and discrete probability distributions; 7. Probabilistic algorithms; 8. Abelian groups; 9. Rings; 10. Probabilistic primality testing; 11. Finding generators and discrete logarithms in Zp*; 12. Quadratic residues and quadratic reciprocity; 13. Computational problems related to quadratic residues; 14. Modules and vector spaces; 15. Matrices; 16. Subexponential-time discrete logarithms and factoring; 17. More rings; 18. Polynomial arithmetic and applications; 19. Linearly generated sequences and applications; 20. Finite fields; 21. Algorithms for finite fields; 22. Deterministic primality testing; Appendix: some useful facts; Bibliography; Index of notation; Index.