Mathematical Software: Computer Algebra

Mathematics 69.387: CLASS OUTLINE WINTER 2001

Week Dates Assignments Sections Topics
1 Jan.3-Jan.5 ~ Chapter 1 Introduction to the course.
2 Jan.8-Jan.12 ~ 25.1-25.3 Review of algebraic concepts.
3 Jan.15-Jan.19 A1 handed-out Chapter 2 Addition and multiplication of numbers and polynomials. Data structures. Division with remainder.
4 Jan.22-Jan.26 ~ 3.1-3.2 Euclidean algorithm; extended Euclidean algorithm.
5 Jan.29-Feb.2 A1 handed-in;
A2 handed-out
3.4; 4.1 Analysis of extended Euclidean algorithm. Application: modular arithmetic.
6 Feb.5-Feb.9 ~ 4.2-4.4 Modular inverses. Repeated squaring.
7 Feb.12-Feb.16 ~ 5.1-5.3 Evaluation and interpolation. Application: secret sharing.
~ Feb.19-Feb.23 WINTER BREAK NO CLASSES THIS WEEK
8 Feb.26-Mar.2 A2 handed-in;
A3 handed-out
5.4-5.5 Chinese remainder algorithm. Application: modular determinant computation.
9 Mar.5-Mar.9 ~ 8.1; 12.1 Karatsuba's algorithm. Strassen's algorithm.
10 Mar.12-Mar.16 ~ 8.2 Discrete Fourier transform.
11 Mar.19-Mar.23 A3 handed-in;
A4 handed-out
9.1; 14.1 Newton iteration. Fast division with remainder. Factorization of polynomials over finite fields.
12 Mar.26-Mar.30 ~ 14.2-14.4; 21.1 Factorization of polynomials over finite fields (cont.). Groebner basis.
13 April 3-April 4 A4 handed-in 21.2-21.5 Groebner basis (cont.). Review of the course.

Note. Sections and chapters are from the textbook: Modern Computer Algebra by Joachim von zur Gathen and Jurgen Gerhard.