Prof. P. Bürgisser
2h Course, TU Berlin, SS 2024,
Eligible as BMS Basic Course in area 2.
Friday 10-12, MA 376
Begin: April 19
TU Berlin
Institute of Mathematics
Straße des 17. Juni 136,
10623 Berlin, Germany
The goal of the course is to discuss several remarkable algorithms that enable an efficient solution of basic problems algebra and number theory. These algorithms are high of importance in applications, notably in cryptography.
The only prerequisite for the course is familiarity with Algebra I.
Contents
1. Berlekamp’s algorithm
2. Hensel lifting
3. Randomized primality tests
4. Basics on lattices
5. Gram-Schmidt orthogonalization
6. LLL-algorithm
7. Factoring rational polynomials
8. Excursion on cyclotomic polynomials
9. AKS primality test
Literature:
Dietzfelbinger. Primality testing in polynomial time. From randomized algorithms to PRIMES is in P. Springer 2004.
von zur Gathen and Gerhard. Modern Computer Algebra. Cambridge 2003.
Lovasz. An algorithmic theory of numbers, graphs and convexity. SIAM 1986.