Introduction to Computational Number Theory and Algebra

G22.3033-002 Spring 2006

Instructor: Victor Shoup

Mailing List

Lectures: Thursdays, 5-6:50pm, room 513 WWH

Text: A Computational Introduction to Number Theory and Algebra, by Victor Shoup. Available on line, or you can buy a hardcover copy from an online book retailer.

Additional Material

Grading: There will be some problem sets.

Problem sets:

Course description:

We shall study algorithms for computing with integers, polynomials, and other algebraic objects. These algorithms play an essential role in the technologies underlying modern systems for storing and transmitting data, especially in the areas of error correcting codes and cryptography, and we shall study some of these applications as well.

I'd like to spend most class time focusing on number theory and algorithms. The lectures should be easily accessible to students who have had undergraduate courses in abstract algebra, linear algebra, and probability theory; however, the textbook for the course develops all of the necessary mathematics from scratch, and so students with some gaps in their mathematical background can fill any such gaps by reading the textbook.

It is also assumed that students have some basic background in algorithm design and analysis.

Course Outline (tentative)

  1. Some basic number theory
  2. Arithmetic with large integers and applications
  3. The distribution of primes
  4. Probabilistic algorithms for generating prime numbers and random factored numbers
  5. Algebra Review
  6. Probabilistic primality testing
  7. Generators and discrete logarithms
  8. Quadratic residues and quadratic reciprocity
  9. Linear Algebra Review
  10. Subexponential-time algorithms for discrete logarithms and factoring
  11. Algebra Review: More Rings
  12. Polynomial arithmetic and applications
  13. Finite Fields
  14. Algorithms for finite fields
  15. Deterministic primality testing