mersenneforum.org  

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

Reply
 
Thread Tools
Old 2010-03-03, 01:06   #45
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

677 Posts
Default

Quote:
Originally Posted by maxal View Post
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
diep is offline   Reply With Quote
Old 2010-03-03, 01:16   #46
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

Quote:
Originally Posted by maxal View Post
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.

Last fiddled with by mdettweiler on 2010-03-03 at 01:17
mdettweiler is offline   Reply With Quote
Old 2010-03-03, 01:36   #47
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
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).

Last fiddled with by maxal on 2010-03-03 at 01:39
maxal is offline   Reply With Quote
Old 2010-03-03, 02:01   #48
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by maxal View Post
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.

Last fiddled with by mdettweiler on 2010-03-03 at 02:01
mdettweiler is offline   Reply With Quote
Old 2010-03-03, 13:41   #49
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

45D16 Posts
Default

I'm guessing it is a strong Frobenius test. Can anyone confirm this?
philmoore is offline   Reply With Quote
Old 2010-03-03, 14:37   #50
Paul Bourdelais
 
Mar 2010

3 Posts
Default

Quote:
Originally Posted by diep View Post
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!
Paul Bourdelais is offline   Reply With Quote
Old 2010-03-03, 16:48   #51
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10110111011112 Posts
Default

Quote:
Originally Posted by Paul Bourdelais View Post
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.
CRGreathouse is online now   Reply With Quote
Old 2010-03-03, 22:39   #52
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

22×3×191 Posts
Default

Tony, I did not know your wife had passed away until just now. I'm really sorry to hear that.
ixfd64 is offline   Reply With Quote
Old 2010-03-04, 06:50   #53
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16178 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
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
T.Rex is offline   Reply With Quote
Old 2010-03-04, 22:36   #54
Paul Bourdelais
 
Mar 2010

3 Posts
Default

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 is offline   Reply With Quote
Old 2010-03-05, 13:00   #55
Paul Bourdelais
 
Mar 2010

3 Posts
Default

Sorry, base -2 not base -3
Paul Bourdelais 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 14:34.

Thu Aug 13 14:34:14 UTC 2020 up 11:09, 1 user, load averages: 1.79, 1.59, 1.57

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.