CS-E4500: Advanced Course in Algorithms [Spring 2026, Aalto University]
Lecture 5 (Tue 24 Feb 2026): Finite fields and Chinese remaindering. This lecture introduces fundamental concepts about finite fields, including prime and non-prime fields, and the role of irreducible polynomials in constructing field extensions. We will also discuss several useful tools-such as Fermat’s Little Theorem, Freshman’s Dream, and the structure of the multiplicative group of a finite field, which will be important for the next topic: univariate polynomial factorization over finite fields. In addition, we will review some basics of the GCD and the Chinese Remainder Theorem (CRT).
Lecture 6 (Tue 3 Mar 2026): Univariate polynomial factorization by Cantor-Zassenhaus.Polynomial factorization is a key concept in many important areas of computer science, and this lecture will introduce univariate polynomial factorization over a finite field. We will see a randomized algorithm for univariate polynomial factorization by Cantor and Zassenhaus (1981) in some detail. Note that univariate polynomial factorization plays a crucial role in the factorization of bivariate and even multivariate polynomials, although we will not cover those settings.
Lecture 7 (Tue 10 Mar 2026): Univariate polynomial factorization by Berlekamp. This lecture continues from the previous one on univariate factorization over finite fields. The algorithm due to Cantor and Zassenhaus (1981) turns out to be efficient but randomized. We will see a deterministic version of Univariate Polynomial Factorization due to Berlekamp (1970). Note that Berlekamp’s algorithm works better over certain finite fields but not really efficient over any finite field. This leads us to one of the key open questions in computational algebra, with which we will conclude the topic of polynomial factorization.
Weekly two lectures: One lecture and one problem solving session.
CGE195-Algorithms for structured matrices and polynomials [Half-Semester course, Autumn 2024, Chennai Mathematical Institute]
Univariate polynomials: GCD, Fast computation of division with remainder, Univariate multipoint evaluation, Chinese remainder theorem for polynomials, Univariate polynomial interpolation, Lagrange & Hermite interpolation. Rational function reconstruction, Cauchy interpolation, Padé Approximation. Resultants.
Multivariate polynomial multiplication.
Linear recurrences. Wiedemann's algorithm for sparse linear system-solving.
Sparse polynomial interpolation, Prony/Ben-Or & Tiwari's algorithm.