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

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




Classifications of Algorithm Complexities


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

Introductory level write-ups

(Popular - accessible to all)


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




Prime Proving in General

Miscellaneous other AKS information sources

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

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