P-1 factoring anyone? - Page 125

James Heinrich · 2012-07-03, 22:45

Quote:

Originally Posted by S34960zz

Does this only help when B1new == B1, or also when B1new > B1 ?

Both. I haven't a clue about the math behind it, but if B1new > B1old it will simply continue stage1 from B1old.

A stage2 savefile is also useful:
* If B1new = B1old and B2new > B2old then stage2 will continue from B2old.
* If B1new > B1old then stage1 will continue from B1old and stage2 will be redone from the start (same as if you only had a stage1 savefile).

Dubslow · 2012-07-03, 22:59

Doing stage 2 depends on the results from stage 1.

If you have a save file for B1o and B2o, if you want to increase B1o, then you will lose any stage 2 work you have done.

This is why Prime95 ignores any new B1 with an old B2, because that would mean throwing out the previously done S2 work.

You can always start any stage 2 bound from an arbitrary B1, if you have the save file for B1.

LaurV · 2012-07-04, 07:25

B2 does not matter. If you have old files saved at the end of the stage 1, then you can extend B1 (no matter what you do with B2, increase it or decrease it) and the work will be resumed from the old saved file.

Having B1new>B1old is always better, no matter how the relation between B2old and B2new.

Stage 1 is the "certitude". Stage 2 is more or less a "lottery", finding the lucky number... Moreover, there must be a single lucky number, if there are two (between B1 and B2) the stage 2 will fail.

This is like fishing, in stage 1 you start taking the water out from the lake. If during this process you catch a fish, is yours, and the job is finished. If not, you can return any time and take more water out from the lake, assuming the status/level of water is the same, it did not rain or someone put the water back (i.e. if you have the saved file).

In stage 2, you can take a boat, chose your favorite fishing net and go fishing. You can use many nets in the same time, 2, 6, 30, or a full Brent-Suyama set, but when you catch a fish, you must catch all his brothers in the same time, otherwise the brothers which are free will sink your boat. With these rules you may be lucky and find a fish with no brother (a single big factor of q-1, or of** k, between B1 and B2), or you can catch a small family in the same time, if it is really small (like two brothers only, one brother is 6k-1 and another is 6k+1

)

But generally you will come back empty-handed, wet, and swimming....

Taking water out of the basin is easier, more certain, and... safe.

**Comic note: for mersenne numbers this method should be called "q-1" or "k"

. No disrespect for Pollard, but we use p as the prime exponent, so if p is a prime, the factors which Mp might have, are usually denoted q. So, the method tries to find a factor q of Mp=2^p-1, and it will succeed if all prime factors of q-1 are small enough. Using "p-1" here is confusing and wrong. OTOH, if q divides Mp, then q is always of the form q=2kp+1, so we are in fact looking for prime factors of 2kp, or more exact, factors F=f^x of k=(q-1)/(2p)), with f prime and x natural. If all such factors F of k are under B1 (we say k is "B1-power-smooth", or easier, just "smooth") then the "q-1" method will always find the factor q of Mp in stage 1.

MrHappy · 2012-07-06, 17:39

Do we currently complete enough P-1 per day?

Would it be a good idea to up the P-1 bounds to search deeper? Or, on the other hand, to lower the bounds to complete (say) double the exponents at (say) only 20% less chance to find a factor?

chalsall · 2012-07-06, 17:57

Quote:

Originally Posted by MrHappy

Do we currently complete enough P-1 per day?

As of the last month or so, the GPU72 sub-project has been completing about the same number of P-1 runs as there are daily LL completions. This is addition to what people are doing directly from PrimeNet. (Note the graph shows a descending trend because many of our big-gun P-1ers submit their results in large batches every week to ten days.)

Quote:

Originally Posted by MrHappy

Would it be a good idea to up the P-1 bounds to search deeper? Or, on the other hand, to lower the bounds to complete (say) double the exponents at (say) only 20% less chance to find a factor?

I'll let others who understand the cost/benefit of P-1 work better than I do speak to this.

Dubslow · 2012-07-06, 18:00

GPU to 72 alone does roughly as many P-1 as LL tests completed per day. Combine that with the many P-1 workers on PrimeNet who don't go through GPU272, I'm pretty sure P-1 is keeping ahead of LL testers.

Even so, increasing bounds would not be a good idea; a lot of work has been put into getting the bounds selection to be as efficient as possible, meaning balancing finding a factor vs. how much effort could have been put into an LL test instead of P-1 work. Increasing bounds may push P-1 throughput to be roughly equal to LL throughput, but GIMPS would progress a bit slower for the same total amount of work.

Edit: Whoops, cross post.

Prime95 · 2012-07-06, 18:20

Quote:

Originally Posted by Dubslow

Even so, increasing bounds would not be a good idea; a lot of work has been put into getting the bounds selection to be as efficient as possible, meaning balancing finding a factor vs. how much effort could have been put into an LL test instead of P-1 work.

Some people feel that finding a factor is more satisfying than 2 matching LL tests. For those people, it makes sense to increase the P-1 bounds even though it decreases GIMPS total throughput.

MrHappy · 2012-07-06, 18:38

But wouldn't it be better (in the sense of personally finding as many factors as possible) to lower the bounds to find more factors per time as the chance to find a factor does not increase proportionally to the time spent?
But that leaves us with "incomplete" P-1 before LL... andafterwards P-1 cannot be taken to the next level as easy as TF.

James Heinrich · 2012-07-06, 18:42

Quote:

Originally Posted by MrHappy

But wouldn't it be better (in the sense of personally finding as many factors as possible) to lower the bounds to find more factors per time as the chance to find a factor does not increase proportionally to the time spent?

If you want to find as many P-1 factors as possible, look at smaller exponents. There are many that have had P-1 poorly done, and re-doing them with better bounds can be done pretty quickly on modern hardware and you can easily find several factors per day, and not mess up GIMPS with leaving badly-done P-1s on PrimeNet.

Jwb52z · 2012-07-08, 15:02

I think something strange has happened. I was looking up exponent M56412857 that my copy of Prime95 says found a factor a few hours ago. I used the http://mersenne-aries.sili.net/expon...ponentdetails= page to look it up. I noticed that the factor Prime95 says it found from my use was already listed, but not as a P-1. I went ahead and manually submitted my result copying it from my result file and it mentioend something about "skipping the known factor" and now it's listed as mine. I wonder if someone should investigate this if it was already a known factor somehow.

LaurV · 2012-07-08, 15:16

There is nothing wrong. The PrimeNet data base (to which P95 reports) is separate. When a factor is found, it does not say in the "exponent status" report who found the factor. The other data base (from James, to which you reported the factor) search the first data base on time basis and gets the factors that were reported meantime, but it can't guess who reported them and which method was used to find them. When you reported your factor you just clarified those aspects.

2012-07-03, 22:59	#1366
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	Doing stage 2 depends on the results from stage 1. If you have a save file for B1o and B2o, if you want to increase B1o, then you will lose any stage 2 work you have done. This is why Prime95 ignores any new B1 with an old B2, because that would mean throwing out the previously done S2 work. You can always start any stage 2 bound from an arbitrary B1, if you have the save file for B1. Last fiddled with by Dubslow on 2012-07-03 at 23:00

2012-07-04, 07:25	#1367
LaurV Romulan Interpreter Jun 2011 Thailand 7·1,373 Posts	B2 does not matter. If you have old files saved at the end of the stage 1, then you can extend B1 (no matter what you do with B2, increase it or decrease it) and the work will be resumed from the old saved file. Having B1new>B1old is always better, no matter how the relation between B2old and B2new. Stage 1 is the "certitude". Stage 2 is more or less a "lottery", finding the lucky number... Moreover, there must be a single lucky number, if there are two (between B1 and B2) the stage 2 will fail. This is like fishing, in stage 1 you start taking the water out from the lake. If during this process you catch a fish, is yours, and the job is finished. If not, you can return any time and take more water out from the lake, assuming the status/level of water is the same, it did not rain or someone put the water back (i.e. if you have the saved file). In stage 2, you can take a boat, chose your favorite fishing net and go fishing. You can use many nets in the same time, 2, 6, 30, or a full Brent-Suyama set, but when you catch a fish, you must catch all his brothers in the same time, otherwise the brothers which are free will sink your boat. With these rules you may be lucky and find a fish with no brother (a single big factor of q-1, or of k, between B1 and B2), or you can catch a small family in the same time, if it is really small (like two brothers only, one brother is 6k-1 and another is 6k+1 ) But generally you will come back empty-handed, wet, and swimming.... Taking water out of the basin is easier, more certain, and... safe. Comic note: for mersenne numbers this method should be called "q-1" or "k" . No disrespect for Pollard, but we use p as the prime exponent, so if p is a prime, the factors which Mp might have, are usually denoted q. So, the method tries to find a factor q of Mp=2^p-1, and it will succeed if all prime factors of q-1 are small enough. Using "p-1" here is confusing and wrong. OTOH, if q divides Mp, then q is always of the form q=2kp+1, so we are in fact looking for prime factors of 2kp, or more exact, factors F=f^x of k=(q-1)/(2p)), with f prime and x natural. If all such factors F of k are under B1 (we say k is "B1-power-smooth", or easier, just "smooth") then the "q-1" method will always find the factor q of Mp in stage 1. Last fiddled with by LaurV on 2012-07-04 at 07:29

2012-07-06, 17:39	#1368
MrHappy Dec 2003 Paisley Park & Neverland 5×37 Posts	Questions, questions, questions. Do we currently complete enough P-1 per day? Would it be a good idea to up the P-1 bounds to search deeper? Or, on the other hand, to lower the bounds to complete (say) double the exponents at (say) only 20% less chance to find a factor?

2012-07-06, 18:00	#1370
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 1C35₁₆ Posts	GPU to 72 alone does roughly as many P-1 as LL tests completed per day. Combine that with the many P-1 workers on PrimeNet who don't go through GPU272, I'm pretty sure P-1 is keeping ahead of LL testers. Even so, increasing bounds would not be a good idea; a lot of work has been put into getting the bounds selection to be as efficient as possible, meaning balancing finding a factor vs. how much effort could have been put into an LL test instead of P-1 work. Increasing bounds may push P-1 throughput to be roughly equal to LL throughput, but GIMPS would progress a bit slower for the same total amount of work. Edit: Whoops, cross post. Last fiddled with by Dubslow on 2012-07-06 at 18:00

2012-07-06, 18:38	#1372
MrHappy Dec 2003 Paisley Park & Neverland 5·37 Posts	But wouldn't it be better (in the sense of personally finding as many factors as possible) to lower the bounds to find more factors per time as the chance to find a factor does not increase proportionally to the time spent? But that leaves us with "incomplete" P-1 before LL... andafterwards P-1 cannot be taken to the next level as easy as TF.

2012-07-08, 15:02	#1374
Jwb52z Sep 2002 2×3×7×19 Posts	I think something strange has happened. I was looking up exponent M56412857 that my copy of Prime95 says found a factor a few hours ago. I used the http://mersenne-aries.sili.net/expon...ponentdetails= page to look it up. I noticed that the factor Prime95 says it found from my use was already listed, but not as a P-1. I went ahead and manually submitted my result copying it from my result file and it mentioend something about "skipping the known factor" and now it's listed as mine. I wonder if someone should investigate this if it was already a known factor somehow.

2012-07-08, 15:16	#1375
LaurV Romulan Interpreter Jun 2011 Thailand 7·1,373 Posts	There is nothing wrong. The PrimeNet data base (to which P95 reports) is separate. When a factor is found, it does not say in the "exponent status" report who found the factor. The other data base (from James, to which you reported the factor) search the first data base on time basis and gets the factors that were reported meantime, but it can't guess who reported them and which method was used to find them. When you reported your factor you just clarified those aspects.