# 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.