| 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 8:
6 Sep to 12 Sep |
Quadratic equation for p= 3 (mod 4) Polynomial division, Euclid's algorithm in Zp[x] Algorithm to factor a quadratic polynomial |
|
Week 9:
13 Sep to 19 Sep |
Hensel lifting: Solving quadratic equations in Zpk
Irreducible polynomials in Zp[x]: testing and counting Quiz 3 (Sep 19) |
|
Week 10:
20 Sep to 26 Sep |
Groups and fields; Application: Secret sharing |
|
Week 11:
27 Sep to 03 Oct |
Univariate polynomial factorization: The Cantor-Zassenhaus algorithm |
| Part 2: Primality Testing and Integer Factoring | |
|---|---|
|
Week 12:
04 Oct to 10 Oct |
Primality testing; the Miller Rabin primality test
Quiz 4 (Oct 09) |
|
Week 13:
11 Oct to 17 Oct |
Integer factoring: n1/4 and n1/3 algorithms
Intro to the quadratic sieve algorithm |
|
Week 14:
25 Oct to 31 Nov |
The quadratic sieve algorithm |
|
Week 15:
01 Nov to 07 Nov |
|
|
Week 16:
08 Nov to 13 Nov | |
|
14 Nov to 18 Nov |
Final Exam |