CS 681: Computational Algebra and Number Theory

Course Contents:

Elementary operations: the complexity of basic operations like additions, multiplications for integers and polynomials. Polynomials: The complexity of factorization, irreducibility testing, ideal membership etc for polynomials over finite fields. Motivating example: Reed-soloman codes. Integer Lattices: the complexity of finding a short vector in an integer lattice. Motivating example; polynomial factorization. Integers: The complexity of factorization, primality testing, discrete log computation etc for integers. Motivating examples: RSA and El Gamal cryptosystems. Elliptic curves: the complexity of addition, point counting etc. for elliptic curves. Motivating examples: Elliptic curve cryptosystems and integer factoring.