max planck institut
mpii logo Minerva of the Max Planck Society

Computational Number Theory and Algebra

Basic Information

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).

Other reference materials:


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:
Homeworks: 40%
Mid-term Exam: 30%
End-term Exam: 30%

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)