mersenneforum.org Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness
 Register FAQ Search Today's Posts Mark Forums Read

2018-07-27, 19:24   #45
sweety439

Nov 2016

22×541 Posts

Quote:
 Originally Posted by CRGreathouse 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

2018-07-27, 22:51   #46
GP2

Sep 2003

257910 Posts

Quote:
 Originally Posted by sweety439 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.

 2018-07-28, 00:39 #47 GP2     Sep 2003 2,579 Posts 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
2018-07-28, 03:42   #48
Dr Sardonicus

Feb 2017
Nowhere

2·3·557 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2018-07-28, 09:48   #49
ATH
Einyen

Dec 2003
Denmark

22×3×241 Posts

Quote:
 Originally Posted by GP2 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.

 2018-07-28, 16:39 #50 GP2     Sep 2003 1010000100112 Posts 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
 2018-07-28, 16:45 #51 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·7·11·59 Posts No, it is a composite. You cannot use 2-PRP for numbers like this one. They are all 2-PRPs, for any n value.
2018-07-28, 17:35   #52
GP2

Sep 2003

257910 Posts

Quote:
 Originally Posted by Batalov 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.

 2018-07-29, 02:46 #53 axn     Jun 2003 33·173 Posts 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
2018-07-29, 20:38   #54
GP2

Sep 2003

2,579 Posts

Quote:
 Originally Posted by GP2 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.

2018-08-01, 19:07   #55
diep

Sep 2006
The Netherlands

677 Posts

Quote:
 Originally Posted by axn 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

 Similar Threads Thread Thread Starter Forum Replies Last Post a nicol Math 3 2017-11-15 20:23 ryanp Wagstaff PRP Search 26 2013-10-18 01:33 Batalov GMP-ECM 9 2012-08-24 10:26 diep Math 27 2010-01-13 20:18 eepiccolo Math 6 2006-03-28 20:53

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

Thu Aug 13 15:18:11 UTC 2020 up 11:53, 1 user, load averages: 1.55, 1.55, 1.44