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.
|show 4 more comments|
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.
|show 2 more comments|
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: