math/big: AKS Test for Int.ProbablyPrime

[pjebs]

There seems to be a relatively new test that is 100% correct:

It's called the AKS Test: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

More Info: https://www.youtube.com/watch?v=HvMSRWTE2mI

[mvdan]

The current test has been changed recently, see 37d078e.

Would switching to this test make the method noticeably slower?

cc @rsc @griesemer

[dgryski]

It appears that AKS is substantially slower in practice than BPSW: https://cs.stackexchange.com/questions/23260/when-is-the-aks-primality-test-actually-faster-than-other-tests

[mvdan]

I wonder if 100% correctness is useful for a method that is called ProbablyPrime, especially if it comes at such high performance cost.

[pjebs]

There is a simplified version of the test highlighted at 2:10 in the youtube video. In the simplified version, it is faster at the expense of some accuracy (I think it's called Lenstra/Pomerance improved AKS).

The AKS test is a deterministic test. The Miller and BPSW are probabilistic tests. That's the main reason why they are faster - at the expense of some possibility of inaccuarcy.

[pjebs]

According to this: http://probableprime.org/images/primality-times.png, AKS test is crap in practice.

[ALTree]

The algorithm is only interesting from a theoretical point of view (deterministic primality test in polynomial time was a breakthrough); I don't think anyone uses AKS in practice.

Also it would be quite strange to use a deterministic method for a function called ProbablyPrime : )

Closing this.

[rsc]

For me the main reason to add BPSW was that there were easy-to-find inputs that ProbablyPrime was demonstrably (and consistently) wrong about. For example, big.NewInt(443*1327).ProbablyPrime(1) == true before that change.

If you can find inputs that the current test gets wrong but that AKS gets right, I'd be happy to look into changing the implementation. And lots of others would be interested too: there are no known counterexamples to BPSW.

[danaj]

The Youtube video is very misleading in a number of ways. What it describes is a preliminary lemma of AKS that is obviously horrendously slow. Worse than the most naive trial division by every integer up to n-1. The real AKS is certainly better than that, but it is still much slower than some other known proof methods, even after improvements by Lenstra, Pomerance, Voloch, Bernstein, et al.

BPSW if implemented correctly has no counterexamples under 2^64. No probably about it. You can extend this using deterministic Miller-Rabin to something like 80 bits. So we'd definitely not care about this until that point.

If you really want something better, I'd recommend one of

• Add additional probable prime tests for numbers larger than the deterministic threshold. E.g. Frobenius and/or random-base Miller-Rabin tests.
• APR-CL
• ECPP

The latter two tests are also 100% correct. APR-CL has a smaller exponent than the current best deterministic AKS for any number computable within the next 100 years.