Computer Algebra

Lecturer

Prof. Friedrich Eisenbrand

Assistant

Yuri Faenza

Alfonso Cevallos

News & Log

 

18.02: Big O notation. Basic arithmetic operations. School method for addition and multiplication. Karatsuba algorithm. Slides.

25.02: Analysis of Karatsuba algorithm. Division with remainder. Euclidean algorithm. Slides.

04.03: Extended Euclidean algorithm. Fast modular exponentiation. Chinese remainder Theorem. Euler’s phi function. Slides.

11.03: Basic properties of rings and groups. Fermat’s little Theorem. RSA cryptography. Fermat primality test, Carmichael numbers. Slides

18.03: Properties of Carmichael numbers and the Miller-Rabin test. Intro to distribution of primes. Slides

25.03: Chebyshev’s Theorem on the density of primes. Slides

01.04: Computation of the determinant of a matrix. Schwartz-Zippel Lemma. Randomized test for the existence of a perfect matching in a graph. (No slides, blackboard lecture. For the first topic, see Assignment 04. For the second and third topics, see pages 165-167 of R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge university press 1985).

08.04-15.04: Proof of the Schwartz-Zippel Lemma. Primitive roots of the unity, Discrete Fourier Transform and Fast Fourier Transform in fields and commutative rings with unity. Introduction to lattices: basis, Hermite Normal Form. Slides

29.04: Polynomial-time algorithm for computing the Hermite Normal Form of a matrix. Certificate that a system of rational linear equations has no integer solution. Slides

06.05: Minkowski’s convex body theorem, with application to shortest vector and simultaneous approximation. Orthogonality defect. Slides

13.05: Lagrange’s algorithm for shortest vector in 2 dimensions. LLL algorithm (first part). Slides

20.05: LLL algorithm (second part). Slides

27.05: Solving random subset-sum using LLL. (No slides, blackboard lecture, based on the paper by A.M. Frieze, On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem, Siam Journal on Computing 15(2). pp. 536-539 (1986).)

 

 

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: Tuesday 15:15 – 17:00 (GR B3 30); first lecture on February 18th
Exercises: Tuesday 17:15 – 19:00 (GR B3 30); first session on February 18th

 *please notice the room change to GR B3 30 (instead of MA A1 12 as in the first session).

Grading

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.

 

Students who received bonus points have been notified via e-mail.

 

Here you find a past exam.

 

You are not allowed to use any kind of support material (books, handwritten notes, etc.) at the exam.

 

 

Assignments

We will publish an assignment sheet with problems and practical exercises on this website. 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. Theoretical exercises can be submitted in groups of up to 3 people. Coding exercises must be submitted individually. Please comment your code thoroughly. Correct solutions to selected “star” problems give bonus points. The deadline is two weeks after the sheet is issued. More precisely, the deadline is:

  • 15:00 if you leave your solutions in the box next to office MA C1 573 (be sure you put them in the correct box).
  • 17:10 if you are sending your solutions via mail or you hand them to us before the exercise session starts.

 We will discuss solutions during the exercise sessions. Notes on some of the previous exercises will also be posted below. 

 

  • Here you can find a survey written by Prof. Eisenbrand on some algorithmic question about lattices and related topics.
  • 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)
  • A Tutorial on Python 2.
  • You can run Python 2 online here and here.