| Part 1: Polynomial factorization | |
|---|---|
|
Week 1:
28 July to 02 Aug |
Intro: The cubic equation and the linear equation over integers;
Euclid's algorithm and time complexity analysis; Bezout's lemma |
|
Week 2:
4 Aug to 9 Aug |
Fundamental theorem of arithmetic; Congruences, Chinese remainder theorem |
|
Week 3:
11 Aug to 16 Aug |
Quiz 1 (Aug 14)
Fermat's little theorem; the equation xd=a in Zp |
|
Week 4:
18 Aug to 23 Aug |
Lagrange's theorem, factorization of xp-x;
When f(x) has deg(f) roots and g divides f, g has deg(g) roots. The ring Zn; the set Zn*, Euler's totient function. |
|
Week 5:
25 Aug to 30 Aug |
Euler's theorem; Quiz 2 (Aug 29) |
|
Week 6:
1 Sep to 6 Sep |
RSA Algorithm; x2=a in Zp when p ≡ 3 (mod 4) |
|
Week 8:
15 Sep to 20 Sep |
Tonelli Shanks algorithm, Polynomial division, Euclid's algorithm in Zp[x] Quadratic reciprocity (statement and use) |
|
Week 9:
22 Sep to 27 Sep |
Hensel lifting: Solving quadratic equations in Zpk
Results for integers that work for polynomials in Zp[x] Second algorithm to factor a quadratic polynomial Irreducible polynomials in Zp[x]: testing and counting |
|
Week 10:
6 Oct to 11 Oct |
Groups and fields; Application: Secret sharing
Quiz 3 (Oct 10) |
|
Week 11:
13 Oct to 18 Oct |
Univariate polynomial factorization: The Canter-Zassenhaus algorithm |
| Part 2: Primality Testing and Integer Factoring | |
|---|---|
|
Week 12:
20 Oct to 25 Oct |
Primality testing; the Miller Rabin primality test |
|
Week 13:
27 Oct to 1 Nov |
Integer factoring: n1/4 and n1/3 algorithms
Intro to the quadratic sieve algorithm Quiz 4 (Nov 1) |
|
Week 14:
3 Nov to 8 Nov |
The quadratic sieve algorithm |
|
Week 15:
10 Nov to 15 Nov |
AKS Primality Testing; Quiz 5 (Nov 15) |
|
17 Nov to 22 Nov |
Final Exam |