Searching for Wagstaff PRP - Page 4

T.Rex · 2010-02-26, 05:00

Quote:

Originally Posted by axn

For base 3:
Define f(x) = x^3-3*x
Test for N=(3^p-1)/(3-1): s₀=4, s_i+1=f(s_i), s_p $\eq$ s₁ (mod N)
Test for N=(3^p+1)/(3+1): s₀=8, s_i+1=f(s_i), s_p $\eq$ s₁ (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

ixfd64 · 2010-02-26, 06:30

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.

AntonVrba · 2010-02-26, 14:44

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?

T.Rex · 2010-02-26, 17:01

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

axn · 2010-02-27, 02:06

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)

philmoore · 2010-02-27, 03:00

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

T.Rex · 2010-02-27, 08:18

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.

T.Rex · 2010-02-27, 08:31

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

diep · 2010-02-27, 23:43

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

diep · 2010-02-27, 23:59

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

maxal · 2010-03-03, 00:48

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
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

2010-02-26, 14:44	#36
AntonVrba Jun 2005 2·7² 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?