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

prime-numbers algorithms number-theory computational-complexity

Solution 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

Related

Generalized FoxTrot Series $F(a,b,q,x) = \sum_{k=q}^{\infty} \dfrac {(-1)^{k+1} k^a}{k^b+x}$
Hartshorne II prop 6.9
How to prove the inequality $ \frac{a}{\sqrt{1+a}}+\frac{b}{\sqrt{1+b}}+\frac{c}{\sqrt{1+c}} \ge \frac{3\sqrt{2}}{2}$
If $a$ is a quadratic residue modulo every prime $p$, it is a square - without using quadratic reciprocity.
Altering an Enum field using Alembic
What's the minimal structure needed to define a notion of derivative?
Prove that any subfield of $\mathbb C$ must contain $\mathbb Q$
Show that $A[X]/(aX+b)$ is an integral domain
Definition of "descends to"
Number of finite extensions of $p$-adic number field of given degree $n$
Number theory: $a\in A\iff \frac{1}{2}-a\in A$.
How to modify an extension from the Chrome Web Store? [closed]