20180727, 19:24  #45 
Nov 2016
2^{3}·11·23 Posts 
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 20180727 at 19:25 
20180727, 22:51  #46  
Sep 2003
2×1,289 Posts 
Quote:


20180728, 00:39  #47 
Sep 2003
2×1,289 Posts 
Is trialfactoring 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 trialfactored 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) bl 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 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 trialfactoring 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 20180728 at 00:42 
20180728, 03:42  #48  
Feb 2017
Nowhere
3266_{10} Posts 
Quote:
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 q1. The conclusion q = 2*p + 1 fails for p = 3; (2^3 + 1)/3 = 3. 

20180728, 09:48  #49  
Einyen
Dec 2003
Denmark
5442_{8} Posts 
Quote:
If I test 6162 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. 

20180728, 16:39  #50 
Sep 2003
2·1,289 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 errorchecking PRP test of 2^29123+1/3/126660872079575401 using allcomplex FMA3 FFT length 1536 [Work thread Jul 28 16:08] 2^29123+1/3/126660872079575401 is not prime. Type5 RES64: 663E02E0E55571F7. Wg8: 993B7657,00000000 [Work thread Jul 28 16:26] Starting PRP test of 2^29123+1/3/126660872079575401 using allcomplex 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 errorchecking PRP test of 2^29123+1/3/126660872079575401 using allcomplex FMA3 FFT length 1536 [Work thread Jul 28 16:26] 2^29123+1/3/126660872079575401 is not prime. Type5 RES64: 663E02E0E55571F7. Wg8: 993B7657,00000000 Code:
{"status":"C", "k":1, "b":2, "n":29123, "c":1, "knownfactors":"3,126660872079575401", "worktype":"PRP3", "res64":"663E02E0E55571F7", "residuetype":5, "fftlength":1536, "errorcode":"00000000", "securitycode":"993B7657", "program":{"name":"Prime95", "version":"29.4", "build":7, "port":8}, "timestamp":"20180728 16:08:03", "errors":{"gerbicz":0}, ... {"status":"C", "k":1, "b":2, "n":29123, "c":1, "knownfactors":"3,126660872079575401", "worktype":"PRP3", "res64":"2282024F325B71EB", "residuetype":1, "fftlength":1536, "errorcode":"00000000", "securitycode":"993B7657", "program":{"name":"Prime95", "version":"29.4", "build":7, "port":8}, "timestamp":"20180728 16:26:44", ... {"status":"C", "k":1, "b":2, "n":29123, "c":1, "knownfactors":"3,126660872079575401", "worktype":"PRP3", "res64":"663E02E0E55571F7", "residuetype":5, "fftlength":1536, "errorcode":"00000000", "securitycode":"993B7657", "program":{"name":"Prime95", "version":"29.4", "build":7, "port":8}, "timestamp":"20180728 16:26:44", "errors":{"gerbicz":0}, ... 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 20180728 at 17:23 
20180728, 16:45  #51 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
5×1,811 Posts 
No, it is a composite. You cannot use 2PRP for numbers like this one.
They are all 2PRPs, for any n value. 
20180728, 17:35  #52  
Sep 2003
2·1,289 Posts 
Quote:
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. 

20180729, 02:46  #53 
Jun 2003
1001000010111_{2} Posts 
This is a known issue in FactorDB. If you run across a large PRP cofactor from a base2 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 20180729 at 02:48 
20180729, 20:38  #54  
Sep 2003
2×1,289 Posts 
Quote:
Quote:


20180801, 19:07  #55 
Sep 2006
The Netherlands
2×337 Posts 
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 20180801 at 19:12 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Testing Mersenne Primes with Elliptic Curves  a nicol  Math  3  20171115 20:23 
New Wagstaff PRP exponents  ryanp  Wagstaff PRP Search  26  20131018 01:33 
Hot tuna!  a p75 and a p79 by Sam Wagstaff!  Batalov  GMPECM  9  20120824 10:26 
Statistical odds for prime in Wagstaff vs Mersenne  diep  Math  27  20100113 20:18 
Speed of P1 testing vs. Trial Factoring testing  eepiccolo  Math  6  20060328 20:53 