mersenneforum.org  

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

Reply
 
Thread Tools
Old 2010-02-26, 05:00   #34
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default GVR !!

Quote:
Originally Posted by axn View Post
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\eqs1 (mod N)
Test for N=(3^p+1)/(3+1): s0=8, si+1=f(si), sp\eqs1 (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
T.Rex is offline   Reply With Quote
Old 2010-02-26, 06:30   #35
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

22×3×191 Posts
Default

Quote:
Originally Posted by T.Rex View Post
Yes, sure, there is a RICH area of research there...

Tony
I agree. Number theory is one of the least explored fields.
ixfd64 is offline   Reply With Quote
Old 2010-02-26, 14:44   #36
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

9810 Posts
Default

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?
AntonVrba is offline   Reply With Quote
Old 2010-02-26, 17:01   #37
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default Huge gap

Quote:
Originally Posted by AntonVrba View Post
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
T.Rex is offline   Reply With Quote
Old 2010-02-27, 02:06   #38
axn
 
axn's Avatar
 
Jun 2003

467110 Posts
Red face

Quote:
Originally Posted by T.Rex View Post
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 View Post
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)
axn is offline   Reply With Quote
Old 2010-02-27, 03:00   #39
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

Quote:
Originally Posted by T.Rex View Post
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
philmoore is offline   Reply With Quote
Old 2010-02-27, 08:18   #40
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Quote:
Originally Posted by axn View Post
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.
T.Rex is offline   Reply With Quote
Old 2010-02-27, 08:31   #41
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default Great idea !

Quote:
Originally Posted by philmoore View Post
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
T.Rex is offline   Reply With Quote
Old 2010-02-27, 23:43   #42
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

677 Posts
Default Industry grade primes forum

Quote:
Originally Posted by philmoore View Post
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
diep is offline   Reply With Quote
Old 2010-02-27, 23:59   #43
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

677 Posts
Default

Quote:
Originally Posted by T.Rex View Post
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
diep is offline   Reply With Quote
Old 2010-03-03, 00:48   #44
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by T.Rex View Post
$ ./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).
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
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
Wagstaff Conjecture davieddy Miscellaneous Math 209 2011-01-23 23:50
Best settings to factor Wagstaff p = (2^n +1) / 1 diep GMP-ECM 10 2010-07-26 21:33
30th Wagstaff prime T.Rex Math 0 2007-09-04 07:10

All times are UTC. The time now is 13:58.

Thu Aug 13 13:58:37 UTC 2020 up 10:34, 1 user, load averages: 1.18, 1.36, 1.53

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.