Mahler Lecture 2003

Galois theory and primality testing

Hendrik Lenstra Jr. (AustMS Kurt Mahler Lecturer 2003)

Friday, June 20, 2pm
Carslaw 373, University of Sydney

Abstract: It was recognized in the mid-eighties, that several then current primality tests could be formulated in the language of Galois theory for rings. This made it possible to combine those tests for practical purposes. It turns out that the new polynomial time primality test due to Agrawal, Kayal, and Saxena can also be formulated in the Galois theory language. Whether the new formulation will allow the test to be combined with the older tests remains to be seen. It does lead to a primality test with a significantly improved guaranteed run time exponent. In this test, one makes use of Gaussian periods instead of roots of unity. The lecture represents joint work with Carl Pomerance (Bell Labs).

While featuring in the Workshop Computational Arithmetic Geometry, this lecture is aimed at a general mathematical audience. Also people who do not participate in the workshop are invited to attend.

This announcement is also available as an A4 sized poster, both in postscript and in PDF format.

Back to main page