This is G o o g l e's cache of http://www.dcc.unicamp.br/~rdahab/cursos/mo637-mc933/Welcome_files/numTheory/WebPages/The%20AKS%20%22PRIMES%20in%20P%22%20Algorithm%20Resource.html as retrieved on Oct 5, 2004 09:07:52 GMT.
G o o g l e's cache is the snapshot that we took of the page as we crawled the web.
The page may have changed since that time. Click here for the current page without highlighting.
This cached page may reference images which are no longer available. Click here for the cached text only.
To link to or bookmark this page, use the following url: http://www.google.com/search?q=cache:_qY8W0GVuOMJ:www.dcc.unicamp.br/~rdahab/cursos/mo637-mc933/Welcome_files/numTheory/WebPages/The%2520AKS%2520%2522PRIMES%2520in%2520P%2522%2520Algorithm%2520Resource.html+aks+algorithm+implementation&hl=en

Google is not affiliated with the authors of this page nor responsible for its content.
These search terms have been highlighted: aks algorithm implementation 
The AKS "PRIMES in P" Algorithm Resource

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

Issues

Content:

Cosmetic:

Classifications of Algorithm Complexities

Soundbytes

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)

Implementations

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:

Future:

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