[Please remove <h1>]

---

Objectives

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.

References

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

Schedule

Three hours of lecture per week.

Outline

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.