mersenneforum.org  

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

Reply
 
Thread Tools
Old 2008-10-05, 06:33   #1
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

2·72 Posts
Default PRIMALITY PROOF for Wagstaff numbers!

At last I have found the proof! Needed some lateral thinking.

This is as per my conjecture 4 in a paralel thread but now hopefully we can upgrade to theorem once checked. I am inviting comment to the attached proof.


\blue \text{Let } q \text{ be a prime integer } > \ 3 \text{ , } W_q = \frac{1}{3}(2^q+1) \text{.}

\blue W_q \text{ is prime }  \Longleftrightarrow \ S_{q} \equiv S_2 \ \pmod{W_q} \text{ , where: } S_0=6 \text{ , and } \ S_{i+1}=S_i^2-2 \ \pmod{W_q}  \ .

best regards
Anton Vrba
Attached Files
File Type: pdf Waggstaff0.0.pdf (90.3 KB, 408 views)
AntonVrba is offline   Reply With Quote
Old 2008-10-05, 08:02   #2
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

2×72 Posts
Default

I noticed a small typo, page 3 comment 2
(a+i)^(2k+1)=(a-i) (mod 2k+1) and not (mod (a+i)) as in the paper.

so please correct.
AntonVrba is offline   Reply With Quote
Old 2008-10-05, 08:31   #3
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

7·353 Posts
Default

Another typo, page 3, comment 1: "The reasoning presented
may not be knew and already documented somewhere and references
are kindly requested."

I guess this should read: "...may not be new..."

Edit: Your link to conjecture 4 does not work - there is one "http" too much.

Last fiddled with by Andi47 on 2008-10-05 at 08:35
Andi47 is offline   Reply With Quote
Old 2008-10-05, 10:55   #4
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·457 Posts
Default Waowwww !!!!

Hello Anton !
Congratulations to your work !!!

I have juste read the proof and I need some time to chew it... However, I see that Phil Carmody already has a comment about a part that seems wrong to him.
I hope that any unclear parts will be cleared asap, and that other people will approve your proof (Hey Bob ! Your comments ?) so that I can send my 100 Euro bank-note to you !

Some preliminary comments:
- In (2) and (4) and (6), it seems to me that you used q instead of p.
- In many places, you use = instead of \equiv
- About (9) { S(p-1)=-S(1) (Mod Wp) } , why ? It has been a question for the LLT when the "Penultimate Lucas-Lehmer step" is - or +. No proof. But I remember that I read that, when using LLT in another case, it is always + (can't remember more details...). What is your proof ?
- I do not see in the theorem the extra conditions saying that S2 must be reached at step p and never before step p. Is it no more useful ? With this p-2 iteration, is it impossible for a composite to reach S2 at step i<p ? Is it what your comment 2 is saying ?
- I'm surprised to see that there is a (p-2) cycle... but that works ! I've checked with different values. I should look again at these damned cycles for Wagstaff primes !
- about your comments dealing with the cost of operations, we really don't care about one step less, same about some small numbers at beginning of iterations. That's peanuts when you have millions of iterations to do with FFT.
- what's inefficient in your test for Wagstaff numbers is your use of (mod Wp). There are technics for that (see LLR test) but they have a cost at each iteration, I think. Using S^2-2 (mod Np) with N=1+2^p enables to use faster FFT with modulo, I think, meaning the Prime95 code can be used with nearly no change. Hey ! you other people experts in this (Crandall, Woltman, Penné, & others), do you agree ?
- and you say not a word about my idea to use cycles of a Digraph, nor you talk about Shallit&Vasiga work (they gave proofs about the cycles). Once checked, the proof is yours, but I'm not sure the idea is entirely yours. Like the LLT is named Lucas-Lehmer-Test, since Lehmer provided a complete proof though Lucas did not but he had the idea, we have to clarify who had the idea to use Cycles and thus to test Sp=S0 (or Si, since you can iterate in a tail before reaching a cycle). You had the idea to use cycles for Wagstaff numbers, for sure. But, as far as I know, based on the Mersenne forum, I was the first to propose to use Cycles of a Digraph as a primality test. Did you write on a forum before me ? I need this point to be clarified because I would like that all the time I've spent on these damned tree and cycles of the Digraph under x^2-2 or x^2 modulo a prime before my wife died is not lost and that my children can see that all the time I didn't spend with her was useful in some way (Maths never die).

Clarifying who had innovative ideas is one thing. Being able to build a proof is another thing. I'm VERY HAPPY you have made a big step !! Now, wait for other mathematicians to check and approve the proof !

What is important (once proof confirmed) is that now not only Mersenne numbers (and also the rare Fermats) can be verified proof or not in a very fast way. Other numbers are k*2^n-1 numbers, with LLR, but it is a little bit smaller. Maybe George will provide such a test for Wagstaffs ? like Jean already did.

Again, congratulations !!

Tony
T.Rex is offline   Reply With Quote
Old 2008-10-05, 11:53   #5
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

1428 Posts
Default

AND, after a rest, I noticed a wild and false conclusion regarding the order of the group, this has been corrected as well as the equality (19) regarding the group order.

I also added the alternate cycle S_0 = -3/2

Tony thanks for your comments I shall work those in and address your queries separately.
I started of with q but then changewd to p so I must have skipped some. Editing in LaTex is not my strength and a complete new experience.
Attached Files
File Type: pdf Waggstaff0.2.pdf (97.3 KB, 166 views)

Last fiddled with by AntonVrba on 2008-10-05 at 12:07
AntonVrba is offline   Reply With Quote
Old 2008-10-05, 12:02   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101100010002 Posts
Default

Quote:
Originally Posted by AntonVrba View Post
At last I have found the proof! Needed some lateral thinking.

This is as per my conjecture 4 in a paralel thread but now hopefully we can upgrade to theorem once checked. I am inviting comment to the attached proof.
Your proof is wrong. You can not do that step from (15) to (16), because if
a*c==b*c mod d, then you can't say that a==b mod d. You can do it only in that case, if you could prove that gcd(c,d)=1 is true in your ring (so if gcd(delta,W(p))=1 is true).
R. Gerbicz is offline   Reply With Quote
Old 2008-10-05, 12:07   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by AntonVrba View Post
\blue W_q \text{ is prime }  \Longleftrightarrow \ S_{q} \equiv S_2 \ \pmod{W_q} \text{ , where: } S_0=6 \text{ , and } \ S_{i+1}=S_i^2-2 \ \pmod{W_q}  \ .
Is the \pmod{W_q} in \blue \ S_{q} \equiv S_2 \ \pmod{W_q} necessary? It seems that since both S_{q} and S_2 are already \pmod{W_q} it is completely unnecessary.
Mini-Geek is offline   Reply With Quote
Old 2008-10-05, 13:00   #8
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

2·72 Posts
Default

Quote:
Originally Posted by T.Rex View Post
Some preliminary comments:
- About (9) { S(p-1)=-S(1) (Mod Wp) } , why ? It has been a question for the LLT when the "Penultimate Lucas-Lehmer step" is - or +. No proof. But I remember that I read that, when using LLT in another case, it is always + (can't remember more details...). What is your proof ?
just remember s^2-2 = (-s)^2-2


Quote:
Originally Posted by T.Rex View Post
- I do not see in the theorem the extra conditions saying that S2 must be reached at step p and never before step p. Is it no more useful ? With this p-2 iteration, is it impossible for a composite to reach S2 at step i<p ? Is it what your comment 2 is saying ?
No, comment two says that S_0 and S_1 will never repeat in the iteration. Further, I believe that S_0=6,-6 and S_0=-3/2 are the only three numbers to guarantee cycles of p-2 and p-1 respectively and that all elemets of S_0 to S_(p-1) are unique for all prime W_p. I do not know what to call these numbers any suggestion.

Quote:
Originally Posted by T.Rex View Post
- I'm surprised to see that there is a (p-2) cycle... but that works !
You have not studied the digraphs as you claim you have.


Quote:
Originally Posted by T.Rex View Post
- what's inefficient in your test for Wagstaff numbers is your use of (mod Wp). There are technics for that (see LLR test) but they have a cost at each iteration, I think. Using S^2-2 (mod Np) with N=1+2^p enables to use faster FFT with modulo, I think, meaning the Prime95 code can be used with nearly no change. Hey ! you other people experts in this (Crandall, Woltman, Penné, & others), do you agree ?
I am sure that this is correct but I cannot prove it for now - somebody else can. The proof of sufficiency is not valid for 3W_p but the proof of necessity would be valid.


Quote:
Originally Posted by T.Rex View Post
- and you say not a word about my idea to use cycles of a Digraph, nor you talk about Shallit&Vasiga work (they gave proofs about the cycles).
Please note I have not named the test but I am presenting the proof. I have not made use of any work of Shallit&Vasiga and thus no need to mention. We are not proofing the form of the diagraph, Shallit&Vasiga have done that, but the proof is making a statement regarding the possible divisors of W_p.

The Lucas-Lehmer test proves that 2^p-1 has no non-trivial factors smaller than 2^(p-1). A consequence of this is that the number is prime.

What this test does assert, is that there are no possible divisors smaller than sqrt(W_p), and as a consequence, W_p is prime - and thus it is very similar to the Lucas-Lehmer test.

Quote:
Originally Posted by T.Rex View Post
Again, congratulations !!

Tony
Thanks we now need to wait for the experts.

Last fiddled with by AntonVrba on 2008-10-05 at 13:22 Reason: in last sentance change no to now
AntonVrba is offline   Reply With Quote
Old 2008-10-05, 13:03   #9
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

9810 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Is the \pmod{W_q} in \blue \ S_{q} \equiv S_2 \ \pmod{W_q} necessary? It seems that since both S_{q} and S_2 are already \pmod{W_q} it is completely unnecessary.
Thanks for the correction
AntonVrba is offline   Reply With Quote
Old 2008-10-05, 13:18   #10
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

6216 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Your proof is wrong. You can not do that step from (15) to (16), because if
a*c==b*c mod d, then you can't say that a==b mod d. You can do it only in that case, if you could prove that gcd(c,d)=1 is true in your ring (so if gcd(delta,W(p))=1 is true).
My old number theory book from 1962 says:
(1) x = y(mod m)
and say that x is congruent to y modulo m. The quantity m is called the
modulus, and all numbers congruent (or equivalent) to x (mod m) are said
to constitute a congruence (or equivalence) class. Congruence classes are
preserved under the rational integral operations, addition, subtraction, and
multiplication.

Mathematica calculates that Mod[7,3x43]=7 and Mod[7*3,3*43]=21 so is it wrong? I think you can withdraw your statement.
AntonVrba is offline   Reply With Quote
Old 2008-10-05, 13:23   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

23×3×59 Posts
Default

For example:
14==21 mod 7 is true, but after dividing
2==3 mod 7 isn't true. And you've done this.

Last fiddled with by R. Gerbicz on 2008-10-05 at 13:23
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime numbers test primality - with proof written in invisible ink Godzilla Miscellaneous Math 40 2018-10-17 00:11
APR-CL as primality proof f1pokerspeed FactorDB 14 2014-01-09 21:06
500€ Reward for a proof for the Wagstaff primality test conjecture Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
Wagstaff number primality test? ixfd64 Math 12 2010-01-05 16:36

All times are UTC. The time now is 03:04.

Wed Nov 25 03:04:06 UTC 2020 up 76 days, 15 mins, 4 users, load averages: 1.25, 1.29, 1.29

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.