Contents of the course
- Gcd and extended Gcd : Euclidean algorithm, Extended Euclidean Algorithm (complexity analysis, properties), quasi-linear gcd (Knuth-Schonhage).
- Algorithms for polynomials : evaluation, interpolation. Product tree. Quasi-linear algorithms for multiple point evaluation and interpolation.
- Algorithms for linear algebra : Gauss pivoting (over a field), applications (image, kernel, determinant, linear system solving) ; multimodular methods and Hensel lifting over Z and K[X].
- Elimination theory and resultant. Applications to the computation of theintersection of two plane algebraic curves.
- Polynomial factoring over Z/pZ : Berlekamp algorithm, Cantor-Zassenhaus algorithm, Hensel lifting over Z/p^k Z.
- Application to Error-Correcting Codes : Reed-Solomon codes. Decoding algorithms, list decoding algorithms.
- (… to be completed)
See the french version of this page for informations about the organisation of this course.