[368.164] Computer Algebra 2 (Winter semester 2018-2019)

---

The course is an overview of algorithms for fast polynomial and integer arithmetic, and for polynomial factorization.

Location	MT 327 (Science Park 1)
Time	Wednesday 10:15 - 11:45
First class	Friday 05 October 2018

Note: the lecture on Wednesday 05 December is moved to Friday 14 December (13:45 - 15:15).

The lecture notes will be available after each class: last version.
The problem sheet for the winter holidays homework is available here.

---

Prerequisites

---

Topics

• Karatsuba's algorithm
• Toom-Cook's algorithm
• Evaluation/interpolation
• Discrete Fourier Transform (DFT)
• Fast Fourier Transform (FFT)
• Schönhage-Strassen's algorithm
• Kronecker substitution
• Newton iteration
• Chinese Remainder Theorem (CRT)
• LLL algorithm
• Berlekamp's algorithm
• Cantor-Zassenhaus's algorithm
• Hensel lifting
• Van Hoeij's algorithm

---

Plan of the course (can and will be modified)

1. Semi-fast multiplication (Karatsuba, Toom-Cook)
2. Fast multiplication in \(\bar{k}[X]\) (using Fourier transform)
3. Fast multiplication in \(R[X]\) (Schönhage-Strassen)
4. Fast multiplication in \(\mathbb{Z}\)
5. Fast multiplication in \(R[X,Y]\) (using Kronecker substitution)
6. Fast division
7. Fast evaluation and interpolation
8. Fast Greatest Common Divisor*
9. Fast squarefree decomposition*
10. LLL algorithm and applications
11. Factorization in \(\mathbb{F}_p[X]\) (Berlekamp, Cantor-Zassenhaus)
12. Factorization in \(\mathbb{Q}[X]\) (using Hensel lifting)
13. Faster factorization in \(\mathbb{Q}[X]\) (using LLL)
14. Even faster factorization in \(\mathbb{Q}[X]\) (van Hoeij)*

* Pending available time

---

References

---