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.

David R. Cheriton School of Computer Science

University of Waterloo

Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293

Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics