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$.


That $p$ passes the base-$2$ Fermat test means that the order of $2$ modulo $p$ is a divisor of $p - 1 = 2q$. Since $q$ is a prime, we have $p = 2q+1 \geqslant 5 > 2^2$, so the order of $2$ modulo $p$ must be larger than $2$. This leaves the two options $q$ and $2q$ for the order. In either case, $q$ divides the order, so $p$ must have a prime factor $r \equiv 1 \pmod{q}$. Since $q + 1 < p = 2q + 1 < 2(q+1)$, it is impossible that $q+1$ is a prime factor of $p$. Therefore the smallest candidate for $r$ is $r = 2q + 1 = p$. In other words, it follows that $p$ is a prime. (Note we did not need the assumption that $3 \nmid p$ in this argument, that is only needed for a verbatim application of Pocklington's criterion. If $p$ is a multiple of $3$, it won't pass the Fermat test.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.