mersenneforum.org Searching for Wagstaff PRP
 Register FAQ Search Today's Posts Mark Forums Read

2010-02-26, 05:00   #34
T.Rex

Feb 2004
France

2×461 Posts
GVR !!

Quote:
 Originally Posted by axn For base 3: Define f(x) = x^3-3*x Test for N=(3^p-1)/(3-1): s0=4, si+1=f(si), sp$\eq$s1 (mod N) Test for N=(3^p+1)/(3+1): s0=8, si+1=f(si), sp$\eq$s1 (mod N) For each base, we have to define a different f(x) and find proper seeds.
OK. That's the kind of f(x) I was using too for meta-cycles over the DiGraph under x^2-2 modulo a Mersenne prime: under x^3-3x modulo a Mersenne prime, we get another DiGraph that is linked with the first one. And so on.

Look at HC. Williams' book ("Edouard Lucas and Primality testing"), pages 77 and 78. The Lucas sequences naturally leads to Chebyshev polynomials : Sn and Cn, the same as Un and Vn for Lucas sequences. Z(n)=x*Z(n-1)-Z(n-2) .

$C0(x) = 2$
$C1(x) = x$
$C2(x) = x^2-2$
$C3(x) = x^3-3x$
$C4(x) = x^4-4x^2+2$
$C5(x) = x^5-5x^3+5x$
$C6(x) = x^6 - 6*x^4 + 9*x^2 - 2$
$C7(x) = x^7 - 7*x^5 + 14*x^3 - 7*x$

So, as an example, with b=5, and with the following gp/PARI program:
Code:
G(q)=W=(5^q+1)/6;print(q," ",isprime(W));S0=2^5;S=S0;for(i=1,q,S=Mod(S^5-5*S^3+5*S,W);
if(i==1,S1=S));if(S==S1,print("prime"))
forprime(j=3,100,G(j))
it is easy to see that W is prime for q=5,67,101,103 .
However, it missed: q=3,229,347 !! Probably due to a bad seed....

Though, for W=(3^q+1)/4, your seed seems perfect. W is prime for q=3,5,7,13,23,43,281,359,487,577

So, I've provided a general f(x) for each base of Generalized Wagstaff family.
So now, if we find a formula for the seed, we have a GVR PRP test for Generalized Wagstaff numbers !!

Yes, sure, there is a RICH area of research there...

Tony

2010-02-26, 06:30   #35
ixfd64
Bemusing Prompter

"Danny"
Dec 2002
California

1001011110002 Posts

Quote:
 Originally Posted by T.Rex Yes, sure, there is a RICH area of research there... Tony
I agree. Number theory is one of the least explored fields.

 2010-02-26, 14:44 #36 AntonVrba     Jun 2005 2·72 Posts My congratulations to Tony, may he soon top the Lifchitz pages. Tony your long patience has been rewarded! Is there a huge gap between 986191 4031399 or have all primes not been tested yet between the the known largest wagstaff prps?
2010-02-26, 17:01   #37
T.Rex

Feb 2004
France

2·461 Posts
Huge gap

Quote:
 Originally Posted by AntonVrba My congratulations to Tony, may he soon top the Lifchitz pages. Tony your long patience has been rewarded!
Thanks Anton. Yes, I am patient... maybe too ?!
Quote:
 Is there a huge gap between 986191 4031399 or have all primes not been tested yet between the the known largest wagstaff prps?
I don't know exactly (Vincent knows). I already have still about 2500 3M numbers to be re-verified due to LLR 3.7.2 bug (gwnum probably). So the probability to find a new PRP below mine is very low, I think... So yes, it seems to be a huge gap between the one Vincent discovered 18 months ago and mine. However, we should wait for a verification. Who wants to contribute ?
Tony

2010-02-27, 02:06   #38
axn

Jun 2003

2×23×113 Posts

Quote:
 Originally Posted by T.Rex Z(n)=x*Z(n-1)-Z(n-2) . $C0(x) = 2$ $C1(x) = x$ $C2(x) = x^2-2$ $C3(x) = x^3-3x$ $C4(x) = x^4-4x^2+2$ $C5(x) = x^5-5x^3+5x$ $C6(x) = x^6 - 6*x^4 + 9*x^2 - 2$ $C7(x) = x^7 - 7*x^5 + 14*x^3 - 7*x$
I rediscovered these in my investigations
Quote:
 Originally Posted by T.Rex So, as an example, with b=5, and with the following gp/PARI program: Code: G(q)=W=(5^q+1)/6;print(q," ",isprime(W));S0=2^5;S=S0;for(i=1,q,S=Mod(S^5-5*S^3+5*S,W); if(i==1,S1=S));if(S==S1,print("prime")) forprime(j=3,100,G(j)) it is easy to see that W is prime for q=5,67,101,103 . However, it missed: q=3,229,347 !! Probably due to a bad seed.... So now, if we find a formula for the seed, we have a GVR PRP test for Generalized Wagstaff numbers !!
I am not sure I have the necessary math to workout the rules for seeds. For base 5, empirical testing suggests seeds 3 & 7 are suitable.

I am close to working out how these tests are working (looks like glorified fermat test)

2010-02-27, 03:00   #39
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts

Quote:
 Originally Posted by T.Rex However, we should wait for a verification. Who wants to contribute ? Tony
Tony, have you thought of asking Mike (XYZZY) for a subforum devoted to this search? Your project seems to be running on roughly the same amount of resources as Five or Bust, maybe a little more, but you have the disadvantage of over 8 times as many candidates in a given range as Five or Bust is now testing (assuming that you eliminate 60% or more of your candidates by trial factoring). But our project may not be lucky for awhile, so you should have a good chance of taking the prp record from us with a little more help! You could have a reservation thread, status reports, and even start to do P-1 testing when the exponents get a little bigger. Talk it over with Paul and Vincent, but I think this could be a nice, not too complicated, small-scale distributed computing project, with a good potential for attracting participants.

Phil

2010-02-27, 08:18   #40
T.Rex

Feb 2004
France

2·461 Posts

Quote:
 Originally Posted by axn I rediscovered these in my investigations I am not sure I have the necessary math to workout the rules for seeds. For base 5, empirical testing suggests seeds 3 & 7 are suitable. I am close to working out how these tests are working (looks like glorified fermat test)
I've tried with using the Cn formula as a seed but without the last term (2^5-5*2^3). It found 229, but not 347. I guess one must use some generic formula. Maybe the Sn Chebytshev formula ? S0=0, S1=1, S(n)=x*S(n-1)-S(n-2) .

However, I guess that it is also possible to build a PRP test for base b generalized Wagstaff numbers with x^2-2 ....

T.

2010-02-27, 08:31   #41
T.Rex

Feb 2004
France

2×461 Posts
Great idea !

Quote:
 Originally Posted by philmoore Tony, have you thought of asking Mike (XYZZY) for a subforum devoted to this search? Your project seems to be running on roughly the same amount of resources as Five or Bust, maybe a little more, but you have the disadvantage of over 8 times as many candidates in a given range as Five or Bust is now testing (assuming that you eliminate 60% or more of your candidates by trial factoring). But our project may not be lucky for awhile, so you should have a good chance of taking the prp record from us with a little more help! You could have a reservation thread, status reports, and even start to do P-1 testing when the exponents get a little bigger. Talk it over with Paul and Vincent, but I think this could be a nice, not too complicated, small-scale distributed computing project, with a good potential for attracting participants.
Hi Phil,

Nice proposal ! Good idea !

I'll talk with Vincent (Diepeeven), who initiated this project and is managing it. I think he will be very happy to have his idea showing to be a very smart one and to attract more people. It depends if he has time, too. He's involved in his Diep chess program and he, from time to time, is very busy with it.

On my side, I am interested by many other subjects (my job..., philosophy, my Blog, friends, poetry, readings, athéism, my children, women and sex ! :) ), so I do not plan to spend on Number Theory and PRP search as much time as I spent in the past. However, I plan to continue on this as long as I can. So much fun !

So, I would be very happy that a bigger Wagstaff PRP is found ! even by someone else. That would attract more people on looking at these damned Conjectures that Vrba, Gerbicz and my-self built 2 years ago now.

We need a proof ! And, with a proof for Vrba-Reix conjecture, I would have found a 1.2 M digits prime !!

Tony

2010-02-27, 23:43   #42
diep

Sep 2006
The Netherlands

11·71 Posts

Quote:
 Originally Posted by philmoore Tony, have you thought of asking Mike (XYZZY) for a subforum devoted to this search? Your project seems to be running on roughly the same amount of resources as Five or Bust, maybe a little more, but you have the disadvantage of over 8 times as many candidates in a given range as Five or Bust is now testing (assuming that you eliminate 60% or more of your candidates by trial factoring). But our project may not be lucky for awhile, so you should have a good chance of taking the prp record from us with a little more help! You could have a reservation thread, status reports, and even start to do P-1 testing when the exponents get a little bigger. Talk it over with Paul and Vincent, but I think this could be a nice, not too complicated, small-scale distributed computing project, with a good potential for attracting participants. Phil
If we hit bigger exponent ranges that luck factor will become less and we should more and more find Wagstaffs with the same regular interval like factories produce cars.

It is true we profit from great work that has been done for the GIMPS search so far, as everything that applies to Mersenne also applies to Wagstaff.

I don't see how other formula's can rival with it in the long run in terms of PRP finding.

Of course i didn't study math, but we just need to test, just like Mersenne, exponent numbers that are prime themselves. 60% gets trial factored.

So after we have determined that the most useless form of wasting CPU power is the search for the holy infinite sized grail as we try here, then searching for Wagstaff from all industry grade primes is the most efficient one i'd argue.

Vincent

2010-02-27, 23:59   #43
diep

Sep 2006
The Netherlands

11000011012 Posts

Quote:
 Originally Posted by T.Rex Thanks Anton. Yes, I am patient... maybe too ?! I don't know exactly (Vincent knows). I already have still about 2500 3M numbers to be re-verified due to LLR 3.7.2 bug (gwnum probably). So the probability to find a new PRP below mine is very low, I think... So yes, it seems to be a huge gap between the one Vincent discovered 18 months ago and mine. However, we should wait for a verification. Who wants to contribute ? Tony
There is still some cores of Tony to finish there, didn't get his results there yet at all so far.

However odds are relative small. Yet there seems bug in core2 which avoided it from functioning very well and there is always a possibility for other problems or misses. So we'll double check up to the largest Wagstaff found to date; i do not know our odds of finding one there.

the bigger ranges more chances maybe. But maybe one is real closeby who knows.

You never know.

This lottery is better than joining other lotteries i'd argue.

Vincent

2010-03-03, 00:48   #44
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by T.Rex \$ ./pfgw -t -q"(2^4031399+1)/3" PFGW Version 20091218.x86_Dev (Beta 'caveat utilitor') [GWNUM 25.13] Primality testing (2^4031399+1)/3 [N-1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 2
I don't know the details of PFGW but if under "N-1" test it means Fermat primality test or even Miller–Rabin primality test, then running this test base 2 does not make sense for Wagstaff numbers.

Indeed, if $q=\frac{2^p+1}{3}$ for odd prime $p$, then $q-1=\frac{2^p-2}{3}=2\cdot\frac{2^{p-1}-1}{3}$, while the multiplicative order of 2 modulo $q$ is $2p$. Clearly, $q-1\equiv 0 \pmod{2p}$, implying that $2^{q-1} \equiv 1 \pmod{q}$. Furthermore, $(q-1)/2 \equiv p \pmod{2p}$, implying that $2^{(q-1)/2} \equiv -1 \pmod{q}$.

Therefore, $q$ always passes Miller–Rabin primality test base 2 (even if $q$ is not prime).

 Similar Threads Thread Thread Starter Forum Replies Last Post ryanp Wagstaff PRP Search 26 2013-10-18 01:33 Batalov GMP-ECM 9 2012-08-24 10:26 davieddy Miscellaneous Math 209 2011-01-23 23:50 diep GMP-ECM 10 2010-07-26 21:33 T.Rex Math 0 2007-09-04 07:10

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

Mon Dec 6 11:27:07 UTC 2021 up 136 days, 5:56, 0 users, load averages: 1.14, 1.25, 2.10