# Checking safe primes

I am in need of a fast algorithm that checks if a given number is a safe prime.*

Any help on this would be appreciated.

*Definition: A safe prime is a prime number of the form $2p + 1$, where $p$ is also a prime.

-
I suggest that you include the definition of safe prime here, or a link to an outside source... but the definition here would be best to make the question self-contained. – Álvaro Lozano-Robledo Aug 20 '11 at 0:58
I have added the definition of a safe prime to the question, thanks for the feedback. – Chris Smith Aug 20 '11 at 0:59
The simplest approach would be to apply any fast primality test to $n$ and, if that succeeds, to $(n-1)/2$; is there any reason not to use this approach? – Brian M. Scott Aug 20 '11 at 1:08
Is there a fast primality test that determines if a number is prime (not probably prime)? – Chris Smith Aug 20 '11 at 1:13
@Chris It would help to clarify if you are interested in searching for safe primes or, rather, for verifying a given probable safe prime. I answered the former. – Bill Dubuque Aug 20 '11 at 1:50

One easily obtains a $25$-times speedup over incremental search algorithms for $512$-bit safe primes. For example, see section $4.2$ in Joye and Paillier: Fast Generation of Prime Numbers on Portable Devices: An Update. 2006.

-
So there is a speedup in safe prime searching, and a good one, over naive double primality testing. Nice to know. – anon Aug 20 '11 at 1:32
Chris actually asked about checking safe primality, not about searching for safe primes. – Brian M. Scott Aug 20 '11 at 2:00
@Brian: That's not clear - see my question to him above (posted 10 minutes before your comment). – Bill Dubuque Aug 20 '11 at 2:36
@Bill: It would be good at this point if he’d offer the clarification, but there’s no ambiguity in the question itself. (Of course, there’s always the possibility that it wasn’t the question that he intended to ask.) – Brian M. Scott Aug 20 '11 at 2:39
@Brian In my opinion it is ambiguous, since most questions of this sort are based on the need to generate them. – Bill Dubuque Aug 20 '11 at 2:43

I am not an expert on primality testing by any means... but Sophie Germain primes enjoy interesting properties that provide necessary conditions for a prime $p$ to be Germain prime. Whether these conditions are computationally helpful... that's another story, which I know nothing about.

The results I am referring to are of the following form:

• Let $q$ be an odd prime, and suppose that $p = 2q + 1$ is also prime. Then, there exist $q$ quadratic nonresidues and $q - 1$ primitive roots of $p$. Thus, every quadratic non-residue of $p$ is a primitive root, except for $-1$.

• Let $q$ be a prime of the form $4k + 1$. If $p = 2q + 1$ is prime, then $2$ is a primitive root of $p$.

• Let $q$ be a prime of the form $4k +3$. If $p = 2q + 1$ is prime, then $-2$ is a primitive root of $p$.

-