Mahler Lecture 2003

Galois theory and primality testing

Hendik Lenstra Jr. (AustMS Kurt Mahler Lecturer 2003)

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

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.

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).

Back to main page