Ignorant question about P-1.

[jasong]

I've decided to involve myself in the Seventeen or Bust P-1 subproject. While it's useful to remove the numbers we're managing to remove, it would be helpful if we could remove more. This causes me to ask the following question:

I have only a vague idea of how p-1 works. I'm aware that if you find a factor, than that factor, minus 1, has a lot of factors below the B1-value, and 1 factor between B1 and B2. My question is, is there any useful way to re-use calculations to try another bound? For instance, if one did a calculation, failed to find a factor, and only wanted to change the B2 bound, can they recycle the calculation in any way?

I realize that if this were possible, it would probably already have been implemented, but I figured a stab in the dark is better than nothing.

[bsquared]

I don't know anything about the Seventeen or Bust projecct, but in general for P-1 the residue after stage 1 can be saved, and calculations resumed with either a larger stage 1 bound, or a different stage 2 bound. GMP-ECM does this already.

Its also possible to save the state after stage 2, to B2, and then resume with a larger B2. But if I understand GMP-ECM correctly, this would involve a prohibitive amount of storage to do, and so isn't implemented.

Simpiler implementations of P-1 don't involve as much storage, and can more easily resume stage 2 with a larger bound. I've written a version that does this.

[jasong]

I would love to have someone mathematically inclined(no, I'm not suggesting bsquared isn't mathematically inclined) to figure out if this would be worthwhile, and if so, to help me implement it. It would be even better if this knowledge, if it's considered useful, could be relayed to the Seventeen or Bust forum, hosted by Free-DC.

[bsquared]

I'm fairly new to this forum, and DC projects in general, so I'm probably not the best resource. Also, Seventeen or Bust seems to use prime95 for P-1, which I don't know much about.

However, I'm willing to speculate that if prime95 doesn't have a feature to save residues after stage 1, there is probably a good reason for it. For one, the residue would be huge given the size of the input number in either SoB or GIMPS. Storing/Serving these huge residues may not be practical.
And two, it might not make sense, from the point of view of maximizing the *project* throughput, to test with P-1 to higher and higher bounds. The extra time spent might be greater than the primalty testing saved. I think there are helper programs for SoB and probably for gimps, to help determine the optimal B1,B2 bounds for P-1.

[Citrix]

Originally Posted by jasong

I would love to have someone mathematically inclined(no, I'm not suggesting bsquared isn't mathematically inclined) to figure out if this would be worthwhile, and if so, to help me implement it. It would be even better if this knowledge, if it's considered useful, could be relayed to the Seventeen or Bust forum, hosted by Free-DC.

Jasong, Prime95 stores the B-1 number in one of the temp files but always starts B2 from the last b1 value. I don't know if there is a setting to make B2 start from some value. (The B1 value is stored in one of the intermediate files)

[ewmayer]

Originally Posted by bsquared

However, I'm willing to speculate that if prime95 doesn't have a feature to save residues after stage 1, there is probably a good reason for it. For one, the residue would be huge given the size of the input number in either SoB or GIMPS. Storing/Serving these huge residues may not be practical.

The p-1 *residue* is exactly the same size as an LL test residue - I think you may be getting misled by the p-1 stage 2 *memory* usage, which is higher than LL because stage 2 involves precomputing many small powers of the stage 1 residue in order to speed up the stage 2 powering - but those added powers need not be save to checkpoint files, all you ever need to restart a stage 2 interval (with arbitrary bounds) is the original stage 1 output.

That's the neat thing about stage 2, it's completely distributable, i.e. many people can do separate stage 2 intervals independently, all starting with a single common stage 1 residue.

[bsquared]

Originally Posted by ewmayer

The p-1 *residue* is exactly the same size as an LL test residue

right. which is big, when the number you are factoring is big (unless I'm completely out to lunch ). The residue is on the order of the size of the input (i.e. 40 million bits or 5Mbyte or so).

All i meant was that if you were going to set up a server of the P-1 residues of mersenne prime candidates, so that others could extend the P-1 factorizations, that would chew up a lot of storage/bandwidth. Say, 10,000 candidates * 5Mbyte = 50Gbyte to serve.

[ewmayer]

Originally Posted by bsquared

right. which is big, when the number you are factoring is big (unless I'm completely out to lunch ). The residue is on the order of the size of the input (i.e. 40 million bits or 5Mbyte or so).

All i meant was that if you were going to set up a server of the P-1 residues of mersenne prime candidates, so that others could extend the P-1 factorizations, that would chew up a lot of storage/bandwidth. Say, 10,000 candidates * 5Mbyte = 50Gbyte to serve.

50 GB - no big deal nowadays. And people download several-MB-large files all the time, although thousands of such per day obviously needs pretty good server bandwidth.

Anyway, for SOB the distributed-stage 2 method isn't likely to be of interest for regular crunching - I only mentioned it to illustrate some of the basic properties of the p-1 algorithm.