PDA

View Full Version : seive question



vjs
06-01-2004, 09:56 AM
my understanding of the seive effort is lacking so hopefully someone can help me out.

how do seive ranges compare to n values?

my major question is two fold

1. Double check test are going to be pretty much complete upto k=800K shortly, is there any need to resieve or seive the 800k-1M or 800k-2m range?? have we fully seived this range.

Or can/should we do a simple seive between 1m-2m very well to eliminate more factors (not sure how this works I though once something was seived it was seived and you can't find more factors...)

2. Were is the seive effort in relation to the current n value.

Are we behind on seiveing compared to prp? compared to prp for double checks? for single checks?

Where is the most upto date dat file. I noticed that some k's have arleady been excluded that are still listed on Mike's site.

Joe O
06-01-2004, 11:03 AM
Welcome!

Please start by reading this excellent page (http://www.aooq73.dsl.pipex.com/) compiled by MikeH. This page leads to more information, including the up to date 1M to 20M SoB.dat file. (http://www.aooq73.dsl.pipex.com/SobDat_n1M-20M.zip)

Sieve ranges are p(rime) values not n values. The Primes in your reserved sieve range are checked to see if they divide k*2^n+1 for any one of the 11k and all n between 1M and 20M. There is another effort finishing up the lower n values between 1K and 1M, but this is nearly at the point of diminishing returns. PM me if you want more information. I do not want to confuse the issue, or take away from the main sieving effort.

While the sieve effort is for all n values, the P-1 factoring effort is for n values just ahead of the PRP tests (current n value). Please see the factoring sub forum for more information and/or this excellent site by H C Grove. (http://www.sslug.dk/~grove/sbfactor/) The P-1 ranges are n values not p values. The k n pairs in your reserved P-1 range are checked to see if you can find a prime p that divides k*2^n+1.

Mike H's stats show 12 K because there were 12 Ks when the sieving effort became public. Prior to that Louie and Dave did all the sieving. The sob.dat file has 11 Ks and is up to date. The SoB.txt file is just there for information purposes.

You will note that the PRP stat pages still show all 17 Ks, even though 6 primes have been found, and tests are only being handed out for the current 11 Ks.

Do not confuse the historical information with the current information. The history (stats) show all that we have done, and all that we are doing. That is what history is all about.

Nuri
06-01-2004, 12:29 PM
Originally posted by vjs
1. Double check test are going to be pretty much complete upto k=800K shortly, is there any need to resieve or seive the 800k-1M or 800k-2m range?? have we fully seived this range.

Or can/should we do a simple seive between 1m-2m very well to eliminate more factors (not sure how this works I though once something was seived it was seived and you can't find more factors...)

2. Were is the seive effort in relation to the current n value.

Are we behind on seiveing compared to prp? compared to prp for double checks? for single checks?

In addition to Joe's comments:

1. As the main sieve effort covers all n values where n>1m, there's absolutely no need to resieve or seive the 800k-1M or 800k-2m range (or 1m-2m).

2. Sieving is still significantly useful on a per PC basis, but it's contribution (from now on) will not exceed 5% (just a wild guess) of the remaining PRP work up to 20m. In other words, it's still useful, but the results would not be dramatic if we stop sieving right now.

As far as P-1 factoring is concerned, by definition it's a few percents faster than PRP in terms of k/n pairs they eliminate (assuming the k/n pair in question is not prime :D )


As a result, doing all three is essential. The question is about the allocation of resources, but in my opinion the collective wisdom of users adjusts allocations reaonably (and very quickly).

PS: In fact, this is valid for PRP double check (secret & supersecret) as well.

Troodon
06-01-2004, 01:16 PM
Another thing you have to consider (as for usefulness): with PRP, you get a residue, which may o not be correct, so to be totally sure you have to double-check it, and for high n's that takes a lot of time. If you find a factor, via sieving or via P-1 factoring, that's a "definitive probe" of non-primality and can be easily checked. So even if that number has already been PRPed, with a factor there no need for a doube check.


As a result, doing all three is essential. The question is about the allocation of resources, but in my opinion the collective wisdom of users adjusts allocations reaonably (and very quickly).
I think there's sufficient power in the sieving area, but the P-1 factoring area is very underpowered. Also, the processor type and the memory available has to be considered in the model. For example, any Pentium I, Pentium II, K6, M-II, C-3 and the slower Pentium III/Celerons will do the greatest contribution by sieving, as they need a lot of time to complete a PRP test at the current n values and they aren't very good at P-1 factoring (plus generally they don't have the memory amount necesary to obtain good results with factoring).