## Other

drummers-lowrise

Message boards : Project Staging Area : Sophie Germain sieve

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Message 15999 - Posted: 2 Jun 2009 | 18:51:30 UTC

Small question, how and how much is the Sophie Germain range sieved?
____________ Message 16002 - Posted: 2 Jun 2009 | 19:08:03 UTC - in response to Message 15999.

Small question, how and how much is the Sophie Germain range sieved?

We used David Underbakke's TwinGen. Sieving was completed in Jan 2008. Below is some additional information:

• Sophie Germain Prime Search
A prime number p is called a Sophie Germain prime if 2p + 1 is also prime. For example, 5 is a Sophie Germain prime because it is prime and 2 × 5 + 1 = 11, is also prime. They are named after Marie-Sophie Germain, an extraordinary French mathematician.

We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-1, & k*2^(n+1)-1. We are able to do this because a quad sieve was performed for this search. This sieve ensured that k*2^n-1, k*2^n+1, k*2^(n-1)-1, & k*2^(n+1)-1 do not have any small prime divisors.

As you can see, a twin prime is also possible from this search although we expect to find a Sophie Germain prime first. Here are some stats for the search:

k range: 1<k<41T
n=666666
sieve depth: p=200T
candidates remaining: 34,190,344

Probability of one or more significant pair = 80.1%
Probability of one or more SG = 66.7%
Probability of one or more Twin = 42.3%

Approximate WU length:
Athlon64 2.1Ghz - ~2000 secs (~33.3 minutes)
C2D 2.1 Ghz - ~1015 secs (~16.9 minutes) per core
C2Q 2.4 GHz - ~880 secs (~14.7 minutes) per core

http://primes.utm.edu/glossary/page.php?sort=SophieGermainPrime
http://mathworld.wolfram.com/SophieGermainPrime.html
http://en.wikipedia.org/wiki/Sophie_Germain_prime

http://en.wikipedia.org/wiki/Sophie_Germain
http://www.pbs.org/wgbh/nova/proof/germain.html

____________

Message 16021 - Posted: 3 Jun 2009 | 14:49:55 UTC