SYLLABUS
topics (tentative).
- Basic algebra results, algorithms- Polynomial multiplication
- Integer multiplication
- Matrix multiplication
- Polynomial factoring -- over finite fields
- Reed-Solomon codes and list decoding
- Blackbox factoring
- Polynomial factoring -- over rationals
- Lattices, NTRU cryptosystem
- Primality testing
- Integer factoring
- Elliptic curves
- Discrete logarithm
Advanced topic ideas.
- Circuit factoring and Debordering results (see STOC'24, etc.) [link].- ``Integer multiplication in O(n.log n)-time'' by Harvey & van der Hoeven (Mar'19) [news].
- Fürer's (STOC'07) and De-Kurur-Saha-Sapharishi's (STOC'08) integer multiplication.
- Le Gall's (ISSAC'14) faster matrix multiplication.
- Kedlaya-Umans' (FOCS'08) sub-quadratic polynomial factoring over finite fields.
- Equivalence of multivariate factoring and the identity testing problem. [pdf]
- Gröbner Basis methods for ideal membership.
- LLL reduced basis applications.
- Variant's of NTRU Cryptosystem.
- Moroz-Schost's (ISSAC'16) fast algorithm for resultant.
Schedule.
[21-Apr week] Integer factoring heuristics. [video27]
[14-Apr week] AKS Primality testing (deterministic). Integer factoring ideas. [video25] [video26] [slide16] [slide17]
[07-Apr week] NTRU cryptosystem. Introduction to Primality testing. Solovay-Strassen and Miller-Rabin primality tests. RSA cryptosystem. [video23] [video24] [slide15]
[31-Mar week] L3 algorithm. Shortest-vector problem (SVP). Rational approximation problem. [video21] [video22]
[24-Mar week] Multivariate polynomial factoring. Integral polynomial factoring. Lattice theory (or, Geometry of numbers!). [video19] [video20] [slide14]
[17-Mar week] Multivariate polynomial factoring. [video17] [video18] [slide13]
[03-Mar week] Bivariate polynomial factoring. [video15] [video16] [slide12]
[17-Feb week] Reed-Solomon code. List decode. Counting irreducibles. [video13] [video14] [slide10] [slide11]
[10-Feb week] Berlekamp. Cantor-Zassenhaus factoring algorithm. [video11] [video12] [slide9]
[03-Feb week] Fast matrix multiplication. Irreducibility and Factorization over finite fields. [video9] [video10] [slide7] [slide8]
[27-Jan week] Fast integer multiplication/ division, GCD and CR. Revisit integer/ matrix multiplication. [video7] [video8] [slide5] [slide6]
[20-Jan week] Fast polynomial and integer multiplication. [video5] [video6] [slide3] [slide4]
[13-Jan week] GCD algorithm. Chinese remainder theorem (CR). [video3] [video4] [slide2]
[06-Jan'25 week] Outline. Notation. Background. [video1] [video2] [slide1]