Combined Sieving?

jaat · 2005-07-14, 00:32

Hi,

I want to know whether I can do combined sieving for a bunch of k together with newpgen or some other tool? The issue is not to save time but save a lot of bother doing it for each k independently.

jaat

geoff · 2005-07-16, 03:04

I don't know of any sieving program that will do this yet.

But with pfgw you can use an ABC2 file to do trial factoring and prp testing for a number of k values. As an example, put this in myfile.txt:

Code:

ABC2 $a*5^$b-1 //{number_primes,$a,1}
a: in { 1002 2004 }
b: from 100 to 1000

and starting pfgw as 'pfgw -f myfile.txt' will trial factor and/or prp test 1002*5^100-1, 2004*5^100-1, 1002*5^101-1, ... etc. When one prp is found for a value of $a then testing will stop for that value and continue just for the remaining values.

This is convenient, but will be much slower than sieving with newpgen unless the range for each k is quite small.

axn · 2005-10-12, 10:34

Maybe its time we gave serious though to combined sieving.

Can someone get in touch with Mikael Klasson to get a modified version of proth_sieve that can handle base 5? No idea how tough it'll be to do this, but i guess its worth a shot.

jaat · 2005-10-26, 17:55

Quote:

Originally Posted by axn1

Maybe its time we gave serious though to combined sieving.

If there is any hope for this project to gather some momentum, this is a must.

jaat

Greenbank · 2005-11-30, 19:05

Even if you can get this done it's going to be much slower.

You lose all of the Quadratic Residue filtering.
All of the small-steps will have to be calculated with powmod instead of simple bit shifts.
The order(2) filtering will be gone (although you might be able to adapt this to base 5.

Better off finding a program that implements base 5 sieving now as there would have been some attempts at optimising this sieving. proth_sieve only implements base 2, and therefore it is only optimised for base 2.

geoff · 2006-04-18, 02:26

Riesel5 candidate k=151026 is the only one satisfying k = 0 (mod 3). This makes it the only remaining candidate that could have primes for both odd and even exponents. The possibilities for any other candidates are:

If k = 1 (mod 3) then k*5^even-1 and k*5^odd+1 are composite
If k = 2 (mod 3) then k*5^odd-1 and k*5^even+1 are composite

[3 | k*5^n+/-1 whenever 3 | k*5^(n-2)+/-1 because 5^2 = 1 (mod 3)].

This fact could be exploited by a siever, for example to halve the memory required for a bitmap of candidate n (assuming k=151026 is not in the sieve). NewPGen does not seem to take advantage of this.

2005-07-14, 00:32	#1
jaat Jul 2005 2·3² Posts	Combined Sieving? Hi, I want to know whether I can do combined sieving for a bunch of k together with newpgen or some other tool? The issue is not to save time but save a lot of bother doing it for each k independently. jaat

2005-07-16, 03:04	#2
geoff Mar 2003 New Zealand 485₁₆ Posts	I don't know of any sieving program that will do this yet. But with pfgw you can use an ABC2 file to do trial factoring and prp testing for a number of k values. As an example, put this in myfile.txt: Code: ABC2 $a5^$b-1 //{number_primes,$a,1} a: in { 1002 2004 } b: from 100 to 1000 and starting pfgw as 'pfgw -f myfile.txt' will trial factor and/or prp test 10025^100-1, 20045^100-1, 10025^101-1, ... etc. When one prp is found for a value of $a then testing will stop for that value and continue just for the remaining values. This is convenient, but will be much slower than sieving with newpgen unless the range for each k is quite small.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
UPS /combined UPS and PS for P95 computer	Christenson	Hardware	12	2011-10-27 03:41
Combined sieving discussion	ltd	Prime Sierpinski Project	76	2008-07-25 11:44
Combined Sieving speed	Joe O	Prime Sierpinski Project	7	2006-09-22 09:34
Combined Sieve Guide Discussion	Joe O	Prime Sierpinski Project	35	2006-09-01 13:44
Sieve discussion Meaning of first/second pass, combined	Citrix	Prime Sierpinski Project	14	2005-12-31 19:39

2005-10-12, 10:34	#3
axn Jun 2003 4,919 Posts	Maybe its time we gave serious though to combined sieving. Can someone get in touch with Mikael Klasson to get a modified version of proth_sieve that can handle base 5? No idea how tough it'll be to do this, but i guess its worth a shot.

2005-11-30, 19:05	#5
Greenbank Jul 2005 2·193 Posts	Even if you can get this done it's going to be much slower. You lose all of the Quadratic Residue filtering. All of the small-steps will have to be calculated with powmod instead of simple bit shifts. The order(2) filtering will be gone (although you might be able to adapt this to base 5. Better off finding a program that implements base 5 sieving now as there would have been some attempts at optimising this sieving. proth_sieve only implements base 2, and therefore it is only optimised for base 2.

2006-04-18, 02:26	#6
geoff Mar 2003 New Zealand 13·89 Posts	Riesel5 candidate k=151026 is the only one satisfying k = 0 (mod 3). This makes it the only remaining candidate that could have primes for both odd and even exponents. The possibilities for any other candidates are: If k = 1 (mod 3) then k5^even-1 and k5^odd+1 are composite If k = 2 (mod 3) then k5^odd-1 and k5^even+1 are composite [3 \| k5^n+/-1 whenever 3 \| k5^(n-2)+/-1 because 5^2 = 1 (mod 3)]. This fact could be exploited by a siever, for example to halve the memory required for a bitmap of candidate n (assuming k=151026 is not in the sieve). NewPGen does not seem to take advantage of this.