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