Algebra, Number Theory and Computation
General information
Course Number : CSS307.1
Instructor : Mrinal Kumar
Email : first name DOT last name AT tifr DOT res DOT in
Class timing : Friday, 9:30 am to 1:00 pm, with a break in between
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.
- Lecture 02 : Polynomial arithmetic: FFT, Schönhage-Strassen (sketch).
- Lecture 03 : Structure and properties of finite fields.
- Lecture 04 : Division with remainder, univariate multipoint evaluation, GCD computation.
- Lecture 05 : Chinese remainder theorem, resultants, Gauss's lemma. Univariate factorization over finite fields: algorithm of Cantor & Zassenhaus.
- Lecture 06 : Cantor and Zassenhaus' algorithm contd, Berlekamp's algorithm. PIT: SZ lemma, multiplicity SZ lemma.
- Lecture 07 : Fast modular composition, multivariate multipoint evaluation and applications.
- Lecture 08 : Algorithms for factoring bivariate polynomials.
- Lecture 09 : Primality testing: randomized primality test of Agrawal-Biswas, deterministic Agrawal-Kayal-Saxena primality test.
- Lecture 10 : Rational approximations and continued fractions.
- Lecture 11 : Continued fractions continued. Integer solutions to linear systems.
- 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.
- Lecture 15 : Integer factorization: randomized and deterministic algorithms.
References