CS 765 Algorithmic Number Theory


To examine the fundamental problems of elementary and algebraic number theory (e.g., primality testing, integer factorization) from an algorithmic and computational complexity point of view. Emphasis is placed on analysis of algorithms.


Algorithmic Number Theory, by E. Bach and J. Shallit, MIT Press, 1996.


Three hours of lecture per week.


Basic Algorithms (6 hrs)

Addition, subtraction, multiplication, division, greatest common divisor, perfect power testing, computations in Z_n^*.

Finite Fields (6 hrs)

Representation, arithmetic, polynomial factorization, irreducibility testing.

Primality Testing (9 hrs)

Pseudoprimes, Solovay-Strassen, Miller-Rabin, Adleman-Pomerance-Rumely, Goldwasser-Kilian-Atkin, and ERH-based methods.

Integer Factorization (9 hrs)

Elliptic curve method, continued fraction method, quadratic sieve, number field sieve, Pollard rho.

Algorithms in Number Fields (6 hrs)

Class groups, composition, computation of regulator.