1
$\begingroup$

Is there a list of all known Sophie Germain prime numbers available anywhere for download? I found a small list from OEIS and the top 20 biggest of such primes, but I can't find a list that would contain numbers that are not on the extremes of size.

$\endgroup$
  • $\begingroup$ Sorry maybe this is a strange comment, but for what do you need such a list? I just can't imagine that such a list would be useful for anything. $\endgroup$ – Dominic Michaelis Mar 17 '13 at 11:06
  • $\begingroup$ vaxasoftware.com/doc_eduen/mat/primsophie_en.pdf. It is not the list of all the Sophi Germain Primes. $\endgroup$ – Inceptio Mar 17 '13 at 11:44
  • $\begingroup$ Have you thought about how long that list would be? The number of primes $p$ less than $N$ such that $2p+1$ is prime is (heuristically) about $N/(\log N)^2$. It's probably easier to generate as many of these primes as you want on the fly as it is to import a table someone else has made. $\endgroup$ – Gerry Myerson Mar 17 '13 at 12:35
  • $\begingroup$ @DominicMichaelis I want to use those numbers for Pohlig-Hellman cipher. However, I also have to balance that with performance of various machines the algorithm will be deployed on (desktop and mobile). So I need a list of such numbers in order to be able to find the right bit size sweet spot. $\endgroup$ – ThePiachu Mar 17 '13 at 12:48
  • $\begingroup$ @GerryMyerson I would, but a good list of prime numbers is also hard to come by - math.stackexchange.com/q/319570/20958 . $\endgroup$ – ThePiachu Mar 17 '13 at 12:49
2
$\begingroup$

Using Gerrys heuristic show us that such a list won't be helpfull at all. With Mathematica you can calculate the $10^9$ prime number in a time which is so small, that mathematica only gives $0.$

The $10^9$th prime number is $22801763489$, with Gerrys heuristic we will have about $4 \cdot 10^7$ Sophie Germain Prime numbers below this prime. Lets assume every of those numbers will need 1 byte in the list, then this list takes $4 \cdot 10^7 $ bytes, which is about 40 mega bytes. This may not seem to be much but they still wasting your cache, and when your list gets larger it won' t fit in the cache and so will extremly slow your computations (taking the sophie primes numbers below the $10^{12}$ primes would be a list of about $3$ giga bytes).

And the list alone doesn't help you, as your program needs to find it in the list, if you give your list a nice structure (using sublists etc) you may get a complextiy of $\mathcal{O}(\log(L))$ to find a number inside your list where $L$ is the number of numbers in your list.

For a lot of problems this will consume much more time than the factorisation itself.

And as you said yourself it is hard to find such a list, this indicates, that it is not so helpful, cause else it would be easier to find.

$\endgroup$
  • $\begingroup$ Can try writing a python program for the same? Is it helpful? $\endgroup$ – Inceptio Mar 17 '13 at 13:36

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.