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)._x000D_ _x000D_ Topics include:_x000D_ ¬∑ Primality testing_x000D_ ¬∑ Lattices and Diophantine approximation_x000D_ ¬∑ Integer factorization_x000D_ ¬∑ Computing discrete logarithms_x000D_ ¬∑ Undecidability of solving Diophantine equations_x000D_ ¬∑ Polynomial factorization_x000D_ ¬∑ Elliptic curve algorithms_x000D_ ¬∑ Number field algorithms_x000D_ ¬∑ The complexity of algebraic computation

Textbook:

none

Prerequisites:

642:582