Computer Algebra

Lecturer

Prof. Friedrich Eisenbrand

Nicolai Hähnle

News & Log

• 21.2.: O-notation, addition and multiplication, 3 algorithms to compute Fibonacci numbers
• 28.2.: Algorithms for Addition, Multiplication, Divide & Conquer, Karazuba
• 07.3.: Division with remainder, quadratic lower and upper bound for Euclidean Algorithm
• 14.3.: Modular Arithmetic, Euler Phi-Function, Chinese Remainder Thm., RSA
• 22.3: Randomized Primality Tests: Fermat & Miller-Rabin
• 29.3: Density of Primes and finding large primes
• 04.4: Determinants, Gaussian Elimination is a polynomial-time algorithm, Schwartz-Zippel Lemma
• 11.4: Tutte’s Lemma, Computing max.cardinality matchings with an algebraic algorithm
• 18.4: Multiplication of polynomials, evaluation and interpolation, Fast Fourier Transform (in fields)
• 02.5: Modular Fourier transform and modular FFT
• 09.5: Lattices, Lattice Determinant and Minkowski’s Theorem (the content of this and the next lectures is described here)
• 16.5:The LLL-Algorithm
• 23.5: Analysis of the LLL Algorithm, Factoring rational polynomials

Description

Computer Algebra is concerned with algorithmic challenges emerging from the interplay of Algebra and Computer Science. In this course, students will learn how to design and analyze efficient algorithms for basic arithmetic, polynomials, fast linear algebra and elementary number theory.

Schedule

Lecture: Monday 10:15 – 12:00 (MA A3 30); first lecture on February 21st
Exercises: Tuesday 8:15 – 10:00 (MA A3 30); first session on February 22nd

Your grade will be determined by a written final exam. You can collect bonus points by handing in solutions to selected exercises from the assignment sheets. If you solve 50% or more of the exercises, the grade of your final exam will be improved by a half grade. If you solve 90% or more of the exercises, the grade of your final exam will be improved by a full grade.

Assignments

We will publish an assignment sheet with problems and practical exercises on this website every two weeks. You can work on the exercises, ask questions, and discuss problems during the exercise sessions.

You will have the opportunity to hand in written solutions for feedback. Correct solutions to selected “star” problems give bonus points. We will discuss solutions during the exercise sessions.

Notes on some of the previous exercises will also be posted below. However, they typically do not contain complete solutions and only give final results and/or a rough sketch of a viable solution approach.

Literature

• Victor Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press. (available online)
• Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms, McGraw Hill. (library, online draft)
• Joachim von zur Gathen, Jürgen Gerhard. Modern Computer Algebra, Cambridge University Press. (library)