max planck institut
informatik
informatik
| Lecture time: | Mondays and Wednesdays 14:00-16:00 |
|---|---|
| Lecture room: | Room HS 003 (E1.3) |
| Lecturers: | Markus Bläser and Chandan Saha |
| Primary textbook: | "Modern Computer Algebra" by von zur Gathen and Gerhard |
| Tutorial time & place: | Wednesday 12:00-14:00, Room HS 001 (E1.3) |
| Tutor: | Fabian Wobito (email: s9fawobi "at" stud "dot" uni "minus" saarland "dot" de) |
| Exam dates: | Midterm: June 11; Endterm: August 6; Re-exam: October 11 |
This is an introductory course on the computational aspects of number theory and algebra. Given the striking applications of algebraic algorithms in cryptography, coding theory and computational complexity theory, the aim of this course is to gain familiarity with some of the important algebraic tools and techniques like Chinese remaindering, Discrete Fourier Transform, Hensel lifting, Short vectors in Lattices, Smooth numbers, Elliptic curves, Algebraic independence etc. and show how these tools are used to design algorithms for certain fundamental problems like integer & polynomial factoring, integer & matrix multiplication, fast linear algebra, root finding, primality testing, discrete logarithm, polynomial identity testing etc. We will also cover certain applications in cryptography (RSA cryptosystem, Diffie-Hellman), and coding theory (Reed-Solomon & Reed-Muller codes, locally decodable codes).
| 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 |
| Prerequisites: | Basic familiarity with linear algebra and properties of finite fields as it is covered in Mathematik für Informatiker 1-3. Alternatively, an undergraduate course in algebra. | |||
|---|---|---|---|---|
| Class Info: | This is a 9-credit-point class. There will be two lectures and one tutorial session per week. | |||
| Grading policy: | Your final grade will be determined by your performance in the homework problems, one mid-term exam, and one final exam:
|