Synopsis for Computational Number Theory

Prerequisites

Despite the sophistication of this course the only pre-requisites are parts of a standard elementary number theory course: Euclid's algorithm, Quadratic residues, The law of reciprocity for Legendre and Jacobi symbols, Fermat's theorem, primitive roots.

Aims and Synopsis

This course aims to describe the algorithms used for efficient practical computations in number theory. It is based on recent research papers, along with parts of the text by Cohen. The course covers: The Euclidean Algorithm, computation of powers and square roots modulo primes; the arithmetic of elliptic curves over finite fields; lattices and the LLL reduction algorithm; factorization algorithms.

Henri Cohen, A course in com­pu­ta­tional al­ge­braic num­ber theory, Springer-Verlag (1993).