mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Wagstaff PRP Search

Reply
 
Thread Tools
Old 2018-07-27, 19:24   #45
sweety439
 
sweety439's Avatar
 
Nov 2016

26×3×13 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Are all factors of Wagstaff numbers (2^p + 1)/3 of the form 2kp + 1? If so then yes, a similar heuristic would drop out.
Yes, since all prime factors of Phi_n(2) are of the form kn+1 (maybe except the largest prime factor of n, like the case n = 6, 18, 20, 21, 54, 100, 110, 136, 147, 155, 156, 162, 253, 342, 486, 500, ...), and (2^p+1)/3 is Phi_{2p}(2), thus all prime factors of it are of the form 2kp+1.

Last fiddled with by sweety439 on 2018-07-27 at 19:25
sweety439 is offline   Reply With Quote
Old 2018-07-27, 22:51   #46
GP2
 
GP2's Avatar
 
Sep 2003

258110 Posts
Default

Quote:
Originally Posted by sweety439 View Post
Yes, since all prime factors of Phi_n(2) are of the form kn+1 (maybe except the largest prime factor of n, like the case n = 6, 18, 20, 21, 54, 100, 110, 136, 147, 155, 156, 162, 253, 342, 486, 500, ...), and (2^p+1)/3 is Phi_{2p}(2), thus all prime factors of it are of the form 2kp+1.
Pardon my ignorance, but what is the name of this Phi function? The only phi I know is the totient function.
GP2 is offline   Reply With Quote
Old 2018-07-28, 00:39   #47
GP2
 
GP2's Avatar
 
Sep 2003

29·89 Posts
Default

Is trial-factoring more effective for Wagstaffs than for Mersennes? It doesn't seem to be true. Here are some numbers.

For Mersenne numbers, thanks to TJAOI's efforts and very extensive ECM testing we can be virtually certain that we know every factor of bit length smaller than 66, without exception, for all exponents less than a billion.

For Wagstaff numbers, there are various data sources, but the main one so far is ATH's trial factoring in 2013 and earlier, for which he posted a zip file. However, his data only includes first factors, since he stopped searching whenever he found a factor for an exponent.

If we look at the exponent range 10k to 10M, ATH trial-factored this range up to 56 bits (i.e. he found all exponents whose smallest factor has a bit length of less than 56).

So for both Mersenne and Wagstaff I counted how many exponents fit the criteria:

Code:
How many Mersenne numbers and how many Wagstaff numbers
with exponents between 10k and 1M
have a smallest factor of a given bit length?
(looking at bit lengths of less than 56)

b-l mer  wag
15   40   51
16   99  105
17  245  250
18  495  470
19  885  857
20 1586 1546
21 2775 2806
22 2084 2193
23 3060 2990
24 2493 2596
25 2530 2489
26 2285 2284
27 2170 2231
28 2025 2015
29 1930 1856
30 1810 1733
31 1578 1620
32 1465 1500
33 1452 1441
34 1409 1391
35 1289 1276
36 1176 1207
37 1111 1115
38 1118 1065
39 1013  945
40  889 1008
41  939  928
42  869  899
43  838  847
44  791  795
45  801  768
46  788  723
47  735  692
48  697  711
49  649  652
50  640  657
51  604  616
52  579  532
53  542  545
54  559  503
55  519  479
The numbers seem roughly the same. Trial-factoring is equally effective for both, and it doesn't seem like the trend would change for larger bit lengths.

Maybe trial factoring for Wagstaff seems more effective because we're still finding the ridiculously easy small factors, the kind that were found and cleared for Mersennes more than two decades ago.


What about P−1 testing? Well, trial factoring isn't really making a difference in terms of clearing away factors, so if P−1 was less effective for Wagstaff numbers than for Mersenne numbers, it would only be if the k−1 corresponding to factors 2kp + 1 was somehow less smooth. That doesn't seem likely.

However, there is a longstanding bug where mprime/Prime95 wrongly calculates the appropriate B1,B2 bounds for P−1 testing and sets them much too low. However if you manually set the bounds higher to match the same values you'd use for Mersenne, then P−1 testing should be equally effective for Wagstaff numbers.

PS,
The Venn diagram intersection of factors that are capable of being found by either trial-factoring or by P−1 is smaller than you'd think. Most factors found by TF have k−1 much too unsmooth to be found by P−1 testing, and most factors found by P−1 testing are much too big to be found by TF.

Last fiddled with by GP2 on 2018-07-28 at 00:42
GP2 is offline   Reply With Quote
Old 2018-07-28, 03:42   #48
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

73328 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Are all factors of Wagstaff numbers (2^p + 1)/3 of the form 2kp + 1? If so then yes, a similar heuristic would drop out.
If p is an odd prime, p > 3, q is prime, and q divides (2^p + 1)/3, then

q divides 2^(2*p) - 1, q does not divide 2^p - 1, and (using the hypothesis p > 3) q also does not divide 2^2 - 1.

Thus, 2*p is the least positive integer h for which q divides 2^h - 1 (the "hauptexponent"), whence 2*p divides q-1.

The conclusion q = 2*p + 1 fails for p = 3; (2^3 + 1)/3 = 3.
Dr Sardonicus is offline   Reply With Quote
Old 2018-07-28, 09:48   #49
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

32·331 Posts
Default

Quote:
Originally Posted by GP2 View Post
For Wagstaff numbers, there are various data sources, but the main one so far is ATH's trial factoring in 2013 and earlier, for which he posted a zip file. However, his data only includes first factors, since he stopped searching whenever he found a factor for an exponent.
Remember there is now "mfaktc-win-64.Wagstaff.exe" for trial factoring on GPUs. Looking at 16M-32M which I trial factored to 61 bits.
If I test 61-62 bits on my ~600 GHzdays / day card on 16M: 8.3 sec and 32M: 4.8 sec, so lets say 6.5 sec on average.
So all my effort could be duplicated pretty quickly on a single GPU today.
ATH is offline   Reply With Quote
Old 2018-07-28, 16:39   #50
GP2
 
GP2's Avatar
 
Sep 2003

258110 Posts
Default Bug in PRP cofactor code???

For the Wagstaff number with exponent 29123, mprime says the cofactor is composite, but actually it's a probable prime.

It fails with both type 1 and type 5 testing.

Other Wagstaff numbers I tested with mprime all worked: all of the known Wagstaff primes and probable primes, plus other Wagstaff numbers with factors known by FactorDB to have a PRP cofactor.

Code:
PRP=N/A,1,2,29123,1,"3,126660872079575401"
PRP=N/A,1,2,29123,1,99,0,3,1,"3,126660872079575401"
PRP=N/A,1,2,29123,1,99,0,3,5,"3,126660872079575401"
Code:
[Work thread Jul 28 16:08] Starting Gerbicz error-checking PRP test of 2^29123+1/3/126660872079575401 using all-complex FMA3 FFT length 1536
[Work thread Jul 28 16:08] 2^29123+1/3/126660872079575401 is not prime.  Type-5 RES64: 663E02E0E55571F7. Wg8: 993B7657,00000000

[Work thread Jul 28 16:26] Starting PRP test of 2^29123+1/3/126660872079575401 using all-complex FMA3 FFT length 1536
[Work thread Jul 28 16:26] 2^29123+1/3/126660872079575401 is not prime.  RES64: 2282024F325B71EB. Wg8: 993B7657,00000000

[Work thread Jul 28 16:26] Starting Gerbicz error-checking PRP test of 2^29123+1/3/126660872079575401 using all-complex FMA3 FFT length 1536
[Work thread Jul 28 16:26] 2^29123+1/3/126660872079575401 is not prime.  Type-5 RES64: 663E02E0E55571F7. Wg8: 993B7657,00000000
Code:
{"status":"C", "k":1, "b":2, "n":29123, "c":1, "known-factors":"3,126660872079575401", "worktype":"PRP-3", "res64":"663E02E0E55571F7", "residue-type":5, "fft-length":1536, "error-code":"00000000", "security-code":"993B7657", "program":{"name":"Prime95", "version":"29.4", "build":7, "port":8}, "timestamp":"2018-07-28 16:08:03", "errors":{"gerbicz":0}, ...

{"status":"C", "k":1, "b":2, "n":29123, "c":1, "known-factors":"3,126660872079575401", "worktype":"PRP-3", "res64":"2282024F325B71EB", "residue-type":1, "fft-length":1536, "error-code":"00000000", "security-code":"993B7657", "program":{"name":"Prime95", "version":"29.4", "build":7, "port":8}, "timestamp":"2018-07-28 16:26:44", ...

{"status":"C", "k":1, "b":2, "n":29123, "c":1, "known-factors":"3,126660872079575401", "worktype":"PRP-3", "res64":"663E02E0E55571F7", "residue-type":5, "fft-length":1536, "error-code":"00000000", "security-code":"993B7657", "program":{"name":"Prime95", "version":"29.4", "build":7, "port":8}, "timestamp":"2018-07-28 16:26:44", "errors":{"gerbicz":0}, ...
FactorDB says it's PRP.

Can anybody verify this??? Do other versions of mprime have the same problem, or other programs derived from the same code base?

Last fiddled with by GP2 on 2018-07-28 at 17:23
GP2 is offline   Reply With Quote
Old 2018-07-28, 16:45   #51
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×43×71 Posts
Default

No, it is a composite. You cannot use 2-PRP for numbers like this one.

They are all 2-PRPs, for any n value.
Batalov is offline   Reply With Quote
Old 2018-07-28, 17:35   #52
GP2
 
GP2's Avatar
 
Sep 2003

29·89 Posts
Default

Quote:
Originally Posted by Batalov View Post
No, it is a composite. You cannot use 2-PRP for numbers like this one.

They are all 2-PRPs, for any n value.
Hmmm, the FactorDB page at the link I gave now shows "C" instead of "PRP", and the main page for 2^29123+1 shows CF instead of FF.

So I guess their server software tests base 2 at first and displays PRP on a preliminary basis, and only then gets around to testing base 3... so if you click on it right after reporting a new factor, maybe you get the bogus FF notification.

Never mind the python snippet I posted, obviously it didn't test primality, it just verified the factor. Excitability and lack of sleep leads to a state of confusion.
GP2 is offline   Reply With Quote
Old 2018-07-29, 02:46   #53
axn
 
axn's Avatar
 
Jun 2003

22×5×239 Posts
Default

This is a known issue in FactorDB. If you run across a large PRP cofactor from a base-2 number, try to test using another base. Chances are, it'll be revealed as a composite.

edit:- Factor DB doesn't, on its own, test using other bases. Somebody will have to manually prod it to do so.

Last fiddled with by axn on 2018-07-29 at 02:48
axn is online now   Reply With Quote
Old 2018-07-29, 20:38   #54
GP2
 
GP2's Avatar
 
Sep 2003

A1516 Posts
Default

Quote:
Originally Posted by GP2 View Post
so if P−1 was less effective for Wagstaff numbers than for Mersenne numbers, it would only be if the k−1 corresponding to factors 2kp + 1 was somehow less smooth.
Quote:
Most factors found by TF have k−1 much too unsmooth to be found by P−1 testing
Of course, it's k itself that needs to be smooth, not k−1. I've been posting too much nonsense lately.
GP2 is offline   Reply With Quote
Old 2018-08-01, 19:07   #55
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

10101100012 Posts
Default

Quote:
Originally Posted by axn View Post
That's not how you do math. Maybe physics. But definitely not math.
I come from search where we beat all methods by some lightyears of course by means of dubious approximations.
edit: even the most optimistic predictions of any expert in the 1990s were totally beaten in the 21th century - progress of hardware had been factored in by some - progress of software (algorithmic progress) by no one. (end of edit)

The best heuristic there to predict the future is by having the most recent history event valued at a much higher value than all before. For example with killermoves.

If we look at Wagstaff then there is 1 prime just under 1M which i found. Then Tony Reix did do the bulk of work for the 4M one, and we know for sure there is nothing until 10M and the propper team probably searched about everything until 13M and found 2 there.

Those 2 are very close together so i count those as for the DISTANCE to next prime, as a single entity. Of course finding 2 is nicer than 1.

most recent history:
13 / 4 = factor 3.25 distance
4 / 1 = factor 4.0 distance
981k / 374321 = factor 2.6 distance

That's significant 3 datapoints. Calling that 'luck' or 'not significant statistical' is wrong. It simply shows it's not Mersenne nor 321.

Seen from a distance I call that factor 3 distance, and then i'm still rather optimistic. Now if we start to test massive number of exponents, millions of them, it's possible luck starts to play a smaller role to some extend.

Still if you search until 30M i highly doubt you have more than odds of 1SD (66%) to find 1 or more PRP's out there.

The recent datapoints suggest 3 * 13M+ = 40M would give high odds.
Yet no garantuee even till the door of the primeshop.

If you claim 2SD odds to find one at 40M, i only would say: "maybe". Yet don't bet at it you find even one.

In a given search space [n;2n] and n larger than a million, i claim that odds simply is lightyears worse than Mersenne.

I would guess it's on average somewhere between log 3 / log 2 => 1.6 until factor 3 to the next one for Wagstaff (above n=1 million), versus what is it something like 1.2 for mersenne?

Yet in our lifetime we do not yet know how far we will be able to test to find sufficient datapoints there.

Last fiddled with by diep on 2018-08-01 at 19:12
diep is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Testing Mersenne Primes with Elliptic Curves a nicol Math 3 2017-11-15 20:23
New Wagstaff PRP exponents ryanp Wagstaff PRP Search 26 2013-10-18 01:33
Hot tuna! -- a p75 and a p79 by Sam Wagstaff! Batalov GMP-ECM 9 2012-08-24 10:26
Statistical odds for prime in Wagstaff vs Mersenne diep Math 27 2010-01-13 20:18
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53

All times are UTC. The time now is 12:11.

Fri Nov 27 12:11:02 UTC 2020 up 78 days, 9:22, 4 users, load averages: 1.02, 1.21, 1.21

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.