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.
Addition, subtraction, multiplication, division, greatest common divisor, perfect power testing, computations in Z_n^*.
Representation, arithmetic, polynomial factorization, irreducibility testing.
Pseudoprimes, Solovay-Strassen, Miller-Rabin, Adleman-Pomerance-Rumely, Goldwasser-Kilian-Atkin, and ERH-based methods.
Elliptic curve method, continued fraction method, quadratic sieve, number field sieve, Pollard rho.
Class groups, composition, computation of regulator.