mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-11-30, 19:18   #1
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

3·769 Posts
Default 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?
ixfd64 is online now   Reply With Quote
Old 2009-11-30, 19:36   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22·1,433 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
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
henryzz is offline   Reply With Quote
Old 2009-11-30, 19:38   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,409 Posts
Default

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

Last fiddled with by R. Gerbicz on 2009-11-30 at 19:38
R. Gerbicz is offline   Reply With Quote
Old 2010-01-02, 11:03   #4
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·457 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2010-01-02, 13:33   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

91410 Posts
Default My draft paper

I've provided my (DRAFT!!!!!!!) paper in this thread.
T.Rex is offline   Reply With Quote
Old 2010-01-02, 18:13   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

296710 Posts
Default

Quote:
Originally Posted by T.Rex View Post
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?
ATH is online now   Reply With Quote
Old 2010-01-02, 18:32   #7
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×457 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
T.Rex is offline   Reply With Quote
Old 2010-01-04, 18:29   #8
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

7·167 Posts
Default

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
Jeff Gilchrist is offline   Reply With Quote
Old 2010-01-04, 19:53   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,409 Posts
Default

Quote:
Originally Posted by Jeff Gilchrist View Post
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).
R. Gerbicz is offline   Reply With Quote
Old 2010-01-04, 21:00   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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?
henryzz is offline   Reply With Quote
Old 2010-01-04, 21:04   #11
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

10111001101002 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
rogue is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 06:49.

Thu Oct 22 06:49:32 UTC 2020 up 42 days, 4 hrs, 0 users, load averages: 1.30, 1.35, 1.34

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.