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$?


1 Answer 1


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$ Sep 27, 2014 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$ Oct 2, 2014 at 17:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .