Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness

[axn]

Originally Posted by DukeBG

Factors of the 33000-34000 range were added to FactorDB by someone.

I am doing t30 on 33000-35000 range. Currently around 34300...

[GP2]

Originally Posted by axn

Perhaps we could switch places. You can take 3k onwards to t40 (using P95 + GMP-ECM - just P95 alone would not be most efficient). I can work my way downwards from 10k to t35. What do you think?

OK, let's do that.

I already did the following exponents before stopping:

UID: GP2/c5.large, 2^9887+1 completed 1580 ECM curves, B1=1000000, B2=100000000, Wg8: 0657232B
UID: GP2/c5.large, 2^9907+1 completed 1580 ECM curves, B1=1000000, B2=100000000, Wg8: 0663232F
UID: GP2/c5.large, 2^9923+1 completed 1580 ECM curves, B1=1000000, B2=100000000, Wg8: 0642232E
UID: GP2/c5.large, 2^9929+1 completed 1580 ECM curves, B1=1000000, B2=100000000, Wg8: 06482323
UID: GP2/c5.large, 2^9931+1 completed 1580 ECM curves, B1=1000000, B2=100000000, Wg8: 064A2325
UID: GP2/c5.large, 2^9949+1 completed 1580 ECM curves, B1=1000000, B2=100000000, Wg8: 06642326
UID: GP2/c5.large, 2^9967+1 completed 1580 ECM curves, B1=1000000, B2=100000000, Wg8: 06402327
UID: GP2/c5.large, 2^9973+1 completed 1580 ECM curves, B1=1000000, B2=100000000, Wg8: 064E232D

I didn't get around to doing 9901, and I skipped 9941 because it's a Mersenne prime exponent and the Mersenneplustwo project has already ECM'd it to t=50+

[GP2]

Hmmm, maybe it's not surprising that Mersenne numbers and Wagstaff numbers with the same exponent may be correlated in terms of being fully-factored.

After all if M_p = 2^p − 1 and W_p = (2^p + 1) /3, then:

3 * M_p * W_p = M_2p

and, as the Lifchitz duo pointed out:

2 * M_p * W_p = W_2p+1 − 1

I imagine the factors of any random composite number N are distributed unpredictably between 2 and sqrt(N), and there is always at least a small probability that it will end up having only small prime factors plus a huge cofactor that splits into exactly two prime factors of roughly equal size. So if M₁₄₈₃₄ and M₁₇₆₉₈ satisfy that condition, as they do, then both M₇₄₁₇, W₇₄₁₇ and both M₈₈₄₉, W₈₈₄₉ will be fully factored if we are lucky and the two huge prime cofactors get split up and go separately into each of the two components.

PS,

It might be worthwhile to go trawling through FactorDB, to see if anyone has reported factors for Mersenne numbers whose exponents are 2 times a prime, to see if there are any undiscovered Wagstaff factors sitting there in plain sight...

[GP2]

The Lifchitz duo, in their paper, point out that by the equation in the previous message, if either M_p or W_p is prime, and p is a Sophie Germain prime (i.e., 2p+1 is also prime), then if W_2p+1 happens to be a probable prime also, then it should be straightforward to certify that it is prime by the N−1 method.

Actually, I think that M_p or W_p don't have to be prime, one of them just needs to be fully-factored.

Of course the catch is, it is really extremely unlikely that W_2p+1 will just happen to be prime, for anything but very small p.

The Lifchitzes, writing in the year 2000, discuss the exponents 5, 7, 11, 23, 47, 179, 383, 7079, 19379, 21383, 43403, 166679 and 1718867, none of which are exponents of Wagstaff primes. From Mersenne primes and Wagstaff primes discovered since then, we can add: W_8,062,799 (has a factor), W_26,694,623 (no factor to 75 bits, but PRP tested as composite), and W_86,225,219 (no factor to 75 bits, I'm PRP testing it now, but what are the odds?). And the currently known fully-factored Mersenne numbers and fully-factored Wagstaff numbers don't yield any Sophie Germain p for which the safe prime 2p+1 is larger than 1M, and everything is already tested composite.

We could also work backward: W₈₃₃₃₉ is a Wagstaff prime, which was very laboriously certified prime by ECPP. But 83339 is a safe prime corresponding to the Sophie Germain prime 41669, so if by some extremely unlikely sheer luck we managed to fully factor either M₄₁₆₆₉ or W₄₁₆₆₉, then we would have an alternative easy N−1 proof. The safe-prime exponents of known Wagstaff primes, along with their Sophie-Germain prime counterparts are:

3 7
5 11
11 23
83 167
173 347
2903 5807
5639 11279
41669 83339

and unfortunately nothing bigger.

This approach is also really extremely unlikely to be fruitful. There aren't any undiscovered Wagstaff primes smaller than 5M, and probably not smaller than 10M, and even if we found one, its exponent would need to be a safe prime, and then we would have to hope that the Mersenne number or Wagstaff number with the Sophie-Germain-prime counterpart exponent of size 2M or 3M or higher would somehow miraculously get fully factored at some point in the future.

[GP2]

Originally Posted by GP2

...if we are lucky and the two huge prime cofactors get split up and go separately into each of the two components.

But of course they have to go separately into each of the two components, because M_p and W_p are necessarily of nearly comparable size...

[DukeBG]

Originally Posted by GP2

It might be worthwhile to go trawling through FactorDB, to see if anyone has reported factors for Mersenne numbers whose exponents are 2 times a prime, to see if there are any undiscovered Wagstaff factors sitting there in plain sight...

I did that before, there's none.

[science_man_88]

Originally Posted by DukeBG

I did that before, there's none.

2^(2p)-1== (2^p+1)(2^p-1) so they'd show up as mersennes with prime exponents and factors of 2^p+1

[GP2]

Originally Posted by GP2

The Lifchitzes, writing in the year 2000, discuss the exponents 5, 7, 11, 23, 47, 179, 383, 7079, 19379, 21383, 43403, 166679 and 1718867, none of which are exponents of Wagstaff primes.

Except the first four obviously are...

[GP2]

We can look for the same phenomenon in other bases.

The generalized repunits are:

R^b_p = (b^p − 1) / (b − 1)

which also implies that for negative b and odd p:

R^−b_p = (b^p + 1) / (b + 1)

Note for the base b=2 we have the special cases of Mersenne and Wagstaff numbers.

For bases other than b=2, ECM factoring beyond the Cunningham exponent range has been done only in limited cases and to at most t=25, which limits the number of known fully-factored exponents.

Still, if we ignore anything below 1500, we find the following:

In the range between 2000 and 3000, there are 127 prime numbers.
For R³ we have nine known fully-factored exponents, and for R⁻³ we have four known fully-factored exponents, and 2131 is a member of both subsets.

In the range between 3000 and 4000, there are 120 prime numbers.
For R⁵ we have one known fully-factored exponent, and for R⁻⁵ we have one known fully-factored exponent, and it is one and the same: 3203.

No coincidences turn up for b=6 and b=7. Well, actually for b=6 we have p=1187, 1409, but these are below the threshold of 1500 that we set. Although perhaps we should still count them, because the larger b is, the less thoroughly the Cunningham project has fully factored the smallish exponents.

For b higher than 7 the FactorDB data is too patchy at the moment.

[axn]

33000-35000 range

2^33013+1 = 244323344600583960643
2^33029+1 = 45013308419
2^33073+1 = 17222305654955729
2^33091+1 = 124387312463539
2^33091+1 = 1581153397174269019
2^33091+1 = 436504452972184865713
2^33119+1 = 538702194827
2^33149+1 = 13237626462989728832803
2^33179+1 = 7354499400278955028073223211115971
2^33191+1 = 1335895311662383504024122457
2^33203+1 = 16097743599829179275664540179
2^33203+1 = 718854557547996076657401257
2^33211+1 = 170860276964275609
2^33211+1 = 7544093761366633
2^33211+1 = 7861460408778833
2^33223+1 = 126848177122404791539
2^33223+1 = 132916318483299713
2^33287+1 = 152116186738774997580371281
2^33287+1 = 2501062389726383774449
2^33289+1 = 12177540892142364314419
2^33289+1 = 183263610982401590323
2^33301+1 = 3549171768274817491922009
2^33301+1 = 952657805611851281
2^33317+1 = 115645840757851
2^33329+1 = 278243447158508283011569
2^33331+1 = 480185938164587
2^33331+1 = 620715582909909563057
2^33331+1 = 687762221807537
2^33347+1 = 1313921489529582668553131
2^33347+1 = 2699773920329
2^33347+1 = 732531534190517329441
2^33349+1 = 149656459113403767580619
2^33353+1 = 30385004648627
2^33409+1 = 4366631937977
2^33413+1 = 532725306062509138128599028257
2^33461+1 = 10014073565014892632177
2^33461+1 = 11981740945115171
2^33469+1 = 46434139988636941006153
2^33479+1 = 1494930625639988954497
2^33479+1 = 7225229942369
2^33487+1 = 135909003481851401
2^33493+1 = 13033009992785363083
2^33493+1 = 815884670636813130108656273
2^33503+1 = 1199487539177
2^33503+1 = 6521458587923
2^33529+1 = 34713085274259031420343723
2^33533+1 = 299422108770288128041
2^33533+1 = 408893428013472489073756907
2^33533+1 = 55789230203611589136220651
2^33533+1 = 7026547473977
2^33547+1 = 3682958195311464985691
2^33569+1 = 268438297101930031971113
2^33569+1 = 33598703521929131
2^33599+1 = 187056272196467429888449
2^33599+1 = 416719592976080321
2^33601+1 = 10910027959271456657
2^33601+1 = 15015193010076399729289979
2^33617+1 = 40637329384323590916196033
2^33629+1 = 1409418420107437042823545969
2^33721+1 = 1295616014293988215211
2^33767+1 = 8323998309620918477707841
2^33773+1 = 161986565290660601
2^33791+1 = 160721309767457
2^33791+1 = 32496687310067
2^33797+1 = 1938529204723
2^33797+1 = 2181904765676237701033868562427
2^33811+1 = 884809052200294129553
2^33827+1 = 209133637849008818963
2^33829+1 = 10035523992138395983481
2^33829+1 = 45606465061170283
2^33863+1 = 432857771928520441
2^33871+1 = 31686284597364513499
2^33889+1 = 115840810661192689459
2^33923+1 = 17260283622599554393
2^33923+1 = 375667847683
2^33937+1 = 5659022510467
2^33961+1 = 2720840357008876913
2^33997+1 = 578864124358664515699
2^34019+1 = 2945883469561
2^34019+1 = 331516200084153691395331667
2^34019+1 = 43933412621320527423429871969
2^34031+1 = 12844836650455262153
2^34033+1 = 108065182512001907
2^34039+1 = 1136707956349891472467
2^34127+1 = 931760715845870405095416329
2^34129+1 = 47871798425320095068719633
2^34141+1 = 2532499149913186204819
2^34147+1 = 41982431853138060908971
2^34171+1 = 155553263856443
2^34213+1 = 62409807693419
2^34231+1 = 2534471762672809681
2^34231+1 = 3305136413977
2^34273+1 = 22727428553793770588053923659
2^34273+1 = 8451030376499
2^34283+1 = 357857836034034043330540923659
2^34301+1 = 6533573278339673804301803
2^34313+1 = 585292729634651
2^34337+1 = 20141353814137937177
2^34337+1 = 27396950810066451227
2^34351+1 = 257790997496422384340443024307209
2^34351+1 = 3934104151916747
2^34351+1 = 44685813781616550941898002539
2^34367+1 = 1012393079369295206873
2^34381+1 = 293668051321891
2^34403+1 = 4936507954231490257
2^34421+1 = 8790590859694832953
2^34457+1 = 48003597884253796365227
2^34469+1 = 183864725557362813883
2^34483+1 = 6216908137845443
2^34511+1 = 17878376212788825883
2^34519+1 = 105543750039055740998969
2^34519+1 = 1408511576725511386626622907
2^34549+1 = 60544939716289365976914816442378681
2^34603+1 = 27322193561083963
2^34607+1 = 1053855121693403
2^34631+1 = 428731898803616108946230238859
2^34651+1 = 88964571347
2^34667+1 = 173923437659
2^34673+1 = 174284181073707501049250873
2^34679+1 = 1000251912481739780354291
2^34679+1 = 34735850317579337
2^34703+1 = 1608699418926762499
2^34721+1 = 42355547062053019
2^34729+1 = 7651793557960376720347
2^34739+1 = 18083223457113209
2^34739+1 = 974826623738688955873
2^34757+1 = 159322816744035432052633
2^34759+1 = 2409451067999054935915970896873
2^34759+1 = 804946991825430611
2^34763+1 = 15248664848634989793427326491
2^34763+1 = 769982993756138555925509113
2^34763+1 = 84324862363998441139
2^34781+1 = 131145081991829433611899
2^34781+1 = 1392522504123119576347193201
2^34807+1 = 3308781771917867467
2^34819+1 = 18321677781314441466419
2^34819+1 = 297408428301239363
2^34847+1 = 3388958014193603857
2^34849+1 = 1175071822091369
2^34849+1 = 357955745877569111177203
2^34849+1 = 6074351530191475465991292233
2^34877+1 = 3004977184910519678088994003
2^34877+1 = 61207936396321988201
2^34877+1 = 858534082772688708473
2^34877+1 = 97229778311829176968771
2^34919+1 = 3948913813971410593

[pinhodecarlos]

25500-26000

2^25561+1 has a factor: 136909595564491867571 (ECM curve 23, B1=250000, B2=25000000)
2^25561+1 has a factor: 136909595564491867571 (ECM curve 3, B1=250000, B2=25000000)
2^25561+1 has a factor: 136909595564491867571 (ECM curve 74, B1=250000, B2=25000000)
2^25583+1 has a factor: 2108375531451544092169 (ECM curve 4, B1=250000, B2=25000000)
2^25589+1 has a factor: 4533217425232723910897 (ECM curve 55, B1=250000, B2=25000000)
2^25609+1 has a factor: 4267185478594256099199502969 (ECM curve 143, B1=250000, B2=25000000)
2^25621+1 has a factor: 368252059833694969 (ECM curve 4, B1=250000, B2=25000000)
2^25639+1 has a factor: 2703117300877515230230787 (ECM curve 85, B1=250000, B2=25000000)
2^25657+1 has a factor: 42188428063252774609 (ECM curve 9, B1=250000, B2=25000000)
2^25673+1 has a factor: 2460099335748156782199019 (ECM curve 49, B1=250000, B2=25000000)
2^25733+1 has a factor: 239001603528530737936039699 (ECM curve 274, B1=250000, B2=25000000)
2^25747+1 has a factor: 869465213607265690470233 (ECM curve 38, B1=250000, B2=25000000)
2^25801+1 has a factor: 683773135900148971 (ECM curve 3, B1=250000, B2=25000000)
2^25841+1 has a factor: 410369752966734745420949220543683 (ECM curve 180, B1=250000, B2=25000000)
2^25847+1 has a factor: 12680442819865294557718499 (ECM curve 255, B1=250000, B2=25000000)
2^25847+1 has a factor: 46751657557521312289475607363658939 (ECM curve 299, B1=250000, B2=25000000)
2^25903+1 has a factor: 15016808139977443 (ECM curve 5, B1=250000, B2=25000000)
2^25919+1 has a factor: 5922210067999919923 (ECM curve 2, B1=250000, B2=25000000)
2^25931+1 has a factor: 1891570224656668841936972723 (ECM curve 109, B1=250000, B2=25000000)
2^25951+1 has a factor: 23260238273143196107 (ECM curve 134, B1=250000, B2=25000000)
2^25951+1 has a factor: 23260238273143196107 (ECM curve 5, B1=250000, B2=25000000)
2^25951+1 has a factor: 317907539894705471225293187 (ECM curve 108, B1=250000, B2=25000000)

26000-26500 still testing..