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

2010-03-03, 01:06   #45
diep

Sep 2006
The Netherlands

2×17×23 Posts

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

2010-03-03, 01:16   #46
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3×2,083 Posts

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.

Last fiddled with by mdettweiler on 2010-03-03 at 01:17

2010-03-03, 01:36   #47
maxal

Feb 2005

11×23 Posts

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

Last fiddled with by maxal on 2010-03-03 at 01:39

2010-03-03, 02:01   #48
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

624910 Posts

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.

Last fiddled with by mdettweiler on 2010-03-03 at 02:01

 2010-03-03, 13:41 #49 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 100010111112 Posts I'm guessing it is a strong Frobenius test. Can anyone confirm this?
2010-03-03, 14:37   #50
Paul Bourdelais

Mar 2010

3 Posts

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!

2010-03-03, 16:48   #51
CRGreathouse

Aug 2006

3×1,993 Posts

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.

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

Feb 2004
France

16378 Posts

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

 2010-03-04, 22:36 #54 Paul Bourdelais   Mar 2010 316 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

 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:32.

Thu Jan 27 11:32:51 UTC 2022 up 188 days, 6:01, 1 user, load averages: 1.66, 1.63, 1.50