PRIMES is in P

This series of talks is not devoted to representation theory. The aim is rather to update our general knowledge as mathematicians, here in complexity theory, where the new discovery (August 2002) is: Primality can be tested in deterministic polynomial time.

Below is a list of talks, each of which is supposed to take about 30 minutes. The first three talks expose the problem of primality testing, give the basic idea and the time complexity analysis of the algorithm of Agrawal, Kayal and Saxena. In the next three talks we prove that the algorithm accepts primes and rejects composites.

Talks

  1. What is PRIMES, what is P, and other FAQ; [1] and [2,(1)]. (Thomas Brüstle)
  2. Basic Idea and the Algorithm; [2,(2) and (4)] or [3]. (Raf Bocklandt)
  3. Time Complexity Analysis; [2,(4.2) and (5.1)]. (Daiva Pucinskaite)
  4. Lemma 4.3 and 4.4 from [2]. (Angela Holtmann)
  5. Lemma 4.5 and 4.6 from [2]. (Andrew Hubery)
  6. Lemma 4.7 from [2]. (Andre Beineke)
  7. Integer factorization and other NP-problems. (Marco Soriano)

References

  1. The PRIMES is in P little FAQ page by Anton Stiglic
  2. Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P
  3. The basic idea of Agrawal, Kayal and Saxena
An excellent resource concerning primes is the Prime Pages where you will find information about
ERH: http://primepages.org/notes/rh.html
Miller's test:   http://primepages.org/prove/prove2_3.html
Adleman-Pomerance-Rumely:   http://primepages.org/prove/prove4_1.html
Goldwasser-Kilian and Atkin:   http://www.utm.edu/research/primes/prove/prove4_2.html
as well as an excellent factorization program using the Elliptic Curve Method:   http://www.alpertron.com.ar/ECM.HTM
+ many more primality algorithms and other prime stuff.

NIST's dictionary of algorithms and data structures http://www.nist.gov/dads/ where you can find definitions for the various complexity classes mentioned here and much more.