Algebra, Number Theory and Computation
General information
Course Number : CSS307.1
Instructor : Mrinal Kumar
Teaching Assistant : Soham Chatterjee
Email : first name DOT last name AT tifr DOT res DOT in
Class timing : Monday and Wednesday 9:30-11 in A-201
Office hours : Tuesday, 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).
- Lecture 03 : Fast division with remainder.
- Lecture 04 : Fast univariate multipoint evaluation. Reducing modular composition to multivariate multipoint evaluation.
- Lecture 05 : Univariate polynomial GCD, Resultants.
- Lecture 06 : Chinese Remainder Theorem and applications, discriminant and square-freeness.
- Lecture 07 : Gauss' lemma, Fast multivariate multipoint evaluation over finite fields.
- Lecture 08 : Efficient parallel GCD.
- Lecture 09 : Agrawal-Biswas primality test.
- Lecture 10 : AKS primality test.
- Lecture 11 : Finding square roots over finite fields. Randomized algorithm for univariate factorization.
- Lecture 12 : Randomized algorithm for univariate factorization contd.
- Lecture 13 : Deterministic univariate factorization over finite fields.
- Lecture 14 : Algorithms for bivariate polynomial factorization.
- Lecture 15 : Algorithms for bivariate polynomial factorization contd.
References