16:642:587 Selected Topics in Discrete Mathematics
Fall 2020
Swastik Kopparty
Subtitle:
Algorithmic Number Theory
Course Description:
This course will be an introduction to basic algorithmic number theory (i.e., designing algorithms for number theoretic problems).
Topics include:
- Primality testing
- Lattices and Diophantine approximation
- Integer factorization
- Computing discrete logarithms
- Undecidability of solving Diophantine equations
- Polynomial factorization
- Elliptic curve algorithms
- Number field algorithms
- The complexity of algebraic computation
Textbook:
none
Prerequisites:
642:582