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
    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.2011-08-20
  • 0
    I have added the definition of a safe prime to the question, thanks for the feedback.2011-08-20
  • 0
    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?2011-08-20
  • 0
    Is there a fast primality test that determines if a number **is** prime (not **probably** prime)?2011-08-20
  • 0
    @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.2011-08-20
  • 0
    @Chris: I’ve only a very casual interest, so I could be wrong, but I believe that algorithms of the AKS class have been implemented reasonably efficiently.2011-08-20
  • 0
    @Bill: Thanks. Is there *any* deterministic test that’s both completely general and practical for a reasonable variety of applications?2011-08-20
  • 0
    @Brian AKS is not competetive for the range of numbers encountered in most applications.2011-08-20
  • 0
    @Brian There are various tradeoffs. For a recent discussion see e.g. Brent: [Primality Testing. 2010.](http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf) For a 100 digit number he quotes: 0.3 sec for 100 trials of Rabin-Miller, 2 secs for ECPP, and 37 weeks to 1 year (est) for AKS in his Magma implementation on a 1 GHz machine.2011-08-20
  • 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.

  • 1
    So there *is* a speedup in safe prime searching, and a good one, over naive double primality testing. Nice to know.2011-08-20
  • 0
    Chris actually asked about checking safe primality, not about searching for safe primes.2011-08-20
  • 0
    @Brian: That's not clear - see my question to him above (posted 10 minutes before your comment).2011-08-20
  • 0
    @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.)2011-08-20
  • 0
    @Brian In my opinion it is ambiguous, since most questions of this sort are based on the need to *generate* them.2011-08-20
  • 0
    @Bill: Ah, okay: we just speak slightly different languages. I’d have said that the intent was ambiguous, but that the question itself, as expressed by a particular string of words, was not.2011-08-20
  • 0
    @Brian I still 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$.