# 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

- Primality testing

- Integer factoring

- Elliptic curves

- Discrete logarithm

# Advanced topic ideas.

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

- Moroz-Schost's (ISSAC'16) fast algorithm for resultant.

# Schedule.

[18, 21Apr-17] [pdf] Integer factoring. Pollard's, Fermat's, Morrison-Brillhart, Quadratic sieve methods.

[11Apr-17] [pdf] Primality testing (deterministic). RSA cryptosystem.

[07Apr-17] [pdf] Primality testing (randomized).

[28, 31Mar, 01Apr-17] [pdf] Integral polynomial factoring. Shortest vector in lattices.

[07, 10, 21Mar-17] [pdf] Blackbox multivariate factoring.

[21, 24Feb, 07Mar-17] [pdf] PFFF -- Bivariate polynomials.

[14, 17, 21Feb-17] [pdf] PFFF -- Coding theory.

[07, 14Feb-17] [pdf] PFFF -- Cantor-Zassenhaus algorithm.

[03, 07Feb-17] [pdf] PFFF-- Resultant. Berlekamp as a reduction method.

[27, 31Jan-17] [pdf] Polynomial factoring over finite fields (PFFF). Berlekamp's algorithm.

[24Jan-17] [pdf] Fast matrix multiplication. Tensor rank.

[21Jan-17] [pdf] Fast integer division. Fast gcd.

[20Jan-17] [pdf] Fast integer multiplication.

[17Jan-17] [pdf] Fast polynomial multiplication.

[12Jan-17] [pdf] GCD algorithm. Chinese remainder theorem.

[06, 10Jan-17] [pdf] Outline. Notation. Background.