Algebra, Number Theory and Computation
General information
Course Number : CSS307.1
Instructor : Mrinal Kumar
Teaching Assistant : Shanthanu S. Rai
Email : first name DOT last name AT tifr DOT res DOT in
Class timing : Tuesday 11:30-1 and 2-3:30 in A-201
Office hours : Monday, 10 am to 11 am, or please send me an email
Grading
Grades will be based on some problem sets (65%), class participation (10%) and an exam (25%).
Prerequisites
Mathematical maturity, familiarity with the contents of a typical Discrete Math and Algorithms Class.
For this class, you are NOT expected to have a background in advanced algebra or advanced number theory (indeed, the instructor doesn't!), and the course will be self contained for the most part.
Description
This course will cover a collection of results (some new, some old) that broadly lie at the intersection of Algebra & Computation or at the intersection of Number Theory & Computation, or all of these.
A tentative list of topics can be found here.
Lectures
- Lecture 01 : Admin things: tentative content, grading etc. Basic algebra: fields, finite fields, polynomial ring etc. Fast Fourier Transform.
- Lecture 02 : FFT continued, Schönhage-Strassen (sketch), Fast division with remainder.
- Lecture 03 : Univariate multipoint evaluation, Efficient parallel GCD computation (Andrews-Wigderson).
- Lecture 04 : Structure and properties of finite fields. Efficient parallel GCD computation contd.
(The first part was guest lecture by Shanthanu)
- Lecture 05 : Chinese remainder theorem, resultants, Gauss's lemma. Fast modular composition and reduction to MME.
- Lecture 06 : Fast multivariate multipoint evaluation over finite fields.
- Lecture 07 : Univariate factorization over finite fields: Berlekamp's algorithm for computing square roots in finite fields, randomized algorithm of Cantor & Zassenhaus.
- Lecture 08 : Berlekamp's deterministic algorithm for univariate factorization over finite fields. Algorithms for factoring bivariate polynomials.
- Lecture 09 : Algorithms for factoring bivariate polynomials contd. Solving linear systems over rationals and over integers.
- Lecture 10 : Agrawal-Biswas randomized primality test. Deterministic primality test of Agrawal-Kayal-Saxena.
- Lecture 11 : Rational approximations and continued fractions.
- Lecture 12 : Approximating complex roots of univariate polynomials. Univariate polynomial factorization over rationals: reduction to shortest vector.
- Lecture 13 : Basics of lattices.
- Lecture 14 : Lattices contd: Minkowski's theorems, LLL algorithm for approximating shortest vector in a lattice.
References