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?
|show 1 more comment|
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.