The AKS algorithm decides whether or not $n$ is prime in time $\tilde{O}((\log{n})^6)$. I am wondering if there is any faster algorithm to determine membership in some infinite set of primes.

What I have tried:

The Lucas-Lehmer test for Mersenne primes runs in $\tilde{O}((\log{n})^2)$, but we cannot prove there are an infinite number of Mersenne primes.

We could find and verify a Pratt certificate, for example if $n-1$ is easy to factor (perhaps it is $\log{n}$-smooth), and $a=2$ works, then this takes time $\tilde{O}((\log{n})^3)$. But I don't know how to prove there are an infinite number of cases where $n$ is prime and these conditions are satisfied.

The AKS algorithm can also return quickly in some cases (if $r$ is small) but again I am unable to show this happens infinitely often for prime $n$.

The Miller-Rabin test runs in $\tilde{O}((\log{n})^4)$ but this requires GRH.

We cannot possibly do better than $O(\log{n})$ since all bits of the input must be inspected.

How can we define an infinite set of primes and a decision algorithm for it that runs in time $O((\log{n})^k)$ for some $k \lt 6$?


This is not really my answer. Being vastly ignorant on such matters, I asked Carl Pomerance who replied :

Pintz, Steiger, and Szemeredi did this some time ago, and a paper of mine with Konyagin went further. This is all pre-AKS. My paper with Konyagin is #111 on my home page, and the PSS paper is referenced. Basically all you want are primes p with a large smooth divisor of p-1.

Best wishes, Carl

  • $\begingroup$ math.dartmouth.edu/~carlp/PDF/110.pdf $\endgroup$ – Dan Brumleve Sep 27 '14 at 9:07
  • $\begingroup$ This is awesome, although the algorithm is said to run in $\tilde{O}{(\log{n})^{16}}$ which is not as good as I am hoping for, I like to think that it is evidence that something faster than AKS for some infinite subset is not out of reach. $\endgroup$ – Dan Brumleve Oct 2 '14 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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