# Is there any infinite set of primes for which membership can be decided quickly?

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