SYLLABUS
topics (tentative).
- Basic algebra results, algorithms- Polynomial multiplication
- Integer multiplication
- Matrix multiplication
- Polynomial factoring -- over finite fields
- Reed-Solomon codes and list decoding
- Polynomial factoring -- over rationals
- Primality testing
- Integer factoring
- Elliptic curves
- Discrete logarithm
Advanced topic ideas.
- Fürer's integer multiplication- Faster matrix multiplication
- Kedlaya & Umans' (2011) sub-quadratic polynomial factoring over finite fields
- Equivalence of multivariate factoring and the identity testing problem. [pdf]
Schedule.
[13-Nov-2014] [pdf] Elliptic curve factoring method.
[10-Nov-2014] [pdf] Number field sieve.
[08-Nov-2014] [pdf] Fast Integer Multiplication using Modular Arithmetic.
[03-Nov-2014] [pdf] Morrison & Brillhart's implementation, Quadratic sieve.
[30-Oct-2014] [pdf] Pollard's rho method, (p-1) method, Fermat's method, Kraitchik family of algorithms.
[27-Oct-2014] [pdf] RSA, smooth numbers.
[17-Oct-2014] [pdf] Primality -- Agrawal-Kayal-S (AKS test).
[16-Oct-2014] [pdf] Primality -- Miller-Rabin.
[13-Oct-2014] [pdf] Primality testing -- Solovay-Strassen.
[09-Oct-2014] [pdf] LLL reduced basis algorithm.
[29-Sep-2014] [pdf] Introduction to the reduced basis of a lattice.
[27-Sep-2014] [pdf] Polynomial factorization over rationals.
[25-Sep-2014] [pdf] Blackbox factoring algorithm.
[11-Sep-2014] [pdf] Hilbert's irreducibility theorem (using Hensel lift).
[08-Sep-2014] [pdf] Multivariate factoring via Hensel lift. Via Hilbert's irreducibility.
[04-Sep-2014] [pdf] Hensel lifting examples. Bivariate factoring algorithm.
[01-Sep-2014] [pdf] Counting irreducibles over finite fields. Hensel's lifting lemma.
[28-Aug-2014] [pdf] Reed-Solomon code. Peterson decoding. List-decoding.
[25-Aug-2014] [pdf] PFFF -- Cantor-Zassenhaus algorithm. Coding theory.
[21-Aug-2014] [pdf] PFFF -- Resultant. Reduction to the prime field case.
[18-Aug-2014] [pdf] PFFF -- Berlekamp's algorithm.
[14-Aug-2014] [pdf] Polynomial factorization over finite fields (PFFF) -- equidegree factors.
[11-Aug-2014] [pdf] Fast matrix multiplication.
[07-Aug-2014] [pdf] Fast integer multiplication & division.
[04-Aug-2014] [pdf] Fast polynomial multiplication, over any ring.
[31-Jul-2014] [pdf] Basic arithmetic, Euclid's gcd, Chinese remaindering, asymptotics.
[28-Jul-2014] [pdf] Outline of the course.