| Part 1: Polynomial factorization | |
|---|---|
|
Week 1:
26 July to 01 Aug |
Intro: The cubic equation and the linear equation over integers;
Euclid's algorithm and time complexity analysis; Bezout's lemma |
|
Week 2:
02 Aug to 08 Aug |
Fundamental theorem of arithmetic; Congruences, Chinese remainder theorem |
|
Week 3:
09 Aug to 15 Aug |
Fermat's little theorem; the ring Zn>, the equation xd=a in Zp |
|
Week 4:
16 Aug to 22 Aug |
Quiz 1 (Aug 18),
Lagrange's theorem, factorization of xp-x;
Factoring polynomials modulo composites |
|
Week 5:
23 Aug to 29 Aug |
Wilson's theorem; The set Zn*, Euler's totient function, Euler's theorem; RSA algorithm |
|
Week 6:
30 Aug to 5 Sep |
Quiz 2 (Sep 1)
Solvability of xd=a in Zp ; Quadratic Reciprocity (statement and use); Application of solving quadratic equations in Zp |
|
Week 7:
6 Sep to 12 Sep |
Quadratic equation for p= 3 (mod 4) Polynomial division, Euclid's algorithm in Zp[x], Bezout's lemma for polynomials, Unique factorization |
|
Week 8:
13 Sep to 19 Sep |
Algorithm to factor a quadratic
polynomial
Hensel lifting: Solving quadratic equations in Zpk |
|
Weeks 9, 10:
20 Sep to 03 Oct |
Groups: definition, examples, Cayley table, isomorphism, subgroups, cosets, Lagrange's theorem, quotient group. |
|
Weeks 10,11:
11 Oct to 17 Oct |
Fields, definition, examples,
irreducible polynomials in Zp[x],
finite field examples, HW3 discussion,
Quiz 3 (Oct 15) |
|
Weeks 12, 13:
25 Oct to 03 Nov |
Irreducible polynomials and counting;
Univariate polynomial factorization:
The Cantor-Zassenhaus algorithm
Release of Prog HW3 (26 Oct) with Nov 7 deadline |
| Part 2: Primality Testing and Integer Factoring | |
|---|---|
|
Week 13:
05 Nov, 06 Nov |
Primality testing: the Miller Rabin primality test; Integer factoring: n1/4 and n1/3 algorithms |
|
Week 14:
08 Nov to 13 Nov |
Integer factoring: The quadratic sieve algorithm
Quiz 4 (Nov 13) |
|
Week 15:
14 Nov to 18 Nov |
Final Exam |
|
Week 15:
19 Nov to 21 Nov |
Project presentations |