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.