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.

Campaign Waterloo

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

Valid HTML 4.01!Valid CSS! Last modified: Friday, 01-Jun-2012 11:00:32 EDT