Re: Primes algorithm

From: Andrew Walker (ajw01_at_REMOVE.uow.REMOVE.edu.au)
Date: 04/26/05 

Date: 26 Apr 2005 10:44:36 +1100

"D. J. Bernstein" <djb@cr.yp.to> writes:

>See http://cr.yp.to/papers.html#prime2004 for a chart showing how fast
>the state-of-the-art primality-testing algorithms are.

>Sebastian Gottschalk wrote:
>> The original AKS had O(n^12) with suggestestions how to improve this
>> to O(n^6) under Sophie-Germain-Prime conjunction and O(n^3) under some
>> additional conjunction. Since then it was improved to O(n^2 log n) under no
>> assumtion.

>No. The original Agrawal-Kayal-Saxena algorithm was faster than 12,
>conjecturally 6+o(1); a subsequent AKS-type algorithm by Lenstra and
>Pomerance is provably 6+o(1); a randomized AKS-type algorithm by me is
>provably 4+o(1). Nobody has done better than 4+o(1), or 6+o(1) without
>randomization.

>For comparison, elliptic-curve primality proving is conjecturally 4+o(1)
>and seems to have a slightly smaller o(1) than the AKS-type algorithms.

>None of these algorithms are competitive with the 2+o(1) achieved by
>Rabin's compositeness proofs, not to mention the slightly faster 2+o(1)
>non-proof methods used in practice.

I'd be interested to know what the record is for a primality proof
using a proven AKS or AKS type method. From memory someone got up
to a few hundred digits, but that was a while back.

Also have any of the methods which had assumptions benn shown true or false?

Andrew Walker

Quantcast