0
$\begingroup$

Do Safe and Sophie Germain primes maintain a relatively stable distribution as numbers get larger, or do they become rarified beyond a predictable value?

This is important in one area of triangular number comparison for some of my study.

What is the predicatable, stable distribution?

Is there a comparable density, like the density of primes (roughly $1/\log n)$? (thanks kodlu) Also, what is the effect if we include triangular numbers of form (N * (2N-1), with N and 2N-1 both being prime?

$\endgroup$
2
  • $\begingroup$ All primes get rarer on average as their size gets larger (density is roughly $1/\log n$) so what exactly are you talking about? The question you are asking has to be specified more precisely. Also please edit your equations using MathJax. See mathjax.org $\endgroup$
    – kodlu
    Nov 28, 2023 at 19:26
  • 1
    $\begingroup$ Actually, a Sophie Germain prime pair (various definitions has either one being the "SG Prime") is the pair of primes $(p, 2p+1)$, not $2p-1$. If you're interested in pairs of the form $p, 2p-1$, that's fine - however that has nothing to do with either Sophie Germain primes or safe primes $\endgroup$
    – poncho
    Nov 28, 2023 at 22:30

2 Answers 2

2
$\begingroup$

So, as far as I can surmise, the existence of infinitely many Sophie Germain primes is still open. There is a preprint on vixra, see here [vixra is a kind of a free for all arxiv server] but it has clearly not been peer-reviewed, neither published.

As far as the distribution of the gap to the next Sophie-Germain prime, this mathoverflow question has a heuristic answer for it, which while nice is definitely not a proof.

Cramer's conjecture (itself a conjecture not a proof) states that the gap between consecutive primes in $[2,n]$ is bounded by $O(\log^2 n)$.

The version for Sophie-Germain primes is that this should be changed to $O(\log^3 n).$

The best proven upper and lower bounds on prime gaps are summarized in the answer to this mathoverflow question. For completeness' sake, the upper bound is due to Baker Hartmann and Pintz and is $O(n^{0.525}/\log n)$ showing the massive gap between what is widely believed and what is provable.

$\endgroup$
0
2
$\begingroup$

Recall that $p$ is a safe prime and $q$ is a Sophie Germain prime when $p=2q+1$ and both $p$ and $q$ are prime. Safe and Sophie Germain primes are sometime useful in cryptography, e.g. in variations of RSA. Therefore the question of their distribution is on-topic. While from a math perspective we have few certainties (see that other answer), in cryptography, we can live with heuristic arguments and approximations, especially when backed by practicable experiments for numbers of cryptographic interest.

Without proof: given a large random integer $q$, the integer $2q+1$ is prime mostly independently of if $q$ is prime or not. And since $2q+1$ is odd, that $2q+1$ is prime with twice the probability of a random integer near $2q+1$.

By the prime number theorem, a random integer near $n$ has probability about $\frac 1{\ln n}$ to be prime (where $\ln$ is the natural logarithm function). It follows that the probability that a large random integer $q$ is prime and the corresponding integer $p=2q+1$ is prime is about $\frac 1{(\ln(2q+1))(\ln q)}$. Thus asymptotically, the probability that a random integer $q$ is a Sophie Germain prime is about $$\frac 2{(\ln q)^2}$$

That's also about the probability that $q$ is a safe prime.

Note: I do not know if $\frac 2{(\ln p)((\ln p)-\ln 2)}$ and $\frac 2{(\ln q)((\ln q)+\ln 2)}$ are any better approximations of the density of safe and Sophie Germain primes. That's not much different for primes of cryptographic interest, and asymptotically the same.

It follows safe and Sophie Germain primes are rarer and thin out faster than primes do. For example, about one 1024-bit (309 decimal digits) integer out of 710 is prime, but only one in about 250,000 is a Sophie Germain prime. Whatever (not too small) size considered, the second of these numbers is about half the square of the first.

It remains reasonably easy to find safe and Sophie Germain primes of cryptographic interest (even when it's totally impractical to factor most integers that size) because

  1. When $q>3$, it must hold $q\bmod6=5$.
  2. We can use sieving techniques to further considerably reduce candidates.
  3. For $q$ that pass test 1, if $q$ and $p=2q+1$ both pass the strong pseudoprime test to base 2, then it's highly likely that $p$ and $q$ are matching safe and Sophie Germain primes (I know no counterexample). Since most candidates $q$ are screened by the first test made, it dominates the cost.
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.