Title: Primality testing
Speaker: Hendrik Lenstra
Summary
In the summer of 2002, three Indian computer scientists showed
that there exists a deterministic polynomial time algorithm that
tests a given integer for primality. Their algorithm allows an
algebraic formulation, which reveals a connection with another
fundamental computational problem, namely, the problem of
constructing finite fields. This insight leads to a significant
improvement in the Indian primality test, both from a practical
and from a theoretical perspective.
Prerequisites
Elementary number theory and basic abstract algebra. A number
of results from computer algebra, algebraic number theory, and
analytic number theory may be taken for granted.