Tentative content

Some basic set up

• A quick introduction to notions of rings, fields
• Structure and properties of finite fields

Algorithms for polynomial arithmetic

• Euclidean algorithm for GCD of univariate polynomials
• Resultants and their properties
• Zeroes of a low degree polynomial - Schwartz-Zippel lemma, notion of multiplicities
• Fast Fourier Transform, and application to polynomial division, fast univariate multipoint evaluation

Algorithms for some basic number theoretic problems

• Euclid's algorithm for integer GCD, fast integer multiplication
• Continued fractions, rational approximations, Dirichlet's theorem
• Finding integer solutions of linear systems

Polynomial factorization over finite fields

• Univariate polynomial factorization over finite fields - Berlekamp's and Cantor-Zassenhaus' algorithms
• Bivariate polynomial factorization - Newton iteration and Hensel Lifting

Lattices

• Basics of lattices over integers, Minkowski's theorems
• LLL algorithm for approximating the shortest vector over a lattice
• Univariate polynomial factorization over rationals - approximating complex roots of univariates, factorization via LLL
• Coppersmith's algorithm for finding small integer roots of a monic univariate modulo a composite
• Lattices over the univariate polynomial ring (possible applications - Cohn-Heninger algorithm for decoding RS codes)

Primality testing

• Pratt's certificate for primality
• Randomized primality tests - Solovay-Strassen, Agrawal-Biswas
• Deterministic primality test - Agrawal-Kayal-Saxena Primality test

Integer factorization

• Randomized algorithms for factoring integers
• Deterministic integer factoring algorithms

Other interesting things that we might not have time for

• Multivariate multipoint evaluation over finite fields and data structures for polynomial evaluation
• Subspace polynomials and some applications
• Basics of elliptic curves
• Kalai's algorithm for generating randomly factored integers
• Multivariate factorization, Kaltofen's theorem and Hilbert's irreducibility theorem
• Algebraic independence and Jacobian
• Linear independence, Wronskians and Alternants