Instructor: Victor Shoup

• Phone: (212) 998-3511
• Office: 511 WWH
• email: shoup@cs.nyu.edu

Mailing List

• It is important that you subscribe to the class mailing list, in order to receive announcements.
• To subscribe to the list, follow these instructions.

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

• Supplement to Chapter 2

Grading: There will be some problem sets.

Problem sets:

• Problem Set 1 (Due Feb. 9):
  • Chapter 1: 8
  • Supplement to Chapter 2 (above): 1, 2, 3
  • Chapter 3: 26, 27, 28, 29, 30
• Problem Set 2 (Due Feb. 23):
  • Chapter 4: 1, 2, 5, 7.
  • Chapter 5: 1, 2.
• Problem Set 3 (Due March 23):
  • Chapter 8: 22, 25, 26, 27.
  • Chapter 9: 6, 10, 22, 23, 28, 29, 30, 31, 32, 33, 43.
• Problem Set 4 (Due April 6):
  • Chapter 6: 27.
  • Chapter 7: 26.
  • Chapter 10: 6, 14.
  • Chapter 11: 5-9 (these form one big problem), and 10.
• Problem Set 5 (Due April 27):
  • Chapter 13: 2, 4, 7, 8.
  • Chapter 15: 14.
  • Chapter 16: 1, 4.
• Extra Credit (Due April 27):
  • Chapter 17: 28, 29, 30, 31, 32, 33, 34, 35.

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.

1. Some basic number theory
   • Fundamental theorem of arithmetic
   • Congruences
2. Arithmetic with large integers and applications
   • Basic arithmetic
   • Fast exponentiation
   • Euclid's algorithm
   • Chinese remaindering
   • Rational reconstruction (including Chinese remaindering with errors)
3. The distribution of primes
   • Chebyshev's theorem
   • Bertrand's postulate
   • Mertens' theorem
   • The prime number theorem
4. Probabilistic algorithms for generating prime numbers and random factored numbers
   • Kalai's algorithm
5. Algebra Review
   • Abelian groups
   • Rings
6. Probabilistic primality testing
   • The Miller-Rabin test
7. Generators and discrete logarithms
   • Finding generators mod p
   • Simple algorithm for discrete logarithms mod p
8. Quadratic residues and quadratic reciprocity
   • The Legendre and Jacobi symbols
   • Quadratic reciprocity
   • Computing square roots mod p
9. Linear Algebra Review
   • Modules and vector spaces
   • Matrices
10. Subexponential-time algorithms for discrete logarithms and factoring
    • Smooth numbers
    • Simple subexponential-time discrete logarithms
    • Simple subexponential-time factoring
    • Practical improvements (the quadratic sieve)
11. Algebra Review: More Rings
12. Polynomial arithmetic and applications
    • Basic arithmetic
    • Fast exponentiation
    • Euclid's algorithm
    • Chinese remaindering/polynomial interpolation
    • Secret sharing
    • Linearly generated sequences
13. Finite Fields
14. Algorithms for finite fields
    • Constructing irreducible polynomials
    • Factoring polynomials
15. Deterministic primality testing
    • The new AKS primality test