German website

study program: none. This lecture used to be in older programmes for Master of Computer Science. Now it is abolished.

ECTS credits: 4

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.

In WS 2012/13, this lecture was given in English.

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. These slides will be translated in English in time and published below.

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 English book of Geddes et al. is the most similar equivalent to our textbook, except for cryptographic methods for which we refer to a cryptogtaphy book, e.g. Paar et al. (see below).

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 arithmetic
    3.1) Computation of modular functions
    3.2) Applications in cryptography
    3.3) Primality test using modular arithmetic

4) Polynomial arithmetic
    4.1) Addition and multiplication
    4.2) Division and rational functions

5) Polynomial equation systems
    5.1) Linear equation systems, matrices, determinants
    5.2) Solution using resultants

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

Summary for final exam preparation (crossed-outs are not covered)

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.

Keith O. Geddes/ Stephen R. Czapor / George Labahn: Algorithms for Computer Algebra, Springer 1992, ISBN 0-792-39259-0
This is the closest English version to our textbook.

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. 

Christof Paar / Jan Pelzl / Bart Preneel: Understanding Cryptography: A Textbook for Students and Practioners, Springer 2010, ISBN 3-64204100-0
Only parts of chapter 6 and chapter 8 are relevant for this course.

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.