Instructor: Swastik
Kopparty (swastik.kopparty@gmail.com)

Class Time and Place: Tuesdays and
Wednesdays, 5:00pm – 6:30pm, in Hill 124

Office Hours: Wednesday 1:30-2:30
(Hill 432)

Prerequisites: undergraduate level
abstract algebra, mathematical maturity.

References: various online sources,
scribe notes.

__Syllabus__

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

Topics include:

·
Primality
testing

·
Lattices
and Diophantine approximation

·
Integer
factorization

·
Computing
discrete logarithms

·
Undecidability of solving Diophantine equations

·
Polynomial
factorization

·
Elliptic
curve algorithms

·
Number
field algorithms

·
The
complexity of algebraic computation

Students will take turns scribing
the lectures, and the notes will be put up here. There will be 1-2 problem
sets.

Latex files for scribes: definitions, main file,
guidelines.

__Homework__

·
Homework
1 (due November 19)

__Lecture Schedule__

·
September 2:
course overview, Euclid’s algorithm, continued fractions (notes)

·
September 3:
continued fractions, rational approximation (notes)

·
September 9:
finding integer solutions to systems of linear equations (notes)

·
September 10:
finding complex solutions to univariate polynomials (notes)

·
September 16:
lattices, lattice reduction (notes)

·
September 17: the
LLL algorithm for lattice reduction (notes coming soon)

·
**September 23: NO CLASS (make-up class to be
scheduled)**

·
**September 24: NO CLASS (make-up class to be
scheduled)**

·
September 30:
polynomial factorization over rationals, finite field
basics (notes coming soon, see these related notes)

·
October 1: finding
roots of univariate polynomials over
finite fields (notes)

·
October 7:
factorization of univariate polynomials over finite fields (notes)

·
October 8:
deterministic factorization over finite fields (notes)

·
October 14:
multivariate factorization (notes)

·
October 15:
multivariate factorization continued, square roots mod m (notes coming soon)

·
October 21: square
roots mod p^{k}, the multiplicative group of Z_{m}, certifying primality (notes coming soon)

·
October 22:
randomized primality testing, deterministic primality testing (notes)

·
October 28:
deterministic primality testing continued (notes)

·
October 29:
discrete log

·
November 4:
discrete log continued, integer factoring

·
November 5:
integer factoring continued

·
November 11:
generating random factored integers

·
November 12:
elliptic curve basics

·
November 18: Schoof’s algorithm for point counting on elliptic curves, application
to square roots mod a prime

·
November 19:
finding small roots of polynomial congruences

·
**November 25: NO CLASS (Thursday Schedule)**

·
**November 26: NO CLASS (Friday Schedule)**

·
December 2: fast
Fourier transform, fast integer and polynomial multiplication

·
December 3: fast
integer and polynomial multiplication continued

·
December 9: undecidability of solving Diophantine equations

·
December 10: undecidability of solving Diophantine equations continued,
course wrap-up

·
**December 11: MAKEUP CLASS: Fast quantum
algorithms for integer factorization.**