Algorithmic Number Theory

642:587, Fall 2020

Course Info

Instructor: Swastik Kopparty (
Class Time and Place: Tuesdays and Thursdays 1:40 am - 3:00 pm, on Zoom
Office Hours: TBD

IMPORTANT: If you are not registered for the course and want to attend, please email me for the zoom link!

Prerequisites: undergraduate level abstract algebra, number theory, algorithms, graduate level mathematical maturity
References: Lovasz (An Algorithmic Theory of Numbers, Graphs and Convexity), various recent papers available online


This course will be an introduction to basic algorithmic number theory (i.e., designing algorithms for number theoretic problems).

There will problem sets. Every one will have to do a project reading a recent paper and producing a writeup of some important theorem from that paper. A list of potential project topics will be put up here soon.

Lecture Schedule

  • September 1: course overview, GCDs
  • September 3: continued fractions, finding the best rational approximation with small denominator
  • September 10: linear algebra, solving systems of linear equations in integers
  • September 15: solving systems of linear equations in integers
  • September 17: solving univariate polynomial equations over the complex numbers
  • September 22: lattice generalities
  • September 24: lattice algorithms, 2 dimensional SVP
  • September 29: technical issues
  • October 1: LLL lattice reduction
  • October 6: LLL lattice reduction, factoring polynomials over rationals
  • October 8: factoring polynomials over the rationals
  • October 13: root finding over finite fields
  • October 15: irreducibility testing over finite fields, construction of finite fields
  • October 20: factoring polynomials over finite fields
  • October 22: factoring bivariate polynomials, power series solutions
  • October 27: square roots mod m
  • October 29: certifying primality, Agrawal-Biswas randomized primality test
  • November 3: Agrawal-Kayal-Saxena deterministic primality test
  • November 5: Agrawal-Kayal-Saxena deterministic primality test, discrete log
  • November 10: Adleman's algorithm for discrete log based on smooth numbers
  • November 12: Lehmann's deterministic algorithm for factoring integers
  • November 17: Dixon's algorithm for factoring integers
  • November 19: FFT, towards fast polynomial multiplication
  • November 24: fast polynomial multiplication, fast integer multiplication
  • December 1: Quantum algorithms, towards fast quantum factoring
  • December 3: fast quantum factoring
  • December 8: class presentations