Can a Pratt certificate for a prime be found in polynomial time?

Question

Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. If unknown, can it be shown to be no easier than integer factorization in general, or is that itself unknown?

Answer 1

Basically, your question boils down to: does knowing that $n+1$ is prime make factoring $n$ easier?

I don't have a proof, but the answer is very probably no.

• One approach is that of Srivatsan: fix an arbitrary $n$ and find the smallest $k$ such that $nk+1$ is prime. Unfortunately there does not seem to be a proof that the worst-case $k$ is polynomial in $\log n$, even if it is supected to be true.

• A modification of this approach that might be more fruitful is to consider the prime counting function $\pi_{n,1}(x)$, that is the number of primes of the form $nk+1$ that are no greater than $x$. The prime number theorem for arithmetic progressions says that asymptotically $$\frac{\pi_{n,1}(x)}{x}\sim \frac{1}{\phi(n)}\frac{1}{\log x}$$ If we somehow manage to prove that this asymptotic bound can be approached "quickly enough", that is if for some exponents $a$ and $b$ we have $$\frac{\pi_{n,1}(n^a)}{n^a}\ge \frac{C}{\phi(n)(\log n)^b}$$ then by picking $k$ at random in the interval $[1,n^{a-1}]$ and checking if $nk+1$ is prime, we will only need $O((\log n)^b)$ tries on average to find a polynomial-sized reduction of integer factorization to your problem. So in such a case we can say that if there is no randomized polynomial-time algorithm for integer factorization, there is no randomized or deterministic polynomial-time algorithm for your problem.

• Finally a somewhat different approach is to consider the semiprimes $pq$ such that $2pq+1$ is prime. The assumption that picking large $p,q$ at random gives a hard to factor $pq$ with very high probability is at the heart of the RSA cryptosystem (some standards define a notion of "strong primes", but cryptographers tend to think it brings little additional security compared to random primes). But it seems that $2pq+1$ has a rather high probability of being prime (apparently higher than a random comparably-sized number, which is expected since it is always an odd number). I don't know if it can be proven, but at any rate this is experimentally true for typical RSA sizes. This would imply that a large fraction of the keys would be vulnerable to factoring if your problem was tractable.