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