If $p=2q +1$ with $p,q$ prime then $p$ is called safe prime and $q$ is a Sophie Germain prime. I want a faster algorithm for a safe prime test than doing two primality checks for $p$ and $q$.
In http://en.wikipedia.org/wiki/Safe_prime you find the hint: However, Pocklington's criterion can be used to prove the primality of 2p+1 once one has proven the primality of p.
Are this statement and it's proof correct?
If $p=2q+1$ with $q\,$ prime and $p\,$ passes the Fermat primality test to base $2$, $p \not \equiv 0 \pmod 3$, then $p\,$ is prime.
Proof: We have the following three facts
1) $q$ is prime, $q | p-1,\;$ and $q > \sqrt{p}-1$
2) $2^{p-1}\equiv 1 \pmod p\;$ because $p$ passes the Fermat primality test to base $2$. And
3) $\gcd(2^{(p-1)/q}-1,p)=\gcd(2^2-1,p)= \gcd(3,p) = 1\;$ because $p$ is no multiple of $3$.
Therefore $p$ is prime according to the Pocklington_criterion.
Update: I added the condition $p \not \equiv 0 \pmod 3$ because otherwise the GCD in 3) is not necessarily $=1$. In the practical implementation this is done while sieving for $p$.