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.

[07-Apr week] NTRU cryptosystem. Introduction to Primality testing. Solovay-Strassen and Miller-Rabin primality tests.    [video23] [video24]    [slide15]

[31-Mar week] L³ 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]