1
$\begingroup$

A prime $p$ is Sophie Germain if $2p+1$ is also prime. Wiki says if $p\equiv3\bmod4$ then $2p+1|2^p-1$. This seems to put a huge restriction on density of Sophie-Germain prime if they are $3\bmod4$. For this reason do all systems use Sophie-Germain primes with $1\bmod 4$ for discrete logarithm?

$\endgroup$
4
$\begingroup$

This seems to put a huge restriction on density of Sophie-Germain prime if they are $3 \bmod 4$.

I'm not sure how you come to that conclusion; whether $2p+1$ is a factor of $2^p-1$ would not have any immediately obvious consequence to $2p+1$ being prime.

For this reason do all systems use Sophie-Germain primes with $1 \bmod 4$ for discrete logarithm?

Actually, Sophie-Germain primes of the form $3 \bmod 4$ would appear to be more prevalent; for example, the primes listed here are all of the form $3 \bmod 4$. One reason is that it makes the value $g=2$ be a quadratic residue, that is, its use during the DH operation doesn't leak the lsbit of the private exponent, and that's appreciated by some people.

$\endgroup$
  • $\begingroup$ could you explain on 'its use during the DH operation doesn't leak the lsbit of the private exponent'? I though lsbit is always leaked no matter what. $\endgroup$ – T.... May 14 '17 at 21:45
  • 2
    $\begingroup$ @Turbo: sure; in DH, Alice picks a random value $a$ and transmites $g^a \bmod p$; if $g$ is a primitive element, anyone can test if $g^a$ is a quadratic residue; if it is, then the lsbit of $a$ is a 0; otherwise it is a 1. If $g$ is a quadratic residue, then that test tells people nothing (as $g^a \bmod p$ is always a quadratic residue). $\endgroup$ – poncho May 14 '17 at 21:47
  • $\begingroup$ so $1\bmod 4$ and $3\bmod 4$ Sophie-Germain prime densities are believed similar? $\endgroup$ – T.... May 14 '17 at 21:49
  • 2
    $\begingroup$ @Turbo: as far as I know; a quick count of the ones under 100,000,000 shows a slight edge to the $3 \bmod 4$ (211,439 vs 211,700)... $\endgroup$ – poncho May 15 '17 at 2:53
  • 1
    $\begingroup$ 3 mod 4 has a very small lead at 1e9 and 1e10 as well, but loses it by 2e10 (20,000,000,000). It's extremely close at 1e11 with 3 mod 4 leading by a very small amount. $\endgroup$ – DanaJ May 15 '17 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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