Series: Mathematics Colloquium

Date: Thursday, December 11, 2003

Time: 4:00 - 5:00 PM

Place: 102 McAllister Building

Host: Robert Vaughan

Refreshments: 3:15 - 4:00 PM, in McAllister Basement

Speaker: Carl B. Pomerance, Dartmouth College

Title: Recent Developments in Primality Testing

Abstract:  

In August of last year, M. Agrawal, N. Kayal, and N. Saxena, all from
the Indian Institute of Technology in Kanpur, announced a new
algorithm to distinguish between prime numbers and composite numbers.
Unlike earlier methods, theirs is completely rigorous, deterministic,
and runs in polynomial time.  The heart of their test to see if n is
prime involves verifying some identities (x+a)^n = x^n+a in the ring
Z[x]/(n,f(x)).  Here a runs over a small set of integers and f(x) is a
polynomial with integer coefficients.  In the original paper f(x) is
of the form x^r-1, where r is a prime with some additional
properties.  We have found a way to instead use the polynomial for an
appropriate subfield of a possibly large cyclotomic field.  The
construction uses Gaussian periods, the same objects that Gauss
studied in his Euclidean construction of regular n-gons.  It is
important that the degree of f(x) be large enough so that the
primality test is valid, but not so large that the running time
suffers.  We are able to choose the degree fairly precisely using some
tools from analytic number theory and a new result, due to
D. Bleichenbacher and V. Lev, from combinatorial number theory.  We
thus achieve a rigorous running time of about (log n)^6, the
heuristic complexity of the original test.  This is joint work with
Hendrik Lenstra.