German website

study program: Master of Computer Science (M_Inf), 2nd semester

ECTS credits: 4

lecture term: summer semester

prerequesites: qualified bachelor program in computer science or mathematics (or related), no prerequesite of master courses

language: This lecture will be given in English if there is at least one student not knowing German, otherwise in German.

Computer algebra deals with symbolic manipulation and computation. This enables exact differentiation and integration of functions and computation of their critical points. Polynomials may be dissolved into irreducible factors. It is possible to do exact computations with arbitrarily large numbers.

Existing computer algebra systems deal with graphical representation of everything they computed. E.g., this enables them to do complete curve discussions automatically as you may had to to manually in a calculus course.

Using an exact processing of terms, computer algebra systems simplify automatically (reducing, collecting, factoring) and avoid inaccuracies as may occur when terms are approximated by numeric values.

This makes computer algebra the counterpart and alternative to numeric data processing. While numerics is based on analytic convergence properties of sequences and series, computer algebra is based more on methods of discrete mathematics and algorithmics.

This course focuses on exact manipulations with numbers and polynomials, also in finite fields. We discuss their applications for cryptography. For this factoring of numbers and polynomials is crucial. This is why we discuss that in detail. Beyond the method of how to solve a linear equation system (which is covered by the Gauss algorithm in the bachelor program), we also discuss how to generalize this to polynomial equation systems.

You also get weekly assignments to implement selected methods discussed in practice. You may work with an open-source system (Maxima) or with a commercial system (Mupad of the symbolic toolbox of Matlab).

The material covered is summarized in German slides published on the German website of this course.

The prime textbook is the German book of Köpf (see below). We will cover everything up to chapter 8. The rest of the book which is dedicated to problems from calculus will not be covered.

The following contents are covered:

1) Introduction into a computer algebra system (Maxima, Mupad)

2) Integer arithmetic
    2.1) Representation, comparisons, addition, multiplication
    2.2) Division, rational arithmetic

3) Modular arithmetik
    3.1) Computation of modular functions
    3.2) Applications in cryptography
    3.3) Prime test

4) Polynomial arithmetic
    4.1) Addition and multiplication
    4.2) Division and simple factoring

5) Polynomial equation systems
    5.1) Algebraic foundations
    5.2) Solution using resultants

6) Efficient factoring of polynomials
    6.1) Factoring in Z_p[x] and GF(q)[x]
    6.2) Factoring in Q[x] via Z_p[x]

Joachim von zur Gathen / Jürgen Gerhard: Modern Computer Algebra, Cambridge University Press 2003 (2nd ed.), ISBN 0-521-82646-2
This book goes far beyond our course. It is more suitable for a program for students of mathematics.

Michael Kaplan: Computeralgebra, Springer 2005, ISBN 3-540-21379-1 (in German)
This book covers some material discussed in better detail, but in general requires to many prerequesites. It is also more suitable for mathematics students.

Donald Knuth: The Art of Computer Programming, vol. 1,2,3,
Addison Wesley 1997, ISBN 0-201-89683-4,  0-201-89684-2, 0-201-89685-0
These volumes cover some details of issues discussed, but they are mainly no computer algebra books.

Wolfram Koepf: Computeralgebra, Springer 2006, ISBN 3-540-29894-0 (in German)
This is our textbook. 

Steven Weintraub: Galois Theory, Springer 2009 (2nd ed.), ISBN 978-0-387-87574-3
This book gives insight into the theory of groups and fields. The content is not covered in our course, but gives a profound understanding of what we sketch in chapter 5.