P-1 on Fermat numbers

[Andrew Usher]

I'm sure it's been thought of before, but there should be some way to find P-1 that's been done on Fermat numbers. If people could see the bounds previously reached, they'd be more willing to start their own runs. I, who don't think my computers could surpass what's already been done but am not sure, think this way. In any case P-1 can't normally be subdivided, so should be done with the best computational resources.

TF quickly reaches diminishing returns, as is well-known, and no new ECM Fermat factors have been found since 2011 even though recorded effort continues. So P-1 looks attractive, especially for F25-29 (24 has no known factor so has probably had significant outside work), but every one through 33 (which Ernst Mayer is supposed to get) should have a non-negligible shot. Since there are so few Fermat numbers, anyone interested in high P-1 would probably best contribute there if possible rather than to Mersennes.

Perhaps mersenne.ca could add pages for Fermats through 33.

[Batalov]

See section 1 here - https://www.mersenne.org/report_ecm/
P-1 likely will not be productive with B1 less than 10 times that of ecm limits that are already performed.

I vaguely remember that there should be some standalone thread about Fermat P-1 deep in the forum:
https://www.mersenneforum.org/showthread.php?t=15614
https://www.mersenneforum.org/showthread.php?t=20011
https://www.mersenneforum.org/showth...675#post288675
...
https://www.google.com/search?q=P-1+...senneforum.org

[Andrew Usher]

None of those links are particularly useful. I have heard the '10 times' rule but really that only is an estimate for the P-1 that will take the same time as _one_ ECM curve. Surely you want to run longer than that; judging by what sensible people actually do, 100 times is a better minimum.

Actually, one can directly calculate the t-value divided by the exponent and compare that to the bounds you're thinking of using. A B1 equal to the fourth root of that gives a reasonable chance of finding a factor, and that is achievable on the larger Fermats (22 and higher), B1 equal to the cube root is good, while B1 less than the fifth root is not worthwhile. (On M1277, the worst case I know for P-1, B1 would need to be near 10^15.)

Ernst was going to use B1 = 10^7 on F33, and that should double with each lower exponent - well, relax it a bit on numbers with known factors, but you're still talking thousands of 'real' GHz-days. Kriesel has implied, though, that for P-1 of such length, ECC memory is a must because the chance of error is too high and P-1 has no real checking (maybe that's the next goal for P95 ...), which would be unfortunate because few people have ECC and you can't add it to existing systems.

Anyway the main point was about some record of previous P-1 attempts, and that that would be as useful as for Mersennes, and more so than for ECM.

[kriesel]

ECC does great things for computation reliability. (I have a 3-YEAR-long-and-climbing test run in LL without Jacobi check, whose interim res64s match a check run on much faster hardware. Several old ECC equipped systems have NO bad final LL residues logged in over 4 years of running each system.)
ECC can be had economically in multiple ways;

• buy used dual-Xeon pro grade workstations with it on eBay;
• buy used Xeon Phi systems;
• rent or borrow in cloud computing such as Google Colab free or paid, Amazon, etc.

There's a whole reference info thread on GIMPS app cloud computing on Google Colab. It's possible to implement P-1 with GEC and Jacobi symbol error checks, as Mihai did in gpuowl v7.x simultaneous PRP & P-1 stage 1, but that is the only such implementation I know of at this point, and GPU ram limits P-1 exponent to far below the F33 level, which needs ~120. GiB in the Mlucas implementation, and would need considerably more in a prime95 v30.8 style polynomial pairing implementation.

[preda]

Originally Posted by Andrew Usher

...

Concerning the splitting of P-1, it is only the first-stage that can't be split. So get a powerful machine to run first-stage to a high B1, and afterwards fan out chunks of second-stage to multiple users.

So we're looking at a giant first stage. Well, it can be error checked! maybe the error check does need to be implemented in mprime, but it's not very hard -- it's similar to the existing GEC, just a bit more complex; and just as efficient overhead-wise.

[Andrew Usher]

OK, what exactly do you have in mind? Could the second stage then be done without error checking? It would require the full amount of memory on each machine (by the way, this is why we can't factor RSA-1024 - if the memory as well as CPU cycles could be perfectly split, it would be a feasible distributed computation).

And I'm pretty sure that method of splitting up won't work with the new 30.8/GMP-ECM continuation, which I'd judge necessary for F22-26, so this would be limited to 27-32 - you can throw in MM31, it hasn't been done but there should be interest - and B2 = 100*B1 presumably.

[kriesel]

Originally Posted by Andrew Usher

you can throw in MM31, it hasn't been done but there should be interest - and B2 = 100*B1 presumably.

~MM31 P-1 is feasible in Gpuowl or Mlucas, including stage 2 given sufficient GPU ram (~32GB) or system ram (~64) respectively (and more is better in stage 2), but would require adding support of ~120M fft length to mprime, which currently tops out at 64M length on AVX512-capable CPUs (so Fermat numbers above F30 would not be feasible in mprime currently). There are 4 known prime factors for MM31 already. https://www.mersenne.ca/exponent/2147483647 Some of those can be used to quickly test P-1 is working properly for small bounds on large fft length. IIUC both gpuowl and Mlucas will find the smallest in stage 1 GCD and terminate. I don't recall either having the ability to ignore specified known small factors and continue in spite of finding them. The min B2 for finding the smallest known factor is smaller than the min B1 in those programs, so the smallest should be found in stage 1.
Per http://www.doublemersennes.org/mm31.php MM31 has already been TF up to k=450E15, f=2kp+1 = 2 * 450E15 * (2^31-1) + 1 ~ 90.64 bits. MMFF can go to 96 bits on that per https://mersenneforum.org/showpost.p...&postcount=382

[Andrew Usher]

My last post was mainly intended to indicate that I would be willing to contribute cycles to such a project, if that were possible. I actually did not start this thread at all to ask or demand that anyone do such P-1 - merely to get information about what, if any, had been done. Obviously I wouldn't be disappointed to see it done, however.

Most people in the project use the hardware they already have, rather than buy or rent anything specifically for it; posters here may not be typical. This makes sense for a volunteer project - is not the main point simply to use the idle computing power you already have for something rather than nothing? This explains the scarcity of ECC systems, even if they aren't terribly hard to acquire.

I used the calculator to find that, given the TF and ECM done, the longest runs (doubling back from B1=10M for F33, est. 20,000 GHz-day stage 1, and B2 = 100*B1) would have a factor probability >5% for each of F27-32 and MM31. I do know these all have known factors already.

[kriesel]

Originally Posted by Andrew Usher

My last post was mainly intended to indicate that I would be willing to contribute cycles to such a project, if that were possible.

Cool.

I actually did not start this thread at all to ask or demand that anyone do such P-1

Didn't think so.

- merely to get information about what, if any, had been done.

I'm unaware of MM31 prior P-1, and unfamiliar with Fxx history. I'd guess there is a thread or more for Fxx.

Most people in the project use the hardware they already have, rather than buy or rent anything specifically for it; posters here may not be typical. This makes sense for a volunteer project - is not the main point simply to use the idle computing power you already have for something rather than nothing? This explains the scarcity of ECC systems, even if they aren't terribly hard to acquire.

Some cloud computing is free, including a free tier of Google Colab, and generally offers pro grade GPUs and ECC system ram. GPU manufacturers have free test programs, as part of their sales effort.

I used the calculator to find that, given the TF and ECM done, the longest runs (doubling back from B1=10M for F33, est. 20,000 GHz-day stage 1, and B2 = 100*B1) would have a factor probability >5% for each of F27-32 and MM31. I do know these all have known factors already.

A quick test in gpuowl v7.2-53 for a 50M test P-1 (7 minutes on radeon vii bounds 100k, 4.1M) confirms it finds a factor, and terminates the PRP run. At 14G maxalloc it quickly terminated with an assert on MM31; maxalloc 15.5G runs but will fail to run stage 2 since 24 buffers are required and a Radeon vii's 16GB will not hold that many; and it will hit a problem before completing stage 1 GCD since it sets up the stage 2 buffers in parallel with doing the GCD. V6.11-380 does the beginning of stage 2 in parallel with stage 1's GCD so will also fail on a 16GB GPU before completing the stage 1 GCD. Some server grade GPUs, and some very recent high end consumer GPUs, offer enough ram for an attempt. One could run nearly all of stage 1 on personal equipment and then move it elsewhere before the big-gpu-ram requirement hits, which would reduce cost if renting cloud computing for only the latter part. Or perhaps another forumite would agree to run the latter part.
I may add MM31 to the list of P-1 reliability test exponents at https://www.mersenneforum.org/showpo...8&postcount=31

And note that used old ECC systems have been available on Ebay at times for under $250/unit (albeit only 12GB ram as listed).

[Andrew Usher]

You mangled your last attempted quote.

You should know about this kind of P-1 as the runs you're doing on your OBD numbers are of similar size and seem to be proceeding successfully, and also that it's preferable to further TF at the level that's been achieved. The early aborts are obviously a fixable problem (best, don't do the GCD after stage 1).

I have not found any threads on actual P-1 done (or attempted) on Fermat numbers except one very old one where I think the person wrote his own program as he had been unable to do the GCD (he ran stage 1 on F31 to 300,000 - no factor).

My 'plan' was a reply to Preda (name?) who proposed splitting the stages, which sounded good to me, and I don't think he particularly had in mind using a GPU for either.

[kriesel]

Originally Posted by Andrew Usher

You mangled your last attempted quote.

fixed, thanks.

The early aborts are obviously a fixable problem (best, don't do the GCD after stage 1).

That makes no sense to me. If P-1 stage 2 can not run, and stage 1 gcd is not run (by altering gpuowl source code and recompiling?), there's no point in running any of stage 1. We'd like to find a new factor in stage 1 and avoid the high ram requirements & more run time of stage 2. Finding a factor in P-1 requires performing at least one GCD AFAIK.
Ernst is making a P-1 attempt on F33 with Mlucas 20.1.1 and its stage 2 is split to multiple users IiRC.
My OBD P-1 attempts and M2253M in Mlucas 20.1.1 have completed stage 1 and GCD, and begun stage 2. Possibly the OBDs will be S2 split, later. Small bounds can be done quickly (days). Suitable bounds are months or years. Hence reliability is a must, and ECC helps that considerably.