MA 765 - Computer Algebra (Spring 2003)

Course by Uwe Nagel at the University of Kentucky.

Overview

Schedule

MWF, 2:00 - 2:50, CB 343

Material

Many problems in science and engineering lead to equations that have to be solved. Computer Algebra is the area of mathematics that develops tools for the exact solutions of equations (if this is possible at all). It is a very active area of research. This introduction to computer algebra will focus on important algorithms and their applications. Topics will include

Chinese remainder theorem and distributed data structures, interpolation, and modular algorithms

Fast Fourier transform and applications in image compression and for multiplication of (large) integers

LLL algorithm for finding short vectors in a lattice and factorization of polynomials

Gröbner bases and solving systems of polynomial equations in several variables

The course will explain and encourage the use of computer algebra systems such as MAPLE (for which all these and many more algorithms have been implemented).

CONTENTS:

2. Division with remainder

3. The Euclidean algorithm

4. The RSA cryptosystem

5. The Chinese Remainder theorem

6. The Fast Fourier Transform

7. Fast multiplication of polynomials and integers

8. Image compression

9. BCH codes

10. Prime number tests

11. The LLL algorithm

12. The problem of factoring polynomials

13. Factoring polynomials over finite fields

14. Hensel lifting

15. Factoring polynomials over the integers

Examples for using MAPLE

In-class presentations

The Schönhage-Strassen algorithm

Olga Mendoza, Decoding BCH codes (April 21)

Bruce Manley, Primes is in P (April 25)

Adam Feldhaus, Some public key cryptosystems (May 2)

Literature

J. von zur Gathen, J. Gerhard, Modern computer algebra.

E. Bach, J. Shallit, Algorithmic number theory, Vol. 1: Efficient algorithms.

A. M. Cohen, H. Cuypers, H. Sterk (eds.), Some tapas of computer algebra.

J. Grabmeier, E. Kaltofen, V. Weispfennig (eds.), Computer algebra handbook.

Last Up-date: May 4, 2003