mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-03-23, 17:33   #1
bur
 
Aug 2020

3·5·11 Posts
Default Doing P-1 on known composite Mersennes

To get some variation from prime hunting, I want to do factoring of known composites and thought that working on Mersennes would be a good way to do that.

Since the computer won't have a good GPU, TF doesn't make much sense from what I read. ECM is maybe a bit extreme for a newcomer, so P-1 seems to be a good choice.

How do I best go about it? I know I could just let GIMPS decide what to do, but to me it's much more fun to work as manual as possible. I know also I can use worktodo.txt to request specific types of work and exponents.

My questions are (and I hope they aren't stupid, I couldn't find answers to them):
  • How do I (can I?) use mersenne.ca to find an exponent that is known composite and in the stage where P-1 makes sense?
    .
  • How do I know which B1 values makes sense? B2 seems to be often chosen as 100x B1. I know these lists, but not how to use them to find a good choice for the next attempt.
    .
  • Or should I use this calculator? What do the 20x 40x 60x and so on mean? Does the calculator take into account what P-1 work has already been done?
    .
  • How do I determine how many workers to use for each P-1 assignment? The CPU will likely be a i9-10900K.
    .
  • And last, I read stage-2 of P-1 takes a lot of memory. Does that mean it'd be useful to install more than 16 GB?

If this is explained somewhere and I missed it, please let me know. Preferrably with a link to the ressource in question. ;)
bur is offline   Reply With Quote
Old 2021-03-23, 18:12   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

3·5·499 Posts
Default

I'll let others answer your P-1 questions.

ECM may be the easier choice. Just get version 30.5 and set your available memory and work preference to ECM. All the B1/B2 choices will be made for you.
Prime95 is offline   Reply With Quote
Old 2021-03-23, 18:51   #3
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

23×3×19 Posts
Default

Quote:
Originally Posted by bur View Post
How do I (can I?) use mersenne.ca to find an exponent that is known composite and in the stage where P-1 makes sense?
A few weeks ago I have asked James for a tool that's meant for exactly this purpose. You can find it here. Discussion about the tool can be found in the mersenne.ca thread, here on the forum.

Quote:
Originally Posted by bur View Post
How do I know which B1 values makes sense? B2 seems to be often chosen as 100x B1. I know these lists, but not how to use them to find a good choice for the next attempt.
In the newest versions of Prime95, B2 is chosen automatically, based on various settings of your machine and workers. B1 depends on what range of exponents you want to do P-1 in, and how much of it. I am now doing P-1 in the 9M range (quite a lot of factors) with B1 = 1,000,000, and B2 is often chosen to be 76,000,000 on my machine.

For the purpose of finding Mersenne PRP-CFs, I suggest somewhere between 1M and 10M, to be optimal for both P-1 time length and the PRP-CF test length. Lower ranges are almost useless for P-1, as there are mostly non-k-smooth factors (hard to find by P-1).

Quote:
Originally Posted by bur View Post
Or should I use this calculator? What do the 20x 40x 60x and so on mean? Does the calculator take into account what P-1 work has already been done?
You should use the calculator to find the optimal value of B1 you want to plug into the tool I mentioned, which will give you worktodo lines with the given B1.

20x and similar are the ratios B2/B1, this will be automatically chosen by Prime95.

I don't think it takes previous work into account.

Quote:
Originally Posted by bur View Post
How do I determine how many workers to use for each P-1 assignment? The CPU will likely be a i9-10900K.
Run a throughput benchmark for the FFT size of the range you will be factoring. If you choose say 5M range, you should expect the FFT size to be about 256K. You will have to look at the numbers for that particular FFT size and those near it.

I recommend running the benchmark according to the settings in the picture. This will benchmark the 1M to 10M range and should take about 10 minutes in total.

When you complete the benchmark, look at your wanted FFT size, and compare the throughput numbers at the ends of the result lines. That one with the highest throughput is the best one.

For 10900K, my prediction is, that 10 worker option with 1 core per worker will be best up to about 256K FFT, or about 5M range, and up from there, the 5 workers with 2 cores per worker will be the best option.

Quote:
Originally Posted by bur View Post
And last, I read stage-2 of P-1 takes a lot of memory. Does that mean it'd be useful to install more than 16 GB?
Stage 2 takes a lot if you allow it to take a lot. It would run fine with 16 GB even for 10 workers because they probably wouldn't run in-sync and do stage 2 at once, but 32 GB might be better. However, I am not educated in the terms of memory usage specifics for stage 2, so someone else should give their opinion on this too.



Lastly, I recommend those B1s for a swift but not too weak P-1 factoring:
1M range - 10,000,000
2M range - 5,000,000
3M range - 3,000,000
4M range - 2,500,000
5M range - 2,000,000
10M range - 1,000,000

Yes, basically so that the product of B1 * exponent size is about 10,000,000,000,000. Try it out, and if you decide you want it faster or slower, change it accordingly. Time (equivalent to the amount of work) scales about linearly with the B1 size.
Attached Thumbnails
Click image for larger version

Name:	benchmark_settings_10900k.png
Views:	23
Size:	6.9 KB
ID:	24559  
Viliam Furik is offline   Reply With Quote
Old 2021-03-24, 04:21   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25·5·59 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
Yes, basically so that the product of B1 * exponent size is about 10,000,000,000,000.
This rule is basically for (very) small exponents, who had some (or a lot) of P-1 already. It won't work for the front P-1 (which is most needed). At 100M+ exponents currently, having a 10k or 100k B1 is ridiculously low. The best way for you to get a "feeling" is to go here, fill your expo in the second table (no need exact, no need prime, just pick an expo in the range you do, then the next prime will be chosen for you), fill the desired probability (between 3-5 percent) and the factored bitlevel, then look at the generated result (new table). The 1:50 or 1:100 ration B1 to B2 is not always the most efficient. This also depends of many things, like pre-factored level. Then, fix some limits and start crunching. At 5% probability, you will find a factor in about 20 trials.

I usually take 1.5M for B1 at the front, opposite to the ~800k-1M recommended, and use a 30x or 50x for B2 according with how fast I want to go through the assignments. Doing a bit more work may turn a larger factor, but this is "personal vanity", not really supported by numbers. The most efficient (factors found to amount of work done) work is said to be when stage 2 takes the same amount of time (wall clock) as stage 1. And this depends on your system.

Alternative is to let P95 chose the numbers for you, if you do that in the CPU. Just select "P-1" as work type.

Last fiddled with by LaurV on 2021-03-24 at 04:24
LaurV is offline   Reply With Quote
Old 2021-03-24, 12:02   #5
bur
 
Aug 2020

16510 Posts
Default

Quote:
Originally Posted by Prime95 View Post
I'll let others answer your P-1 questions.

ECM may be the easier choice. Just get version 30.5 and set your available memory and work preference to ECM. All the B1/B2 choices will be made for you.
Thanks, this is certainly the most efficient choice, but I like to know what's going on under the hood. So I'd like to manually choose an exponent and the parameter at least for a while.

Quote:
Originally Posted by Viliam Furik View Post
A few weeks ago I have asked James for a tool that's meant for exactly this purpose. You can find it here. Discussion about the tool can be found in the mersenne.ca thread, here on the forum.
Thanks, I'll look it up.

Quote:
In the newest versions of Prime95, B2 is chosen automatically, based on various settings of your machine and workers. B1 depends on what range of exponents you want to do P-1 in, and how much of it. I am now doing P-1 in the 9M range (quite a lot of factors) with B1 = 1,000,000, and B2 is often chosen to be 76,000,000 on my machine.
But if someone has already done P-1 work on that exponent, do I simply increase B1 to a value larger than theirs?

Quote:
For the purpose of finding Mersenne PRP-CFs, I suggest somewhere between 1M and 10M, to be optimal for both P-1 time length and the PRP-CF test length. Lower ranges are almost useless for P-1, as there are mostly non-k-smooth factors (hard to find by P-1).
So these smaller factors would be found by ECM?

Quote:
You should use the calculator to find the optimal value of B1 you want to plug into the tool I mentioned, which will give you worktodo lines with the given B1.
20x and similar are the ratios B2/B1, this will be automatically chosen by Prime95.
I don't think it takes previous work into account.
If it doesn't consider previous work, how do I adjust for that?

Quote:
Run a throughput benchmark for the FFT size of the range you will be factoring. If you choose say 5M range, you should expect the FFT size to be about 256K. You will have to look at the numbers for that particular FFT size and those near it.
Ah, I didn't know it worked for P-1 as well.

Thanks again, that was really helpful.



Quote:
Originally Posted by LaurV
This rule is basically for (very) small exponents, who had some (or a lot) of P-1 already. It won't work for the front P-1 (which is most needed). At 100M+ exponents currently, having a 10k or 100k B1 is ridiculously low. The best way for you to get a "feeling" is to go here, fill your expo in the second table (no need exact, no need prime, just pick an expo in the range you do, then the next prime will be chosen for you),
Thanks for the detailed explanation on choosing B1, only question left is, what if someone else already did a P-1 with these settings? Do I just increase B1 by 10% or something like that?

Last fiddled with by bur on 2021-03-24 at 12:06
bur is offline   Reply With Quote
Old 2021-03-24, 12:49   #6
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

24×11×29 Posts
Default

You can quickly get a good idea of what P-1 bounds are appropriate, by https://www.mersenne.org/report_expo...3001000&full=1 or similar.
https://www.mersenne.ca/exponent/107500007 is an example where P-1 bounds were not adequate, and TF was a bit deeper than usual, so overall the probability of finding a factor is close to what it should be, although a little less efficiently reached.
I would use the GPU72 row's TF depth and P-1 bounds on https://www.mersenne.ca/exponent/108500057.
It's more efficient to go for the full bounds that will retire the P-1 need the first time. See https://www.mersenneforum.org/showpo...9&postcount=30 and https://www.mersenneforum.org/showpo...9&postcount=20
On mprime/prime95, give it enough allowed memory usage to be efficient and reach suitable bounds, but not so much that the console response is slow or virtual memory is thrashing, madly paging out to disk. GBs not MBs for wavefront P-1.

Last fiddled with by kriesel on 2021-03-24 at 12:54
kriesel is offline   Reply With Quote
Old 2021-03-24, 13:07   #7
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

23×3×19 Posts
Default

Quote:
Originally Posted by bur View Post
But if someone has already done P-1 work on that exponent, do I simply increase B1 to a value larger than theirs?
Yes, you can run the P-1 with a higher B1, but often there was no P-1 done on already factored exponents because most of them have tiny factors, which were swept through long ago.

Quote:
Originally Posted by bur View Post
So these smaller factors would be found by ECM?
Some of them would, but ECM is probabilistic, in that it has only a certain probability of finding a factor with a given size, whereas P-1 (if done without computation errors, of course) will find it for sure if the bounds are high enough and there is a factor to be found.

Quote:
Originally Posted by bur View Post
If it doesn't consider previous work, how do I adjust for that?
You don't have to worry much about it, just run the P-1 with a higher B1 size.

Quote:
Originally Posted by bur View Post
Thanks again, that was really helpful.
You're welcome.

Quote:
Originally Posted by bur View Post
Thanks for the detailed explanation on choosing B1, only question left is, what if someone else already did a P-1 with these settings? Do I just increase B1 by 10% or something like that?
In that case, you can either increase the bound to some reasonable extent, balanced with the amount of work needed to be done. E.g. if I find an exponent in the 9M range with 1,000,000 P-1 done, I could either make it say 2,000,000 or just leave it and throw the same amount of work on other exponents. From a certain size up, for specific hardware, there is always a value above which you will just waste time waiting for it to complete. If you set it to be 1,000,000,000 for a 9M exponent, it is useful for a single specific exponent, but it's an inefficient waste of resources for mass factoring.
Viliam Furik is offline   Reply With Quote
Old 2021-03-26, 20:26   #8
bur
 
Aug 2020

3·5·11 Posts
Default

So for https://www.mersenne.ca/exponent/107500007, if I was determined to find a factor via P-1, which value for B1 would I use? Just increase it to 2,000,000?

Or as a more extreme example: https://www.mersenne.ca/exponent/200087 would I go with B1=100,000,000?

While for https://www.mersenne.ca/exponent/108500057 where no P-1 was ever done, I would just go with the 24,000,000 that GPU72 suggests?


To use an example, if I was to work on https://www.mersenne.ca/exponent/100003 and wanted to find another factor with 25% probability, I was told by https://www.mersenne.ca/prob.php?exp...ob=25&work=200 to use B1=17,164,935,784 and the following line worktodo.txt would make prime95 ask it to be assigned:
Code:
Pminus1=1,2,100003,-1,17164935784,2059792294080,67 (from the calculator)

Pminus1=1,2,100003,-1,2600000000,2600000000,67,"6400193,1113838336566049330755578765857" (from morefactors.php)
First of all, is that correct?

And is that 25% probability including the fact that 2 factors were already found, does it even matter?

And how do I know if ECM would make more sense? 413 GHz days would be about 12 days on that i9?


Another example https://www.mersenne.ca/exponent/200087, the calculator suggested B1=76131. But I know it was done to 50,000,000. So I force it to B1=100,000,000? For B2=3,000,000,000 it calculated 50% odds in 3 GHz days, which sounds like a nice first task.

Last fiddled with by bur on 2021-03-26 at 20:35
bur is offline   Reply With Quote
Old 2021-03-27, 00:44   #9
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

22·3·277 Posts
Default

One thing that might need to be pointed out is the P-1 method is not accrual. If you run P-1 using B1=1M on an exponent and then run P-1 again using B1=5M you are essentially re-running the 1M computations again along with the 1-5M range, unless you use a save file. Since this is posted in factoring thread instead of PrimeNet I’m not sure how all this works with Mersenne numbers. Others, feel free to correct my understanding. So, the most bang for the buck is to pick a B1 that your RAM can handle and not to consider incremental work.
RichD is offline   Reply With Quote
Old 2021-03-27, 02:33   #10
axn
 
axn's Avatar
 
Jun 2003

495910 Posts
Default

Your calculations are

You have to account for all the prior factorization work done, chief among them being ECM. Check here 100003 has had approximately 20% of t35 done, so you can assume no factors less than 30 digits. In the calculator, you should say how much pre-TF is done. 10^30 is about 2^100. Unfortunately, the calculator only goes up to 85. But give at least that and you'll see more realistic numbers. Same for 200087

EDIT:- Some better numbers. If you're willing to spend about 4000 GHzDays, you can get about 5% probability (closer to 4% practically) for 100003.
Subtract prior from new

Last fiddled with by axn on 2021-03-27 at 02:43
axn is offline   Reply With Quote
Old 2021-03-27, 18:24   #11
bur
 
Aug 2020

101001012 Posts
Default

Thanks, that's both good to know.


Now some technical questions, I added the lines to worktodo.txt and Prime95 startet work, but it apparently wasn't contacting primenet to get an ID. It didn't show up in my assignments at least. If the work was already assigned, shouldn't I see a status message?


I tried the manual assigment form, but it said "No assignment available meeting CPU, program code and work preference requirements". I couldn't find any info about this error message. I thought only LLR/PRP on large exponents was limited to trusted computers?


Additionally, to prevent prime95 from requesting new assigments, is adding NoMoreWork=1 to worktodo.txt the best way?

Last fiddled with by bur on 2021-03-27 at 18:25
bur is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The spread of low k´s (1 up to 13) of Mersennes Kalli Hofmann Probability & Probabilistic Number Theory 2 2020-09-13 13:39
Possible obfuscation for Mersennes paulunderwood Miscellaneous Math 3 2019-01-24 03:14
Composite integers n satisfying prime exponents of Mersennes carpetpool carpetpool 7 2017-01-05 04:36
Betting on Mersennes -- update #1 CRGreathouse Lounge 10 2016-03-31 13:41
Stars and Mersennes David John Hill Jr Science & Technology 2 2009-12-13 09:47

All times are UTC. The time now is 23:44.

Sat May 8 23:44:23 UTC 2021 up 30 days, 18:25, 0 users, load averages: 2.15, 2.59, 3.03

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.