1
$\begingroup$

It is clear that AKS primality proving is the newest one, but as the results show it is not the fastest one.

When I try the 9 digits long prime number it consume about 6 minutes to give you the result.

Are there any modifications to make it faster for large random primes in size above 200 digits?

The problems in the AKS are:

  1. Euler phi function
  2. Binomial congruence
Improve this question
$\endgroup$
2
  • $\begingroup$ AKS's paper is not the newest one. There's been a bunch of follow-on research that shows how to make the AKS algorithm somewhat faster. What research have you done? Have you looked on Google Scholar? What have you found so far? For instance, the Wikipedia article on the AKS algorithm already provides citations to a bunch of follow-up work from 2002, 2003, and 2005 that provides some speedups. If your question is already answered in the natural place on Wikipedia, it's worth doing more research before asking next time. $\endgroup$
    – D.W. ♦
    Nov 26, 2016 at 18:42
  • $\begingroup$ thank you DW , im asking if there is any modification for binomial congruence like by replacing it with linear recursive sequence $\endgroup$
    – Ramez Hindi
    Nov 28, 2016 at 8:53

1 Answer 1

Reset to default
1
$\begingroup$

There are a number of modifications, but none of the improvements I'm aware of will get it remotely close to the speed of ECPP or APR-CL. For random 100-digit primes, the times for the fastest codes I'm aware of are:

  • 246 days (estimated) AKS v6 paper
  • 45 hours (estimated) AKS Bernstein + Voloch + Bornemann
  • 2.6 hours AKS Bernstein theorem 4.1
  • 0.042 seconds APR-CL (WraithX 1.1)
  • 0.04 seconds APR-CL (Pari/GP 2.7.0)
  • 0.029 seconds ECPP (ecpp-dj 1.03)
  • 0.20 seconds ECPP (Primo 4.1.0 single thread)

At 500 digits, ECPP and APR-CL are in the 9-15 second range. AKS would take years, albeit we could trivially parallelize or distribute it.

I haven't seen anything that gives better improvements than Bernstein's 2003 paper while not being a complete rework such as adding randomization. The growth rate in practice comes out to $O(\log^{6.03} n)$ (there's almost certainly more than 0.03 variance in measurements, but the point is that it's very close to the ideal exponent of 6). Ricky points out that Lenstra Jr. and Pomerance are still actively publishing theoretical improvements, tightening the proven exponent.

The time taken at more than very small input sizes is almost entirely in the congruence test. There really should be very little time spent selecting the 'r' and 's' parameters, though it's possible to see it be non-trivial. For the congruence tests, Bernstein has a paper describing some of the methods that can be used to speed this up, and the implementations shown above use binary segmentation in GMP, as he suggests. You can see the implementation I used for timing at https://github.com/danaj/Math-Prime-Util-GMP/blob/master/aks.c, with various algorithms available.

There isn't any reason to use AKS in practice at any input size, given open source implementations of more efficient algorithms, not to mention Primo for use on large inputs. ECPP gives certificates as well, which is a huge advantage.

http://probableprime.org/images/primality-times-v3.png

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ As far as theory goes, I believe this is the best that's currently free online. ​ (There's a more recent version from this month, which "is submitted for publication.".) ​ ​ ​ ​ $\endgroup$
    – user12859
    Dec 25, 2016 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.