A Computational Introduction to Number Theory and Algebra

Victor Shoup

Digital versions PDF
Latex source No
Exercises Yes
Answers and hints Yes
License Creative Commons for the electronic version only
  • 598 pages, 21 chapters
  • Topics motivated by applications in computing and communications, particularly coding theory and cryptography
  • Published version for about $60 from Amazon
  • For more information and to download

This books does not presuppose any previous background in number theory or algebra, but it quickly moves into material beyond the usual courses in math departments because of the emphasis on algorithms and computation. The chapter titles give an idea of the unusual flavor of this book, which has a number of topics that would be suitable for a senior level “advanced topics” course following a more traditional algebra or number theory course. The author writes that the book could “be used as a textbook in a graduate or upper-division undergraduate course on (computational) number theory and algebra, perhaps geared towards computer science students.”

Although this book is published commercially by Cambridge University Press, who has the exclusive right to distribute it in print form, the publisher has granted access to a free PDF version that individuals can download, use, and print.

Table of Contents

  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
  1. Quadratic reciprocity and computing modular square roots
  2. Modules and vector spaces
  3. Matrices
  4. Subexponential-time discrete logarithms
  5. More rings
  6. Polynomial arithmetic and applications
  7. Linearly generated sequences and applications
  8. Finite fields
  9. Algorithms for finite fields
  10. Deterministic primality testing