Date |
Topics |
Lecture notes |
Apr 18 |
Introduction. Motivating applications: RSA cryptosystem, Diffie-Hellman key exchange, Reed-Solomon codes. |
Lecture 1 |
Apr 23 |
Berlekamp-Welch unique decoding, Sudan's list decoding of RS codes, Local decodability - e.g, Hadamard code.
| Lecture 2 |
Apr 25 |
Reed-Muller codes, Chinese Remaindering Theorem, An application of CRT - Determinant computation.
| Lecture 3 |
Apr 30 |
Discrete Fourier Transform, Fast Fourier Transform, Polynomial multiplication using FFT.
| Lecture 4 |
May 2 |
Integer multiplication using FFT, Polynomial division.
| Lecture 5 |
May 7 |
Multipoint evaluation, Polynomial interpolation, the Resultant.
| Lecture 6 |
May 9 |
Modular gcd computation, Polynomial factoring over finite fields.
| Lecture 7 |
May 14 |
Equal-degree factoring, Reduction to root finding, Testing irreducibility.
| Lecture 8 |
May 16 |
Generating irreducible polynomials over finite fields, Miller-Rabin primality test.
| Lecture 9 |
May 21 |
AKS primality test.
| AKS paper |
May 23 |
AKS primality test (contd.)
| AKS paper |
May 30 |
Hensel lifting, Bivariate polynomial factoring.
| Lecture 12 |
June 4 |
Bivariate factoring (contd.), Schwartz-Zippel lemma, Hilbert irreducibility theorem (ref. Madhu Sudan's course note)
| Lecture 13 |
June 6 |
Black-box polynomial factoring, Sparse polynomial interpolation.
| Lecture 14 |
June 11 |
Short vectors in lattice, The LLL basis reduction algorithm.
| Lecture 15 |
June 13 |
LLL algorithm (contd.), Polynomial factoring over rationals.
| Lecture 16 |
June 18 |
Breaking low exponent RSA, Pollard-Strassen integer factoring algorithm, Discussion of assignment problem solutions.
| Lecture 17 |
June 20 |
Pollard's rho method for integer factoring, Introduction to Smooth numbers.
| Lecture 18 |
June 25 |
Dixon's random square method for integer factoring.
| Lecture 19 |
June 27 |
Quadratic Sieve method for integer factoring, Discussion of mid-sem problem solutions.
| Lecture 20 |
July 2 |
Index calculus method, Ideals and Varieties, Division in Ideals (ref. Madhu Sudan's course note)
| Lecture 21 |
July 4 |
Ideal membership, Groebner bases: Existence & uniqueness, Buchberger's algorithm (ref. Madhu Sudan's course note)
| Lecture 22 |
July 9 |
Buchberger's algorithm (contd.), Explicit bound for ideal membership (ref. Madhu Sudan's course note)
| Lecture 23 |
July 11 |
Elimination & Extension theorems, Hilbert's weak & strong Nullstellensatz (ref. Madhu Sudan's course notes: 1 & 2)
| Lecture 24 |
July 16 |
Complexity of Bilinear forms and matrix multiplication (ref: Markus Bläser's course notes)
| Lecture 25 |
July 18 |
Complexity of Bilinear forms and matrix multiplication (contd.)
| Lecture 26 |
July 19 |
Complexity of Bilinear forms and matrix multiplication (contd.)
| Lecture 27 |
July 25 |
Wrapping up...What we did/didn't cover in the course, List of open problems, Discussion of assignment solutions
| Lecture 28 |