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.
- ``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.
[COVID19][14,16Apr-20] [pdf] Integer factoring. Pollard's, Fermat's, Morrison-Brillhart, Quadratic sieve methods, NFS.
[COVID19][07,09Apr-20] [pdf] AKS Primality testing (deterministic).
[COVID19][31Mar,02,07Apr-20] [pdf] Primality testing (randomized). RSA cryptosystem.
[COVID19][19,24,26Mar-20] [pdf] Integral polynomial factoring. Lattices. NTRU Cryptosystem.
[COVID19][17,19Mar-20] [pdf] Multivariate polynomial factoring.
[29Feb, 03,05Mar-20] [pdf] Bivariate polynomial factoring.
[26, 29Feb-20] [pdf] List decode. Counting irreducibles.
[13Feb-20] [pdf] Reed-Solomon code.
[11, 13Feb-20] [pdf] Cantor-Zassenhaus factoring algorithm.
[04, 06Feb-20] [pdf] Berlekamp factoring algorithm.
[28, 30Jan-20] [pdf] Factorization over finite fields.
[23, 28Jan-20] [pdf] Fast matrix multiplication.
[23Jan-20] [pdf] Fast integer division, GCD and CR. Revisit integer multiplication.
[16, 18Jan-20] [pdf] Fast integer multiplication.
[14, 16Jan-20] [pdf] Fast polynomial multiplication.
[09, 14Jan-20] [pdf] GCD algorithm. Chinese remainder theorem (CR).
[02, 07Jan-20] [pdf] Outline. Notation. Background.