Sophie-Germain sieve

firejuggler · 2014-01-08, 19:11

I'm looking for a SG siever, as Newpgen can only sieve for one n at a time. More particulary, for the k*2^n+1 & k*2^(n+1)+3.
Right now, i'm looking for Fermat divisor with k between 50e6 and 100e6 with N between 6150 and 6300. The best method
I found so far is to take the prime found with PFGW , convert to newpgen format, add the SG header (1:P:0:2:4097) then
pass the file to LLR (PFGW doesn't seem to handle it well)

pfgw output

Code:

50000015*2^6277+1 is 3-PRP! (0.0164s+0.0000s)
2*50000015*2^6277+3 is 3-PRP! (0.0166s+0.0007s)
50000091*2^6208+1 is 3-PRP! (0.0159s+0.0006s)
2*50000091*2^6208+3 is composite: RES64: [99DB9963CADC02CB] (0.0502s+0.0006s)
50000135*2^6287+1 is 3-PRP! (0.0161s+0.0001s)
2*50000135*2^6287+3 is composite: RES64: [FCAA64210051C2F4] (0.0164s+0.0007s)
50000163*2^6200+1 is 3-PRP! (0.0160s+0.0001s)
2*50000163*2^6200+3 is composite: RES64: [8D56C728E7EFFC3F] (0.0476s+0.0006s)
50000167*2^6270+1 is 3-PRP! (0.0163s+0.0001s)
2*50000167*2^6270+3 is composite: RES64: [A418C1326AE85D01] (0.0163s+0.0007s)
50000187*2^6283+1 is 3-PRP! (0.0166s+0.0001s)
2*50000187*2^6283+3 is composite: RES64: [045B1F70DECC6B45] (0.0480s+0.0005s)
50000229*2^6230+1 is 3-PRP! (0.0160s+0.0001s)
2*50000229*2^6230+3 is composite: RES64: [B2A6EB7E8322FD6E] (0.0479s+0.0006s)
50000251*2^6284+1 is 3-PRP! (0.0163s+0.0001s)
2*50000251*2^6284+3 is composite: RES64: [9A56C78E1776A515] (0.0163s+0.0006s)
50000259*2^6281+1 is 3-PRP! (0.0164s+0.0001s)
2*50000259*2^6281+3 is composite: RES64: [A67C2FC9A89CE30B] (0.0478s+0.0008s)
50000265*2^6297+1 is 3-PRP! (0.0162s+0.0001s)
2*50000265*2^6297+3 is composite: RES64: [87C048E4FFAEB5E3] (0.0483s+0.0005s)
50000317*2^6272+1 is 3-PRP! (0.0164s+0.0001s)
2*50000317*2^6272+3 is composite: RES64: [DF2A75D16604E7A9] (0.0164s+0.0006s)
50000325*2^6236+1 is 3-PRP! (0.0160s+0.0001s)
2*50000325*2^6236+3 is composite: RES64: [D747A2F35C2BDD4F] (0.0498s+0.0007s)
50000429*2^6171+1 is 3-PRP! (0.0170s+0.0001s)
2*50000429*2^6171+3 is composite: RES64: [22019FE0A0057A3F] (0.0167s+0.0006s)
50000443*2^6210+1 is 3-PRP! (0.0166s+0.0001s)
2*50000443*2^6210+3 is composite: RES64: [47B1488C097FC7C2] (0.0161s+0.0011s)
50000495*2^6241+1 is 3-PRP! (0.0161s+0.0001s)
2*50000495*2^6241+3 is composite: RES64: [37E0A97E82814D45] (0.0163s+0.0006s)
50000503*2^6286+1 is 3-PRP! (0.0162s+0.0001s)
2*50000503*2^6286+3 is composite: RES64: [4BA8D20C6F34F488] (0.0163s+0.0007s)

lresult ouput

Code:

50000015*2^6277+1 is prime!  Time : 42.616 ms.
100000030*2^6277+3 is not prime.  RES64: 23B1D99649043283  Time : 44.281 ms.
50000091*2^6208+1 is prime!  Time : 43.337 ms.
100000182*2^6208+3 is not prime.  RES64: 99DB9963CADC02CB  Time : 73.486 ms.
50000135*2^6287+1 is prime!  Time : 49.604 ms.
100000270*2^6287+3 is not prime.  RES64: FCAA64210051C2F4  Time : 42.066 ms.
50000163*2^6200+1 is prime!  Time : 42.613 ms.
100000326*2^6200+3 is not prime.  RES64: 8D56C728E7EFFC3F  Time : 72.979 ms.
50000167*2^6270+1 is prime!  Time : 38.726 ms.
100000334*2^6270+3 is not prime.  RES64: A418C1326AE85D01  Time : 44.334 ms.
50000187*2^6283+1 is prime!  Time : 53.914 ms.
100000374*2^6283+3 is not prime.  RES64: 045B1F70DECC6B45  Time : 70.249 ms.
50000229*2^6230+1 is prime!  Time : 39.567 ms.
100000458*2^6230+3 is not prime.  RES64: B2A6EB7E8322FD6E  Time : 71.958 ms.
50000251*2^6284+1 is prime!  Time : 48.216 ms.
100000502*2^6284+3 is not prime.  RES64: 9A56C78E1776A515  Time : 44.708 ms.
50000259*2^6281+1 is prime!  Time : 43.079 ms.
100000518*2^6281+3 is not prime.  RES64: A67C2FC9A89CE30B  Time : 90.409 ms.
50000265*2^6297+1 is prime!  Time : 204.661 ms.
100000530*2^6297+3 is not prime.  RES64: 87C048E4FFAEB5E3  Time : 92.486 ms.
50000317*2^6272+1 is prime!  Time : 38.953 ms.
100000634*2^6272+3 is not prime.  RES64: DF2A75D16604E7A9  Time : 44.580 ms.
50000325*2^6236+1 is prime!  Time : 43.489 ms.
100000650*2^6236+3 is not prime.  RES64: D747A2F35C2BDD4F  Time : 71.081 ms.
50000429*2^6171+1 is prime!  Time : 40.058 ms.
100000858*2^6171+3 is not prime.  RES64: 22019FE0A0057A3F  Time : 44.556 ms.
50000443*2^6210+1 is prime!  Time : 35.011 ms.
100000886*2^6210+3 is not prime.  RES64: 47B1488C097FC7C2  Time : 36.916 ms.
50000495*2^6241+1 is prime!  Time : 68.993 ms.
100000990*2^6241+3 is not prime.  RES64: 37E0A97E82814D45  Time : 45.293 ms.
50000503*2^6286+1 is prime!  Time : 34.812 ms.
100001006*2^6286+3 is not prime.  RES64: 4BA8D20C6F34F488  Time : 36.231 ms.

and yes I found some hit.

Code:

50063587*2^6290+1 is prime!  Time : 48.686 ms.
100127174*2^6290+3 is prime!  Time : 53.284 ms.

50138695*2^6216+1 is prime!  Time : 94.767 ms.
100277390*2^6216+3 is prime!  Time : 102.605 ms.


50232221*2^6235+1 is prime!  Time : 44.790 ms.
100464442*2^6235+3 is prime!  Time : 47.948 ms.

As for the reason of this... for fun, what else?

Citrix · 2014-01-09, 07:36

http://www.underbakke.com/primes/

might be helpful.

I would suggest searching k between 50e6 and 100e6 with N between 6150 and 6300 using the above. (This range might have already been searched before).

Then test with PFGW or LLR and then test the primes found for SG candidates.

It would be fun to have a coordinated search for Fermat factors for small n (that do not end up on the top 5000 list ie n<250k) and large k ranges (10k-1.2M).

firejuggler · 2014-01-09, 14:14

Thanks a lot Citrix.

Ken_g6 · 2014-01-09, 23:28

That's an unusual range. Most people do k*2^n-1 for SG, but maybe that's why you picked this range. It doesn't look like David Underbakke's software does k*2^n+3.

My ppsieve won't do the +3s, but it would be really fast on the +1s. You can even run the CUDA or OpenCL version if you have an appropriate graphics card.

NewPGen can be set to work on one N up to a given P, and then jump to the next N. Not as efficient as ppsieve, but maybe you could have it sieve the +3s on your CPU while ppsieve does the +1s on a GPU (Edit: and one CPU core - that small range of N's is almost certainly going to be CPU-limited), and then you could combine the results somehow.

firejuggler · 2014-01-10, 00:09

The fact is, I'm looking for fermat divisors, and the range (k=50e6 to 100e6 and N between 6150-6300) is at the factoring limit as far as W.keller page would say.

I got interested in this because of my searsh for low prime the 12/31, when Proth.exe told me that 31122013*2^56+1 and 31122013*2^57+3 were SG prime.

I know of ppsieve, and will use it again soon.ATM I use fermfact.

2014-01-09, 07:36	#2
Citrix Jun 2003 11001000101₂ Posts	http://www.underbakke.com/primes/ might be helpful. I would suggest searching k between 50e6 and 100e6 with N between 6150 and 6300 using the above. (This range might have already been searched before). Then test with PFGW or LLR and then test the primes found for SG candidates. It would be fun to have a coordinated search for Fermat factors for small n (that do not end up on the top 5000 list ie n<250k) and large k ranges (10k-1.2M). Last fiddled with by Citrix on 2014-01-09 at 07:39

2014-01-09, 23:28	#4
Ken_g6 Jan 2005 Caught in a sieve 18B₁₆ Posts	That's an unusual range. Most people do k2^n-1 for SG, but maybe that's why you picked this range. It doesn't look like David Underbakke's software does k2^n+3. My ppsieve won't do the +3s, but it would be really fast on the +1s. You can even run the CUDA or OpenCL version if you have an appropriate graphics card. NewPGen can be set to work on one N up to a given P, and then jump to the next N. Not as efficient as ppsieve, but maybe you could have it sieve the +3s on your CPU while ppsieve does the +1s on a GPU (Edit: and one CPU core - that small range of N's is almost certainly going to be CPU-limited), and then you could combine the results somehow. Last fiddled with by Ken_g6 on 2014-01-09 at 23:30

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sophie Germain Twins	Trejack	Twin Prime Search	10	2016-06-23 15:10
Sophie-Germain primes as Mersenne exponents	ProximaCentauri	Miscellaneous Math	15	2014-12-25 14:26
Advantage of lattice sieve over line sieve	binu	Factoring	3	2013-04-13 16:32
Sophie Germains, multiple n-ranges, future of TPS	MooooMoo	Twin Prime Search	8	2008-11-05 15:03
Left over Sophie Germain primes?	axn	Twin Prime Search	3	2007-01-15 12:57

2014-01-09, 14:14	#3
firejuggler "Vincent" Apr 2010 Over the rainbow B44₁₆ Posts	Thanks a lot Citrix.

2014-01-10, 00:09	#5
firejuggler "Vincent" Apr 2010 Over the rainbow 2²×7×103 Posts	The fact is, I'm looking for fermat divisors, and the range (k=50e6 to 100e6 and N between 6150-6300) is at the factoring limit as far as W.keller page would say. I got interested in this because of my searsh for low prime the 12/31, when Proth.exe told me that 311220132^56+1 and 311220132^57+3 were SG prime. I know of ppsieve, and will use it again soon.ATM I use fermfact.