21

I am writing an implementation of a cryptography protocol. So far I've been having a difficult time finding the fastest deterministic primality test for 1024-bit to 4096-bit integers (308- to 1233-digit numbers). I am aware of several options but I have not been able to find real world speed comparisons.

Specifically, how does the AKS test perform compared to the deterministic version of Rabin-Miller and the Elliptic Curve Primality Proving test (and others) for general random numbers this size ?

jnm2
  • 7,960
  • 5
  • 61
  • 99
  • This is an interesting post : http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2 – Ricky Bobby Jun 10 '11 at 16:35
  • 4
    You don't need deterministic primality tests for public key crypto - existing solutions don't use them. Almost-certainly-primes are generally sufficient. Of course, you probably shouldn't be implementing your own crypto primitives anyway, if you can avoid it. – Nick Johnson Jun 11 '11 at 07:46
  • 1
    AKS will be _very much worse_ than ECPP, which will be _very much worse_ than Miller Rabin. Note that Miller Rabin can make errors but the others can't. For crypto, Miller Rabin is generally sufficient. – user448810 Aug 18 '15 at 21:05
  • Your computer has a finite (though small) chance of failing and giving an incorrect answer. As long as the probability of a non-deterministic algorithm failing and giving the wrong answer is smaller than the chance of your hardware giving the wrong answer, then a non-deterministic answer will be fine. Bruce Schneier calls them "industrial strength primes". the chance of them not being prime is small enough to ignore for all practical purposes. – rossum Aug 18 '15 at 21:09

3 Answers3

11

This article is answering your question:

PRIMALITY TESTING by Richard P. Brent: http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf

It compares in complexity and in "real world speed" the 3 algorithms.

Adam Stelmaszczyk
  • 19,665
  • 4
  • 70
  • 110
Ricky Bobby
  • 7,490
  • 7
  • 46
  • 63
  • +1 Awesome. It leaves me curious about Las Vegas algorithms. It seems preferable to have a certificate in probably-good time, than to have a probable prime in guaranteed time. – phkahler Jun 10 '11 at 13:51
  • There's just one thing I still don't know: how do they compare to the _deterministic_ version of Rabin-Miller? – jnm2 Jun 10 '11 at 21:14
  • 1
    https://web.archive.org/web/20110414142105/http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf – Will Brickner Apr 25 '16 at 07:28
5

I'm new, so i can't comment on the above link, but here is the internet archive link to that article:

https://web.archive.org/web/20110414142105/http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf

Dan K
  • 71
  • 1
  • 3
4

The fastest proof methods for this size would be APR-CL (e.g. mpz_aprcl) and ECPP (e.g. Primo or ecpp-dj). APR-CL is deterministic and almost polynomial time, while ECPP is randomized but the answer returned is proven, not probabilistic. Alternately, use a constructive method for proven primes such as Maurer's methods or Shawe-Taylor. These are methods for quickly generating random n-bit primes created by building up Pocklington-style proofs. From a practical point of view, if you are generating the random candidates rather than receiving them from a third party then the error rates for Miller-Rabin are extraordinarily low, and almost all people in this case are satisfied with multiple Miller-Rabin tests using random bases, possibly with a strong Lucas test in addition. See FIPS 186-4 for lots of info on constructive methods and recommendations for probable prime testing.

Times are shown in this graph for a selection of random n-digit primes run through trial division, BPSW (an efficient probable prime test), two versions of AKS, APR-CL, and ECPP. This shows how AKS compares to the other methods.

I didn't add deterministic M-R as I assume you're not talking about 64-bit inputs, and over that you have to either test n/4 bases or prove the Riemann Hypothesis so you only have to test 2*log^2(n) bases. Neither one is attractive compared to our other options even if you use the latter without a proof. In practice the Bach version is faster than AKS as expected, but noticeably slower than ECPP and APR-CL in my tests with C+GMP. I haven't looked at asymptotics, but at 300 digits it is over 100x slower. Hence I don't see any point vs. APR-CL (Det M-R is slower) or ECPP (Det M-R is slower and ECPP gives you a certificate to boot).

Brent's paper can be found in this UMS10 version from 2010 as well as a similar version from 2006. It basically agrees with what I've found from more modern implementations in C+GMP of the various algorithms. AKS is a landmark theoretical result, but is of no current practical use.

DanaJ
  • 724
  • 6
  • 9