Future directions in algorithmic number theory

March 24 to March 28, 2003

at the

American Institute of Mathematics, Palo Alto, California

organized by

Hendrik Lenstra, Carl Pomerance, and Jonathan Pila

Original Announcement

This workshop is occasioned by the breakthrough result of Agrawal, Kayal and Saxena devising an unconditional, deterministic, polynomial-time algorithm for distinguishing prime numbers from composite numbers. The solution of one of the basic problems in the discipline ushers in a new era. The main objective of the workshop is to consolidate the breakthrough and explore ramifications for other fundamental algorithmic problems in number theory and finite fields. In addition the workshop will look to the future of the subject and chart directions in which developments might occur.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

Lecture Notes:

  1. Agrawal: Primality Testing
  2. Agrawal: Finding Quadratic Nonresidues
  3. Bernstein: Proving Primality After Agrawal-Kayal-Saxena
  4. Edixhoven: Point Counting
  5. Gao: Factoring Polynomials under GRH
  6. Kedlaya: Counting Points using p-adic Cohomology
  7. Lauder: Counting Points over Finite Fields
  8. Lenstra: Primality Testing with Pseudofields
  9. Pomerance and Bleichenbacher: Constructing Finite Fields
  10. Silverberg: Applications of Algebraic Tori to Crytography
  11. Stein: Modular Forms Database
  12. Voloch: Multiplicative Subgroups of a Finite Field
  13. Wan: Partial Counting of Rational Points over Finite Fields
Remarks on Agrawal's Conjecture