The AKS "PRIMES in P" Algorithm Resource

(Apologies to those incorrectly blocked, by the way.) Things relevant to the AKS algorithm - little original content - mainly links.
| Analyses | Improvements | Issues | Complexity | Soundbytes | Intros | Implementations | Presentations | Primes | Miscellany |

Recent changes:
2005/08/13 - (Woh! Where's time gone?) Another implementation added.
2003/05/12 - Capitalised PRIMES where appropriate. It not shouting, it's correct.
2003/05/07 - (Woh! Where's time gone?) One analysis, one improvement, two presentations, and 2 new implemetations added.
2003/03/19 - Removed these pages from half of the internet.

AKS Algorithm Descriptions

• AKS 'PRIMES is in P' home page with the original paper, and the revised 'v3' paper. [l.u. 2003/03/04]
• Francois Morain's analysis
• Professor Caldwell's Prime Pages
• Bhattacharjee and Pandey's background on Conjecture 4 ([BP01] in the AKS paper)
• Michiel Smid's thorough proof of correctness with all the background material required. If you only read 1 paper, read this one.
• Madhavan Makund's proof. To appear in BULLETIN OF THE EATCS 78, October 2002 (http://www.liacs.nl/~beatcs/toc/beatcs78.txt)
• Carl Pomerance's lecture on primality proving. [new 2003/04/07]
• Folkmar Bornemann's "A Breakthrough for Everyman". Very thorough history of the breakthrough, [new 2003/05/07]

Improvements on the Original AKS algorithm

1. Note - Agrawal, Kayal,and Saxena incorporated some of these improvements in their 'v3' revised paper (see above).
2. Dan Bernstein's analysis (includes Lenstra's, Poonen's and Voloch's improvements) [l.u. 2003/01/21]
3. Felipe Voloch's improvement
4. Pedro Berrizbeitia's "Sharpening Primes is in P"
5. Dan Bernstein's ``Proving primality in essentially quartic expected time'', which generalises Berrizbeitia's improvements. (Note, this is a randomized algorithm, unlike original AKS.) [new 2003/01/29]
6. Qi Cheng's "Primality Proving via One Round in ECPP and One Iteration in AKS" hybrid building on Berrizbeitia's work for randomised O~(d^4) time (certificate finding, O(d^4) to verify).

Issues

Content:

• In the original AKS paper, the authors cite Fouvry as refering to |{p|p is prime, p<=x and GPF(p-1)>x^(2/3)}|
  Whereas others (Pomerance) cite it as refering to |{p|p is prime, p<=x and GPF(p-1)>p^(2/3)}| for GPF=greatest prime factor. Refering to a copy of Fouvry, didn't make it clear which was correct.
  NB: This is changed in the 'v3' revision of the paper, AKS and Pomerance are in accord. [l.u. 2003/03/04]
• Conjecture 4 not true as stated. Conjecture 4 is not required for the validity of the algorithm as a whole, it merely offers a dramatic speed increase, a much smaller Big-Oh. Easily fixable, through a simple restatement.

• The numbering of the conjectures has caused some confusion. Conjecture 4 is in section 6.
• Oh, it's also now (in the 'v3' paper) become Conjecture 5 :-| [new 2003/03/04]

Classifications of Algorithm Complexities

• Paul Leyland's analysis
  (Obsoletes Paul's UK Crypto posting.)
• Anton Stiglic's FAQ

Soundbytes

I.e. renouned mathematicians who have implicitly or explicitly indicated that they agree with the validity of the proof.

• Dan Bernstein
• Carl Pomerance
• Bob Silverman
• Hendrik Lenstra
• Fabricated dissent, however, from Noam D. Elkies : "AKS? Demon lie!" (no it's not a quote, it's an anagram of his name I just concocted!)

Introductory level write-ups

(Popular - accessible to all)

• India's "Frontline" Magazine - lots of info - recommended.
• Mathworld's fluffy overview (wrong in places)
• Ivars Petersen brief introduction for ScienceNews.[new 2003/02/20]
• Society for Industrial and Applied Mathematics. Thorough introduction by Sara Robinson. [new 2003/03/07]

Implementations

• Yves Gallot : C++ / various : AKS+DB
  • No bigum dependencies
  • Using GMP library
  • Using NTL library
  • Using Miracl library
• Michael Scott : C++ / Miracl : Conjecture 4
• Medhi Tibouchi : Pari/GP : AKS - perfect powers
• Allan K. Steel : Magma : AKS
• Peter Luschny : Maple : AKS+DB +(opt) Germain Conjecture +(opt) Conjecture 4
• Aldo D. : UBasic : Conjecture 4 , local mirror
• Christiano : C++ / Miracl : Conjecture 4
• Folkmar Bornemann : GP/Pari : AKS [new 2003/05/07]
• Crandall : C : AKS+HL
  Plus: Full implementation notes [new 2003/05/07]
• Lasse Nielsen : C++ / GMP : AKS
  Accompanies a batchelor's thesis on the subject - mostly in Danish. [new 2005/08/13]

Notes:
"HL" and "DB" refers to the improvements made by Henrik Lenstra and Professor Bernstein in papers linked to above.
+(opt) means that there's a choice of whether to use the following conjectures:
"Germain Conjecture" means assuming the truth of the conjecture stated in section 5 of the AKS paper, and explained further in AKS's [HL22] reference. Similarly "Conjecture 4" means assuming the truth of the conjecture stated in section 6 of the AKS paper, and explained further in AKS's [BP01] reference. See the AKS paper linked to above.

Presentations

Past:

• Notes - Dan Bernstein's Santa Barbara Presentation (v. brief, just the formulae)
• Announcement - Exploration - Can similar principles be used for Factoring AIM workshop to explore problems related to fast factoring of very large numbers. March 24-28 2003.
• Notes - Michael Jacobsen's Exposition. For a presentation, very full of details, but like all such notes tending to be a bit dry. [new 2003/05/07]
• Notes - George Gilbert's presentation. Has all the details from the ground up, and not the typical dry presentation style.

• Announcement - Manindra Agrawal's Special Lecture - "A Polynomial-time Algorithm for Primality Testing", Fields Institute, University of Toronto, May 23, 2003 -- 3:30 pm.

Prime Proving in General

• The Prime Pages
• Miller's Test
• APR - Adleman-Pomerance-Rumely
• ECPP - Goldwasser-Kilian and Atkin
• AKS - Agrawal-Kayal-Saxena
• All of the above
• Scott Aaronson's "Prime Facts" aimed at sparking an interest in primes in younger readers. I think it was delivered to pre- or just-teens, but it does't aim low.

Miscellaneous other AKS information sources

Alas, no direct URLs for the payloads here, but hopefully enough information to find paper versions.

• Actaully, I have URLs for everything currently!

Thanks, for the pointers and contributions, guys:
*_Peter Luschny_* (an absolute star! Peter - drop me a mail, wanadoo just bounced my most recent "thank you"), Anton S., Paul L., Yves G., Medhi T., Alan S., Alexander R., Scott Aaronson, Professor Bernstein, Aldo, Nathan R. and of course to Agrawal, Kayal, and Saxena themselves. Oh, and apologies to Noam for jokingly besmirching his good name with the anagram!

You are visitor N+1, where N is the number of visitors before you.
B0rken HTML courtesy of the web-authoring tool 'Pico' :-)

Home/ Maths/ AKS/ index.html