Wagstaff number primality test?

ixfd64 · 2009-11-30, 19:18

A while ago, there was a thread about a possible new primality test for Wagstaff numbers that had the same run-time as the Lucas-Lehmer test. However, it was considered to be only a conjecture due to a some reported errors in the proof.

This proof would be an important milestone in number theory, yet there has been no new posts in that thread since February. So far, no major academic journals or mathematics websites have mentioned this conjecture. Does anyone know if there has been any progress with the proof?

henryzz · 2009-11-30, 19:36

Quote:

Originally Posted by ixfd64

A while ago, there was a thread about a possible new primality test for Wagstaff numbers that had the same run-time as the Lucas-Lehmer test. However, it was considered to be only a conjecture due to a some reported errors in the proof.

This proof would be an important milestone in number theory, yet there has been no new posts in that thread since February. So far, no major academic journals or mathematics websites have mentioned this conjecture. Does anyone know if there has been any progress with the proof?

i think that it was disproved from memory
i still think that it might be a fast way of finding huge prps

R. Gerbicz · 2009-11-30, 19:38

Quote:

Originally Posted by ixfd64

Does anyone know if there has been any progress with the proof?

I know no progress about the proof. But there is a fast mpir/gmp implementation for it that I have written some month ago, see: http://mpir-devel.googlegroups.com/w...krTYJH3lVGu2Z5

T.Rex · 2010-01-02, 11:03

Hi,
Last year, I spent some time trying to build a proof for a modified-LLT using Cycles for Mersenne numbers. Without any success. However, I'm only an amateur and I know quite well only some old methods used by Lucas, Lehmer and Williams. I planned to publish my draft on this forum, so that other people can look and say if, in this garbish, there are some good ideas. I'll do that some day...
I know that Sir Wagstaff asked a student to look for a proof for the Vrba-Reix conjecture for Wagstaff numbers. No fresh news.
I tried to inform several Mathematicians over the world that have worked or are working in this LLt area about this conjecture.
I also have summarized the work on my Blog . (I would recommend you to read the French poetry I provide there ! Aragon !!)
Also, I'll pay 100 euros to the first guy who can provide a proof. (I would pay much more if I was richer !

)
Jean Pené has implemented the Vrba-Reix PRP test within LLR, which is based on the prime95 code. Very fast !
Just a clarification : the conjectures are true theorems about PRPs : if a Wagstaff, Mersenne or Fermat number is prime, then the property holds. So, Vrba-Reix test IS a very fast way for finding a Wagstaff PRP.
Out of the conjecture, my opinion is that the DiGraph under x^2-2 modulo a number N is a very interesting subject to be studied. I've studied some different forms of numbers and, in each case, the DiGraph of the prime numbers have properties that the non-prime numbers seems not to have. The problem is to find a way to building proofs... (too difficult for me !).
The Number Theory books I've looked at recently still do not even talk about using LLT for proving that a N+1 number (N easy to factor, like Fermats) is prime. Recently, I've discovered that Kustaa Inkeri, in 1960, provided a proof for the LLT used as a primality proof for Fermats, with seed 8 instead of the 5 I'm using. Who will continue the wonderful work of Lucas, Lehmer, Williams, ... ?
Regards,
Tony

T.Rex · 2010-01-02, 13:33

I've provided my (DRAFT!!!!!!!) paper in this thread.

ATH · 2010-01-02, 18:13

Quote:

Originally Posted by T.Rex

Jean Pené has implemented the Vrba-Reix PRP test within LLR, which is based on the prime95 code. Very fast !

I can't find anything about this in LLR version 3.7.1c. Is there a newer LLR?

T.Rex · 2010-01-02, 18:32

Quote:

Originally Posted by ATH

I can't find anything about this in LLR version 3.7.1c. Is there a newer LLR?

Yes: 3.7.2 . I have no news from Jean since a while.

Jeff Gilchrist · 2010-01-04, 18:29

I wonder how the speed of the LLR version compares to R. Gerbicz's GMP/MPIR version. Has anyone actually tested them both?

R. Gerbicz · 2010-01-04, 19:53

Quote:

Originally Posted by Jeff Gilchrist

I wonder how the speed of the LLR version compares to R. Gerbicz's GMP/MPIR version. Has anyone actually tested them both?

Gmp/mpir is slower by a lot, for example for q=127031 my version takes about 235 sec. using mpir-1.3.0, while llr372 takes about only 16 seconds. Both of the them is using only one core, but gmp/mpir isn't using complex numbers for FFT, and that is a big disadvantage in speed. (The difference probably not so large in general, because 127031 is close to 2^17).

henryzz · 2010-01-04, 21:00

Quote:

Originally Posted by R. Gerbicz

Gmp/mpir is slower by a lot, for example for q=127031 my version takes about 235 sec. using mpir-1.3.0, while llr372 takes about only 16 seconds. Both of the them is using only one core, but gmp/mpir isn't using complex numbers for FFT, and that is a big disadvantage in speed. (The difference probably not so large in general, because 127031 is close to 2^17).

is anyone here able to contribute to gmp/mpir to get rid of or improve this handicap?

rogue · 2010-01-04, 21:04

Quote:

Originally Posted by henryzz

is anyone here able to contribute to gmp/mpir to get rid of or improve this handicap?

Not likely. GMP will not accept code that runs in the FPU.

2009-11-30, 19:18	#1
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 9CF₁₆ Posts	Wagstaff number primality test? A while ago, there was a thread about a possible new primality test for Wagstaff numbers that had the same run-time as the Lucas-Lehmer test. However, it was considered to be only a conjecture due to a some reported errors in the proof. This proof would be an important milestone in number theory, yet there has been no new posts in that thread since February. So far, no major academic journals or mathematics websites have mentioned this conjecture. Does anyone know if there has been any progress with the proof?

2010-01-02, 11:03	#4
T.Rex Feb 2004 France 13·73 Posts	Ideas for a proof Hi, Last year, I spent some time trying to build a proof for a modified-LLT using Cycles for Mersenne numbers. Without any success. However, I'm only an amateur and I know quite well only some old methods used by Lucas, Lehmer and Williams. I planned to publish my draft on this forum, so that other people can look and say if, in this garbish, there are some good ideas. I'll do that some day... I know that Sir Wagstaff asked a student to look for a proof for the Vrba-Reix conjecture for Wagstaff numbers. No fresh news. I tried to inform several Mathematicians over the world that have worked or are working in this LLt area about this conjecture. I also have summarized the work on my Blog . (I would recommend you to read the French poetry I provide there ! Aragon !!) Also, I'll pay 100 euros to the first guy who can provide a proof. (I would pay much more if I was richer ! ) Jean Pené has implemented the Vrba-Reix PRP test within LLR, which is based on the prime95 code. Very fast ! Just a clarification : the conjectures are true theorems about PRPs : if a Wagstaff, Mersenne or Fermat number is prime, then the property holds. So, Vrba-Reix test IS a very fast way for finding a Wagstaff PRP. Out of the conjecture, my opinion is that the DiGraph under x^2-2 modulo a number N is a very interesting subject to be studied. I've studied some different forms of numbers and, in each case, the DiGraph of the prime numbers have properties that the non-prime numbers seems not to have. The problem is to find a way to building proofs... (too difficult for me !). The Number Theory books I've looked at recently still do not even talk about using LLT for proving that a N+1 number (N easy to factor, like Fermats) is prime. Recently, I've discovered that Kustaa Inkeri, in 1960, provided a proof for the LLT used as a primality proof for Fermats, with seed 8 instead of the 5 I'm using. Who will continue the wonderful work of Lucas, Lehmer, Williams, ... ? Regards, Tony Last fiddled with by T.Rex on 2010-01-02 at 11:30

2010-01-02, 13:33	#5
T.Rex Feb 2004 France 1665₈ Posts	My draft paper I've provided my (DRAFT!!!!!!!) paper in this thread.

2010-01-04, 18:29	#8
Jeff Gilchrist Jun 2003 Ottawa, Canada 3·17·23 Posts	I wonder how the speed of the LLR version compares to R. Gerbicz's GMP/MPIR version. Has anyone actually tested them both? Last fiddled with by Jeff Gilchrist on 2010-01-04 at 18:29

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing	Trilo	Miscellaneous Math	25	2018-03-11 23:20
Basic Number Theory 9: a primality test and a cryptosystem	Nick	Number Theory Discussion Group	9	2016-11-24 21:11
500€ Reward for a proof for the Wagstaff primality test conjecture	Tony Reix	Wagstaff PRP Search	7	2013-10-10 01:23
PRIMALITY PROOF for Wagstaff numbers!	AntonVrba	Math	96	2009-02-25 10:37
A primality test for Fermat numbers faster than Pépin's test ?	T.Rex	Math	0	2004-10-26 21:37