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

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?

-
Here's a possible approach to prove that your question is as hard as factoring. Assume that given $N$, it is easy to find a prime $p$ that is $1$ mod $N$. Under this assumption, $N$ can factored easily given the Pratt certificate for this $p$. Now, to the question of computing a $p$ that is $1$ mod $N$. One approach is to simply iterate through $1+iN$ for $i = 0, 1, 2, \ldots$. This algorithm is efficient if and only if the smallest such $p$ is polynomial in $N$. In other words, given $N$, we want to know best bounds on the smallest prime $p=1 \mod{N}$. I am not sure how promising this is. – Srivatsan Sep 5 '11 at 0:53
In second thought, this approach is not that useful. This procedure will be efficient only if the smallest prime is $O(N \ \text{polylog} N)$, which seems extremely unlikely. I originally assumed that it can be $N^{O(1)}$ and we will be fine. That is clearly incorrect. My apologies for misunderstanding. (The other question has been answered by the way. The current bound stands at $O(N^{5.2})$.) – Srivatsan Sep 5 '11 at 2:24
@Srivatsan Narayanan: In light of my new answer to your question, your approach does seem to work, conjecturally at least. You should delete these comments and add them as an answer (perhaps expanded slightly). – Charles Sep 5 '11 at 5:04
– Charles Sep 5 '11 at 16:21

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.

-