Searching for Wagstaff PRP - Page 5

diep · 2010-03-03, 01:06

Quote:

Originally Posted by maxal

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

Correct base2 doesn't work for Wagstaff for same reason it doesn't work for Mersenne.

Note if it would work, there is a real fast manner to find prime numbers for Mersenne.

Vincent

mdettweiler · 2010-03-03, 01:16

Quote:

Originally Posted by maxal

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.

What PFGW refers to as the "N-1" test is a Pocklington test. It can also do the N+1 Morrison test as well as a combined test. Here's the details on those from PFGW's included pfgwdoc.txt:

Code:

A.3. More details/methods used
 Pfgw can work with numbers from 2 up to almost 2^79700000 (about 24000000
 digits). It can find probable primes with Fermat's method, with bases
 from 2 to 256.
 To be more precise: The largest FFT is 4 million elements long, with 19
 bits per element. GFN's can be tested upto 24M digits, and generic numbers
 upto 12M digits.
 To prove a number prime, other methods need to be used.
 Only a small percentage of all numbers can be easily proven prime.
 Name a number N, then you must be able to factor N-1 or N+1 to 33.33% to
 find a proof using PFGW.
 If N-1 is factored deep enough, then Pocklington's test can be applied.
 If N+1 is factored deep enough, then Morrison's test can be applied.
 If N^2-1 is factored deep enough, a combined method can be used.
 
A.3.1 Fermat's method
 Fermat's method is NOT a proof, but more like a quick indicator that a
 number might be prime.
A.3.2 Pocklington's test
 This test can be used whenever N-1 can be factored to 33.33% of the size
 of N. (Actually, the factored part must be greater than the cube root of
 N/1000000). This test is conclusive.
A.3.3 Morrison's test
 This test can be used whenever N+1 can be factored to 33.33% of the size
 of N. (Actually, the factored part must be greater than the cube root of
 N/1000000). This test is conclusive.
A.3.4 F-Strong test
 This test is used when you use the -t option, and your factors don't reach
 the magic 33.33%. It is a strong-primality test, and gives more certainty
 than a Fermat test, but still is NOT a proof!

In the case of this PRP, Tony's PFGW run attempted an N-1 test but couldn't attain the needed 33.33% factored part of N-1, so it only ended up producing an F-Strong PRP test.

maxal · 2010-03-03, 01:36

Quote:

Originally Posted by mdettweiler

Code:

A.3.4 F-Strong test
 This test is used when you use the -t option, and your factors don't reach
 the magic 33.33%. It is a strong-primality test, and gives more certainty
 than a Fermat test, but still is NOT a proof!

In the case of this PRP, Tony's PFGW run attempted an N-1 test but couldn't attain the needed 33.33% factored part of N-1, so it only ended up producing an F-Strong PRP test.

And what is exactly "strong-primality test" that "gives more certainty than a Fermat test"? I would guess it's Miller-Rabin test (that does not make sense for Wagstaff numbers using base 2 as explained above).

mdettweiler · 2010-03-03, 02:01

Quote:

Originally Posted by maxal

And what is exactly "strong-primality test" that "gives more certainty than a Fermat test"? I would guess it's Miller-Rabin test (that does not make sense for Wagstaff numbers using base 2 as explained above).

No, I'm quite sure it isn't a Miller-Rabin test; I'm pretty sure it's a special type of method (not sure what exactly it is--all I know is that PFGW calls it "F-Strong test") that arises from an N-1 or N+1 test without sufficient factorization. Someone with more familiarity with such things can feel free to elaborate here.

philmoore · 2010-03-03, 13:41

I'm guessing it is a strong Frobenius test. Can anyone confirm this?

Paul Bourdelais · 2010-03-03, 14:37

Quote:

Originally Posted by diep

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

Congratulations on your discovery and I hope you extend the search. Once the large gap is verified, I would suspect another larger PRP is not too far (p<5500000) since these primes tend to occur in pairs after such large gaps, but of course no gaurantees. I have nearly completed a search for all Repunit PRPs with bases from -11 to 11 up to a base 10 length of 250,000 digits. Good Luck!

CRGreathouse · 2010-03-03, 16:48

Quote:

Originally Posted by Paul Bourdelais

Once the large gap is verified, I would suspect another larger PRP is not too far (p<5500000) since these primes tend to occur in pairs after such large gaps

Why?

I mean, in a region that large there's a decent chance of a Wagstaff prime popping up anyway -- I estimate a 57% chance based on an off-the-cuff adaptation of Wagstaff's heuristic for Mersenne numbers (this is probably low, since I haven't examined the numbers mod 8). But why do you expect pairs after large gaps? I would expect them to be (after transforming to normalize the probabilities) Poisson-distributed.

ixfd64 · 2010-03-03, 22:39

Tony, I did not know your wife had passed away until just now. I'm really sorry to hear that.

T.Rex · 2010-03-04, 06:50

Quote:

Originally Posted by ixfd64

Tony, I did not know your wife had passed away until just now. I'm really sorry to hear that.

Thanks a lot. A new life has started for me now... Tears are over. Looking for a new sun in my life...
Tony

Paul Bourdelais · 2010-03-04, 22:36

I chose p<5500000 since it is one average gap higher than 4000000 in base -3 with G=.47 instead of 0.56145948. Since the distribution of primes is random (Poisson), the location of the next prime is not deterministic, but 2 large gaps, back to back is very rare. To quote from Caldwell's prime pages
http://primes.utm.edu/notes/faq/NextMersenne.html

Noll's nebulous "Island Theory" for Mersennes (which I have never seen quantified) seems to roughly state that Mersennes occur in clumps with gaps between them. Perhaps so, but that is exactly what you would expect from any Poisson process!

It seems likely that after large gaps, we have encountered a "clump" of 2 or 3 primes. Even though I know that the gaps are independent, they can not all be uniformly spaced either.

Paul Bourdelais · 2010-03-05, 13:00

Sorry, base -2 not base -3

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-03-03, 13:41	#49
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3×373 Posts	I'm guessing it is a strong Frobenius test. Can anyone confirm this?

2010-03-03, 22:39	#52
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 5×17×29 Posts	Tony, I did not know your wife had passed away until just now. I'm really sorry to hear that.

2010-03-04, 22:36	#54
Paul Bourdelais Mar 2010 3 Posts	I chose p<5500000 since it is one average gap higher than 4000000 in base -3 with G=.47 instead of 0.56145948. Since the distribution of primes is random (Poisson), the location of the next prime is not deterministic, but 2 large gaps, back to back is very rare. To quote from Caldwell's prime pages http://primes.utm.edu/notes/faq/NextMersenne.html Noll's nebulous "Island Theory" for Mersennes (which I have never seen quantified) seems to roughly state that Mersennes occur in clumps with gaps between them. Perhaps so, but that is exactly what you would expect from any Poisson process! It seems likely that after large gaps, we have encountered a "clump" of 2 or 3 primes. Even though I know that the gaps are independent, they can not all be uniformly spaced either.

2010-03-05, 13:00	#55
Paul Bourdelais Mar 2010 3₁₀ Posts	Sorry, base -2 not base -3