Table of Contents

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. 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.

Promotional Information

This introductory book emphasises algorithms and applications, such as cryptography and error correcting codes.

About the Author

Victor Shoup is Associate Professor at The Courant Institute of Mathematical Sciences at New York University.

Reviews

"This is an outstanding and well-written book whose aim is to introduce the reader to a broad range of material -- ranging from basic to relatively advanced -- without requiring any prior knowledge on the part of the reader other than calculus and mathematical maturity. That the book succeeds at this goal is quite an accomplishment! ...this book is a must-read for anyone interested in computational number theory or algebra and especially applications of the latter to cryptography. I would not hesitate, though, to recommend this book even to students 'only' interested in the algebra itself (and not the computational aspects thereof); especially for computer science majors, this book is one of the best available introductions to that subject." SIGACT News As computer science students have very likely not previously mastered probability theory, linear algebra, or basic abstract algebra, Shoup packages crash courses in each. Despite taking time for so many basics, Shoup climaxes with careful treatment of the late-breaking, ingenious, polynomial-time deterministic primality test of Agrawal, Kayal, and Saxena. Apart from number theory, one could easily build a fine discrete mathematics course on this book. Highly recommended. Choice