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.