mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-07-21, 20:56   #1
GP2
 
GP2's Avatar
 
Sep 2003

257810 Posts
Default Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness

Is there any centralized data repository for Wagstaff number testing? A list of exponents with factors, and a list of PRP test residues, possibly double-checked?

Various people have tested extensively, but have the results been centralized anywhere?

I think systematic testing has been done up to about 4M, and then Ryan Popper found (2^13372531+1)/3 and (2^13347311+1)/3 which are actually the largest known PRPs, and it's not clear if anyone has searched the gap between 4M and 13.3M

However, I'd especially like to confirm that testing has been done to try to invalidate the New Mersenne Conjecture, by factoring or testing all the known Mersenne prime exponents larger than 4M as Wagstaff exponents, to see if any of them might be Wagstaff primes as well. I assumed this was the case, but maybe I'm wrong?

Edit: Chris Caldwell's page says the Wagstaff status of Mersenne prime exponents 20996011 and 30402457 is unknown, with no info about any higher exponents. Is this still true?

Last fiddled with by GP2 on 2018-07-21 at 21:27
GP2 is offline   Reply With Quote
Old 2018-07-21, 21:08   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17×79 Posts
Default

Quote:
Originally Posted by GP2 View Post
Is there any centralized data repository for Wagstaff number testing? A list of exponents with factors, and a list of residues, possibly double-checked?
Why not use my own error checking on these numbers? Even a single run is much stronger than your double or even triple/quadruple check if you compare only RES64. The same is true for Mersenne numbers.
R. Gerbicz is offline   Reply With Quote
Old 2018-07-21, 22:26   #3
GP2
 
GP2's Avatar
 
Sep 2003

50228 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Why not use my own error checking on these numbers? Even a single run is much stronger than your double or even triple/quadruple check if you compare only RES64. The same is true for Mersenne numbers.
I was not really interested in Wagstaff testing until now, so I'm not familiar with it. Can mprime/Prime95 be used to do Wagstaff PRP testing? I was under the impression that it can only do k*b^n+c where all of these are integers.

Which programs can do Wagstaff PRP testing, and has your Gerbicz error check been implemented for them yet?

Also, it's necessary to know which exponents p have known factors for (2^p + 1)/3

Last fiddled with by GP2 on 2018-07-21 at 22:28
GP2 is offline   Reply With Quote
Old 2018-07-21, 22:50   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17×79 Posts
Default

Quote:
Originally Posted by GP2 View Post
I was under the impression that it can only do k*b^n+c where all of these are integers.
It is in the form of (k*2^n+c)/d, so for these I'm assuming that the error checking is already included in prime95 (note that here the base=2).

ps.
If you have an algorithm/code for k*b^n+c, then you have a code also for (k*b^n+c)/d, because you need only one biginteger division (or even eliminate that also if d is "small").
R. Gerbicz is offline   Reply With Quote
Old 2018-07-21, 23:43   #5
GP2
 
GP2's Avatar
 
Sep 2003

2×1,289 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
you need only one biginteger division
You also need to get more sleep. At least I do, clearly...
GP2 is offline   Reply With Quote
Old 2018-07-22, 07:56   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

24778 Posts
Default

Quote:
Originally Posted by GP2 View Post
You also need to get more sleep. At least I do, clearly...
OK, I was too compact/short.
Here are the deatils: we restrict to b=2 to enable my fast error checking
let N=k*2^n+c (but we want a test for N/d),
if N/d is a Fermat prp to base=a^d, then

(a^d)^(N/d)==a^d mod (N/d), so
a^N==a^d mod (N/d), for this first get

res=a^(2^n) mod N using my check, then compute
(you can assume that k,c is small, but this works in general)

res2=res^k*a^c mod N, until this point you have not used d.
Reduce this:
res'=res2 mod (N/d) to get a^N mod (N/d), using a single biginteger division
(or two if you count also the N/d division).

[There is another option here, if you begin with a^k mod N, and then use
squarings, in timing there is no real difference, also note that c<0 is possible].

Assumed that you are a super heavy p95 user (I'm not using it on a daily routine)
, PRP-CF doesn't really using the error checking for (2^p-1)/d ?
Your own problem (2^p+1)/3 is totally similar. In general I'm not checking things where I'm sure,
but if it is really not in p95, then it should be.

Have you seen this?
http://www.mersenneforum.org/showthread.php?t=12157

Just picked up a random (known!) prime: (use the -d flag)
in worktodo.txt put PRP=2675,2,1350023,1
Code:
...
[Work thread Jul 22 09:22] Resuming Gerbicz error-checking PRP test of 2675*2^1350023+1 using all-complex FMA3 FFT length 96K, Pass1=384, Pass2=256, clm=4, 4 threads
...
[Work thread Jul 22 09:23] 2675*2^1350023+1 is a probable prime! Wg8: A97983C5,00000000
And you can also see in results.txt that my error check has been used.

So at least for d=1 (or there f=1), it is really working.
But for f>1 it is just throwing
Code:
[Main thread Jul 22 09:28] Illegal line in worktodo.txt file: PRP=1,2,986191,1,3
or when you try to trick it with f=1:
Code:
[Work thread Jul 22 09:29] PRP test of 2^986191+1 aborted -- number is divisible by 3
Well, we know this. Maybe overlooked something trivial how to set the numbers in worktodo.txt.
But if N=k*2^n+c is already working, then N/d should be also, the underlying Maths is so trivial.

Last fiddled with by R. Gerbicz on 2018-07-22 at 08:05 Reason: more info
R. Gerbicz is offline   Reply With Quote
Old 2018-07-22, 08:10   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17×79 Posts
Default

Bingo: you have to use this: PRP=1,2,986191,1,"3"
at least on Linux, and, then
Code:
..
[Work thread Jul 22 10:07] Starting Gerbicz error-checking PRP test of 2^986191+1/3 using all-complex FMA3 FFT length 48K, Pass1=768, Pass2=64, clm=2, 4 threads
[Work thread Jul 22 10:08] Iteration: 10000 / 986191 [1.01%], ms/iter:  0.124, ETA: 00:02:00
[Work thread Jul 22 10:08] Iteration: 20000 / 986191 [2.02%], ms/iter:  0.122, ETA: 00:01:57
..

[Work thread Jul 22 10:09] Iteration: 980000 / 986191 [99.37%], ms/iter:  0.122, ETA: 00:00:00
[Work thread Jul 22 10:10] 2^986191+1/3 is a probable prime! Wg8: D9C45894,00000000
(it was a known prp Wagstaff prime)
Minor issue, but parentheses are missing here in text: 2^986191+1/3.

Last fiddled with by R. Gerbicz on 2018-07-22 at 08:18
R. Gerbicz is offline   Reply With Quote
Old 2018-07-22, 10:14   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

34·5·7 Posts
Default

I worked on the NMC:
http://mersenneforum.org/showthread.php?t=19229
http://hoegge.dk/mersenne/NMC.html

But as you can see in that thread, most agree that it is a "joke" conjecture, so I have not worked on it since adding the newest Mersenne primes.

You can trial factor Wagstaff numbers on GPU using mfaktc-win-64.Wagstaff.exe

Last fiddled with by ATH on 2018-07-22 at 10:21
ATH is offline   Reply With Quote
Old 2018-07-22, 18:31   #9
GP2
 
GP2's Avatar
 
Sep 2003

2·1,289 Posts
Default

I was made aware of these resources that are useful for the New Mersenne Conjecture:

Factors of Wagstaff numbers with Mersenne-prime exponents:
http://bearnol.is-a-geek.com/Mersenn...neplustwo.html

PRP tests of Wagstaff numbers with Mersenne-prime exponents:
https://groups.google.com/forum/#!to...wo/j4RYTPh54-0
GP2 is offline   Reply With Quote
Old 2018-07-22, 18:34   #10
GP2
 
GP2's Avatar
 
Sep 2003

2·1,289 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Bingo: you have to use this: PRP=1,2,986191,1,"3"
Yes, and I was actually well aware of how to do that sort of thing, since I've been doing both PRP and PRP cofactor testing. But I had some kind of brain freeze I think.
GP2 is offline   Reply With Quote
Old 2018-07-24, 08:24   #11
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

67410 Posts
Default

the short answer to all questions i got by e-mail and messages and everything regarding wagstaff is YES.

Systematic testing from our part has been done until 10M. I have all results until 10M.

TF i have to lookup how far i did do it, as i did do it in waves. I think i had it until 52-54 bits done at about 20-24 cores up to 12M-15M, i would need to look that one up.

For the later gpgpu TF software that is total peanuts of course.

And YES of course Wagstaff has the same habits like Mersenne. The main differences between Wagstaff and Mersenne, is that there seems no official proving method for Wagstaff has been recognized. I know some French and a Canadian researcher think different there, yet i'm not gonna pick sides there and just cite what i know as a layman there.

Another difference seems the factoring. Trial Factoring, but i lack hard data of Mersenne to compare it with, seems more effective for Wagstaff than it is for Mersenne.

Some researcher who wants to take this important unpaid job on himself might be able to officially determine that. I just posted here a gutfeeling.

Though there might be a simple explanation for it that has to do with the spread of primes there. Because we divide by 3, maybe it is the case there is less Wagstaffs between [n and 2n].

As a result TF seemingly is far more effective so it would be possible to search Wagstaff deeper than Mersenne using the same horse power.

Yet you'll find less PRP's than Mersenne primes of course using that same horse power.

I do not have a formula how many less PRP's there are between [n;2n] of Wagstaff versus Mersenne. Blindfolded i would guess it ranges somewhere between (log 3) / (log 2) and factor 3.

That means you could be busy with it a long time and not find any PRP and run the risk that when you are close to next one, the Ryan Propper team then suddenly posts them online including a "we were so lucky letter", which Jeff Gilchrist and Tony Reix, when they had to run fast and were out of paper at the bathroom, used over there.
diep is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Testing Mersenne Primes with Elliptic Curves a nicol Math 3 2017-11-15 20:23
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
Statistical odds for prime in Wagstaff vs Mersenne diep Math 27 2010-01-13 20:18
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53

All times are UTC. The time now is 18:46.

Thu Jun 4 18:46:44 UTC 2020 up 71 days, 16:19, 2 users, load averages: 2.09, 1.73, 1.77

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.