MHT 933 : Computational Number Theory



The course uses classical and modern factorization algorithms to present important ideas and techniques in computational number theory. We will cover the reduction of Z-modules and lattices, factorization of univariate polynomials over finite fields, the rationals and the complex numbers, then primality testing (up to the Elliptic Curve Primality Proving algorithm) and integer factorization (up to the Number Field Sieve). We will also study some algorithms in number fields, essentially those leading to the computation of the ring of integers, the units and the class group. The emphasis is on important ideas throughout, as opposed to technical details necessary for efficient implementation, and asymptotically fast methods.