Algorithms in Algebra and Number Theory

Course Info

Instructor: Swastik Kopparty (swastik.kopparty@utoronto.ca)
Class Time and Place: Mondays 1pm-2pm, Thursdays 2pm-4pm, Northrop Frye Hall 004 (and Zoom)
Office Hours: Wednesdays 11am-12noon (on Zoom)

Please email me if you are not enrolled in the course and would like to sit in. Please email me if you are trying to enroll in the course and would like to be added to the course quercus site in the meantime.

Prerequisites: a solid background in linear algebra, a tiny bit of abstract algebra, mathematical maturity
There is no required book.
References: Lovasz (An Algorithmic Theory of Numbers, Graphs and Convexity), various recent papers available online

This course will study algorithms for dealing with basic objects of algebra and number theory, such as integers, polynomials, rational numbers, matrices, etc. Topics will include: GCDs, continued fractions, lattices, Fast Fourier Transforms, primality testing, integer and polynomial factorization, fast matrix multiplication, and applications to combinatorial algorithms and cryptography.

Homeworks

• HW0
• Remaining Homeworks on the quercus page.

Lectures

• September 9: Course overview, integer operations, Euclid's GCD algorithm
• September 13: Rational approximation, continued fractions
• September 16: Rational approximation, systems of linear equations over the integers
• September 20 - efficiently computing the Hermite Normal form
• September 23 - finding roots of univariate polynomials in the complex numbers
• September 27 - resultants
• September 30 - Bezout's theorem, finite fields
• October 4 - square roots in finite fields
• October 7 - square roots mod m
• October 14 - discrete logs via smooth numbers
• October 18 - the Discrete Fourier Transform
• October 21 - the Fast Fourier Transform (FFT), applications to polynomial algebra
• October 25 - fast multipoint polynomial evaluation, interpolation
• October 28 - fast integer multiplication, primality testing
• November 1 - midterm solutions
• November 4 - wrapup of randomized primality testing
• November 15 - secret sharing, k-wise independence
• November 18 - Secure multiparty computation
• November 22 - Public key cryptography, RSA
• November 25 - Attacks on RSA
• November 29 - Boolean Fourier Analysis basics
• December 2 - Finding important Fourier coefficients of a Boolean function
• December 6 - STUDENT PRESENTATIONS
• December 9 - STUDENT PRESENTATIONS