3
$\begingroup$

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.

  • 0
    http://vixra.org/pdf/1702.0136v3.pdf2017-02-20

2 Answers 2

3

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.

  • 0
    @Brian I s$t$ill disagree. But it's pointless to continue. Please wait for the OP to clarify.2011-08-20
1

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