mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2017-11-21, 22:04   #1
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·7·47 Posts
Default Run P-1 before PRP tests

The current timing for PRP is about 2 hours. Since most Mersenne numbers with small factors have very little P-1 done, I would like Prime95 to be changed so it performs P-1 with bounds B1 = 500000, B2 = 15e6 before attempting PRP. In this way more factors can be found, and no time is lost running PRP on numbers that can be easily factored.

Last fiddled with by alpertron on 2017-11-21 at 22:05 Reason: Typo
alpertron is offline   Reply With Quote
Old 2017-11-22, 03:13   #2
GP2
 
GP2's Avatar
 
Sep 2003

2·1,289 Posts
Default

Is it worthwhile?

How much time will the P−1 test take, and how does it compare to the time taken by the PRP-cofactor test?

This question will depend on the exponent range, since the time complexity required for PRP-cofactor testing rises more sharply than it does for P−1 testing, as the exponent increases.

And what percentage of exponents will have new factors discovered by P−1?

For the ranges we are currently doing, P−1 will probably find factors for only a very small number of exponents, and it will be simple and quick to re-run PRP for the new cofactors of those few exponents. Requiring mandatory prior P−1 instead for every exponent would enormously slow down the PRP testing work.

Currently nearly all the new factors of small exponents are being found by user TJAOI with a "by k" methodology. Most of the rest are being found by ECM, and a few by TF.

Pretty much none are being found by P−1, but hardly anyone (and maybe no one) is even attempting these. It's not surprising, since there is no Primenet credit given for unsuccessful P−1 testing of exponents that already have at least one known factor.

I myself did some no-credit P−1 testing of small exponents. (Most of that was done about a year ago). For example, I tested the 400k range with B1=5e6 B2=40e6 and found only six new factors (for M416497, M432349, M436739, M450019, M450383, M499033). I also did the ranges below 400k and did find considerably more factors there, but the 400k range itself was mostly unfruitful, so I didn't continue past 500k.

Part of the reason, I think, is that ECM already found many of the factors that P−1 would have found. And since a year ago, even more ECM and also TJAOI discoveries have been made.

Before bundling this P−1 testing into PRP-cofactor testing as a mandatory prerequisite, it would be essential to do a proof-of-concept. Choose a range and P−1 test it and report how many new factors were found.

Due to the greater time complexity of PRP-cofactor testing vs. P−1 testing, there will be some point where it would make sense to do P−1 testing first, but we are probably not near that point yet. (The proof-of-concept testing suggested above might prove otherwise). However, at some point, nearly all the exponents already started getting routine P−1 testing before LL testing. So there is at best only a limited range of exponents (bounded both below and above) where it might make sense to do more P−1 testing, and it's not immediately obvious whether this range is the empty set.

Last fiddled with by GP2 on 2017-11-22 at 03:13
GP2 is offline   Reply With Quote
Old 2017-11-22, 11:27   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·7·47 Posts
Default

I have ran P-1 algorithm with the bounds cited above on exponents less than 2.3M with known factors and the computer found several hundred new factors.

Also the amount of ECM for exponents above that number is very low, especially for Mersenne numbers with known factors.

Last fiddled with by alpertron on 2017-11-22 at 12:20
alpertron is offline   Reply With Quote
Old 2017-11-22, 16:20   #4
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

102538 Posts
Default

I accept the fact that you know WAYYY more about P-1 than I do so feel free to elaborate on the following as you see fit.

What I have done is created a table with various B1/B2 bounds (yours is first) for P-1 in the range you suggest.
This specific table uses Exponent 2,600,001.
I'll explain the columns:

B1/B2: various choices for B1 and B2 bound for the new P-1
Pct: The odds of it finding a factor strictly based on this: http://www.mersenne.ca/prob.php
GD: The GhzDays to do the P-1 based on the same URL above.
-- Then 4 pairs of columns as follows (Most Exponents in the 2.6M range have existing P-1 runs with an estimated success rate of about 3.25% - 4%):
3.25: The number at the top of the pair of columns is the odds of the existing P-1 run finding a factor.
PerFac: The calculated number of P-1 with the new bounds required to find a factor taking into account the odds from the prior P-1 run
GD/F: The calculated GhzDays required to find a new factor based on the above parms. I suggest we want to minimize this number.

For example: From the first row: Statistically, 68.97 P-1 runs would be required to find a factor based on the net Percent of 4.70 - 3.25 (New - Existing P-1). Then based on 0.13 GhzDays per new P-1 it would take 8.97 total GhzDays of P-1 work to find the new factor.

NOTE: What this table does NOT take into account is the ECM work already done on these Exponents. More than I could bite off.

Code:
					3.25		3.50		3.75		4.00	
B1	B2	         Pct	GD	PerFac	GD/F	PerFac	GD/F	PerFac	GD/F	PerFac	GD/F
500000	15000000	4.70	0.13	68.97	8.97	83.33	10.83	105.26	13.68	142.86	18.57
1000000	20000000	5.45	0.21	45.45	9.32	51.28	10.51	58.82	12.06	68.97	14.14
2000000	40000000	6.62	0.42	29.67	12.46	32.05	13.46	34.84	14.63	38.17	16.03
2600000	52000000	7.08	0.53	26.11	13.84	27.93	14.80	30.03	15.92	32.47	17.21
2600000	26000000	6.32	0.39	32.57	12.70	35.46	13.83	38.91	15.18	43.10	16.81
3000000	60000000	7.34	0.61	24.45	15.01	26.04	15.99	27.86	17.10	29.94	18.38
4000000	80000000	7.86	0.82	21.69	17.77	22.94	18.78	24.33	19.93	25.91	21.22
5200000	104000000	8.33	1.06	19.69	20.87	20.70	21.95	21.83	23.14	23.09	24.48
petrw1 is online now   Reply With Quote
Old 2017-11-22, 16:44   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

24448 Posts
Default

For Mersenne numbers with small known factors in the range about 4.2M, there is no previous P-1 done, no ECM done and they were factored up to 64 bits. That means that I would find a factor in about 21 attempts.

At this moment I am running P-1 starting from 4.2M up.

Last fiddled with by alpertron on 2017-11-22 at 17:02
alpertron is offline   Reply With Quote
Old 2017-11-22, 17:04   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×13×107 Posts
Default

Does P-1 actually work on exponents with known factors like this?:

Pminus1=N/A,1,2,7508981,-1,100000000,10000000000,"45053887,60071849,285341279,585700519,26356523311,20333239254737,18694135089678809,281287549065522023,346309182073938289,367107436768162151,1211907173840894224264391"


I did some of these, but got error messages and no P-1 show up on the exponents:

Code:
Sending result to server: UID: athath/ec2-1xb, M7508981 completed P-1, B1=105000000, B2=3000000000, E=12, Wg8: 7B49A837
Sending result to server: UID: athath/ec2-1xb, M9100919 completed P-1, B1=50000000, B2=2000000000, E=12, Wg8: 91BADB7F

PrimeNet error 40: No assignment
P-1 result for M7508981 was not needed

PrimeNet error 40: No assignment
P-1 result for M9100919 was not needed

Last fiddled with by ATH on 2017-11-22 at 17:05
ATH is offline   Reply With Quote
Old 2017-11-22, 17:26   #7
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×7×47 Posts
Default

Just send them using the manual testing menu:

https://www.mersenne.org/manual_result/
alpertron is offline   Reply With Quote
Old 2017-11-22, 18:37   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

ADE16 Posts
Default

Thanks, I was pretty sure I had already tried this, but I guess I forgot.
ATH is offline   Reply With Quote
Old 2017-11-24, 00:04   #9
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×13×107 Posts
Default

Has anyone found factors with P-1 using the already known factors in the assignment?
ATH is offline   Reply With Quote
Old 2017-11-24, 00:52   #10
GP2
 
GP2's Avatar
 
Sep 2003

2·1,289 Posts
Default

Quote:
Originally Posted by ATH View Post
Has anyone found factors with P-1 using the already known factors in the assignment?
Yes, I've done this. For instance, for the exponents linked in the post above.

I did this with UsePrimenet=0 and submitted the results manually. You get no Primenet credit (unless you found a factor), but it does add a line to the History section.
GP2 is offline   Reply With Quote
Old 2017-11-24, 06:01   #11
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

17×251 Posts
Default

I can create a table using various B1/B2 bounds and looking up the following 2 values from

http://www.mersenne.ca/prob.php

- Percent: The odds of it finding a factor strictly based on this:
- GhzDays: to do the P-1 .

But that is time consuming

Can anyone point me at the formula used to compute these values myself knowing the Exponent, B1, B2 and Bits Factored used in that web-site.

When I try the "show source" link I get:

Code:
Fatal error: Call to undefined function htmlentities_safe() in /var/www/vhosts/mersenne.ca/httpdocs/prob.php on line 15
petrw1 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
p4 - 1.8 ghz - LL tests? joblack Hardware 12 2009-08-26 20:40
More P-1 tests dave_0273 Marin's Mersenne-aries 1 2006-03-23 00:03
PRP => LL-tests? Holmes Math 1 2005-05-13 17:18
Yet another set of 20 P-1 tests GP2 Completed Missions 5 2003-09-30 22:10
Bad LL Tests outlnder Lounge 8 2002-10-21 00:12

All times are UTC. The time now is 18:33.

Sat Mar 28 18:33:00 UTC 2020 up 3 days, 16:06, 2 users, load averages: 1.52, 1.57, 1.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.