3
$\begingroup$

I am trying to find a list or table of safe prime numbers i.e. the ones that are based on the Sophie Germain primes i.e. $N = 2p + 1$ where $p$ is also prime.

All I found till now is this database. However the problem with that database is that all Sophie Germain primes in this database have at least 1000 digits. So, is out there any database that has the Sophie Germain primes including the one that are less then 1000 digits long?

I am looking for Sophie Germain primes that will allow me to calculate safe prime numbers that are 512, 768, 1024, 2048, 4096 bit long.

Improve this question
$\endgroup$
  • $\begingroup$ 1) Why don't you simply generate a random number of the desired size, check if it's a safe prime and repeat if it's not? 2) I think there are some RFC documents that define standard primes for use with Diffie-Hellman, these are often safeprimes. $\endgroup$ – CodesInChaos Jan 7 '15 at 10:24
  • $\begingroup$ well i already did that and found some safe primes in srp rfc's however i found them only till 1024 bits and not above. $\endgroup$ – Tito Jan 7 '15 at 12:41
  • $\begingroup$ CodesInChaos your idea was the correct one rfc5054 appendix A. Thank you. $\endgroup$ – Tito Jan 7 '15 at 19:54
6
$\begingroup$

A Sophie Germain prime is a prime $p$ such that $2p+1$ is prime (that later prime is deemed a safe prime). For small examples, see A005384 in the OEIS.

A random integer $n$ has odds commensurate to $1/\log(n)^2$ to be a Sophie Germain prime. Therefore, there's in the order of $2^{495}$ Sophie Germain primes of 511 bits, way too much to enumerate them, much less store them in a database.

In order to find a Sophie Germain prime that will allow to calculate safe prime of $k=$512, 768, 1024, 2048, 4096 bits, one can simply repeatedly find a random prime $p$ of $k-1$ bits, until $2p+1$ is prime (or repeatedly find a random $k$-bit prime $p$, until $(p-1)/2$ is prime); the smallest of the two related primes exhibited is the Sophie Germain prime, the other is the safe prime.

A large speedup is possible by sieving with small primes, noticing that $p$ and $2p+1$ being large primes implies $p$ odd; $p\bmod3=2$; $p\bmod5\in\{1,3,4\}$; and more generally $p\bmod q\not\in\{0,(q-1)/2\}$ for any small odd prime $q$.

For cryptographic applications, one can use the Miller-Rabin primality test.

Improve this answer
$\endgroup$
  • $\begingroup$ @Tito: I (and most on this website) would rather not give direct answer to what could be homework. $\;$ Beside, you ask for 2048 and 4096-bit Sophie Germain primes in you last comment, versus 2047 and 4095-bit in the question (given that the size stated in the question is for the safe prime); so I'm sure neither of if you ask specific values for a legitimate reason, and exactly what bit size they should have. $\endgroup$ – fgrieu♦ Jan 7 '15 at 16:43
  • $\begingroup$ frrieu i agree, please igore my last requst. I have already found what i was searching for in RFC 5054 Appendix A. Anyway thanks for the help $\endgroup$ – Tito Jan 7 '15 at 19:52
0
$\begingroup$

Here is what I'm using to find Sophie Germain primes (and twin primes) at the 1024 (and 1023) bit level:

    private void TwinSeeker()
    {
        BigInteger p1, p2;
        string ps;
        int cntr = 0;
        p1 = 2;
        p2 = BigInteger.Pow(2, 1023);
        if (p2 % 2 == 0)
        {
            p2++;
        }
        while (cntr<100)
        {
            if (PrimeTest(p2))
            {
                ps = (p2 * 2 + 1).ToString();
                if (PrimeTest(p2*2+1))
                {
                    textBox1_SetText("Sophie Germain = " + ps);
                    cntr++;
                }
                ps = p2.ToString();
                //if(p2 % 12 == 11)
                //{
                //    textBox1_SetText("Safe-ish Prime = " + ps);
                //}
                if (p2 - p1 == 2)
                {
                    textBox1_SetText("Twin Prime (p+2) = " + ps);
                }
                p1 = p2;
            }
            p2 += 2;
        }
    }

PrimeTest() was a Rabin-Miller prime test but it was too slow so I'm doing a simple Fermat test at bases 2,3,5,7 and 11:

BigInteger.PowerMod(2,p-1,p)==1 And BigInteger.PowerMod(3,p-1,p)==1 And .. And BigInteger.PowerMod(11,p-1,p)==1

At 1023 bits, that's plenty, I haven't seen a liar for base 2 at that level yet.

I'll give you the first three for free (no twins so far):

Sophie Germain = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624225795083

Sophie Germain = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624227077847

Sophie Germain = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624227998859

EDIT: Fixed a bug that suppressed twin primes.

Improve this answer
$\endgroup$
  • $\begingroup$ "simple Fermat test at bases 2,3,5,7 and 11" >> I find this a bit restrictive and quite unsure to provide relatively safe prime numbers. It is like having an anti-virus but having it disabled because it slows down the computer. Expect some problem then... $\endgroup$ – Biv Mar 2 '16 at 12:37

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.