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.

[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]