mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-04-28, 13:52   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16178 Posts
Default Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1)

Hello,

Let consider the following conjecture, which is based on my previous thread (DiGraph for LLT) where I provide theorems from Shallit and Vasiga, and which makes use of the properties of the LLT Cycles instead of the LLT Tree as does the Lucas-Lehmer-Test :

\large M_q \text{ is prime }  \Longleftrightarrow \ S_{q-1} \equiv S_0 \ \pmod{M_q} \text{ , where: } S_0=3^2+1/3^2 , \ S_{i+1}=S_i^2-2 \ .

I have checked this is true up to M26.

Can you prove this is true for all q prime ?


Then, since it seems there are always cycles of length \frac{q-1}{2}, I think it is possible to build a test saying:

\large S_0=3^x+1/3^x , \ S_{i+1}=S_i^2-2 , \text{ then: } \ S_{(q-1)/2} \ \neq \ S_0 \ \pmod{M_q}  \ \Longrightarrow  \ M_q \text{ is not prime }  .

\large S'_0= f(S_{(q-1)/2}), \ S'_{i+1}=S'_i^2-2 , \text{ then: } \ S'_{(q-1)/2} \ \equiv \ S'_0 \ \pmod{M_q}  \ \Longleftrightarrow  \ M_q \text{ is prime }  .

And thus, this could speed up when Mq is not prime.

Okay, it's just a guess ... but, who knows what one can discover with LLT Cycles !

Tony
T.Rex is offline   Reply With Quote
Old 2006-04-29, 09:47   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Quote:
Originally Posted by T.Rex
... since it seems there are always cycles of length \frac{q-1}{2} (under x^2-2 modulo a Mersenne prime) ...
I've checked this is true for all Mersenne primes from M3 to M43.
Maybe it is easy to build a proof.
Tony
T.Rex is offline   Reply With Quote
Old 2006-04-29, 10:05   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default An example for q=13

Here is an example of what seems possible.

Let: \large q=13 , \ x=28 , \ f=llt^{\bot} : \ x \mapsto x^3-3x .

We have:

\large S_0=3^{28}+1/3^{28}=101 , \ S_1 =2008, \ S_2=2090, \ S_3=2295, \ S_4=210, \ S_5=3143, \ S_6=101=S_0.

So step 1 is true.

\large f(101)=-2068

\large S'_0=-2068 , \ S'_1=920, \ S'_2=2725, \ S'_3=-3614, \ S'_4=3651, \ S'_5=3042, \ S'_6=-2068

So step 2 is true, too.


But, for q=13 :
- there is 1 Cycle of length (q-1)/2 which jumps to himself (S_0=-4093) through: \large S'_0= f(S_{(q-1)/2}),
- there is 1 Cycle of length (q-1)/2 which jumps to a Cycle of length (q-1)/4 (S_0=2255) again through:\large S'_0= f(S_{(q-1)/2}).
- and there are cycles that are not generated by \large 3^x+1/3^x (does it show a problem in Shallit's theorem ?).

Tony

Last fiddled with by T.Rex on 2006-04-29 at 10:08
T.Rex is offline   Reply With Quote
Old 2006-05-08, 14:46   #4
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default A (possible) proof faster than LLT and Pépin's tests

I may have not been enough clear in the previous posts. So here is a summary of the idea.

The Lucas-Lehmer-Test is based on the Tree built by llt : x --> x^2-2 mod Mq. We usually start with S0=4, but there are plenty other starting values.
Since we cannot divide the q-1 iterations in smaller parts, there is no hope to improve the LLT in order to build a faster proof.

As proved by Shallit and Vasiga, the llt(x) function not only builds a Tree ; it also builds Cycles.
I think q-1 iterations of llt are needed for proving that a Mersenne number is prime. And the conjecture I've given in first post seems to show that LLT-Cycles of length q-1 can be used the same way we are using the LLT-Tree.
Now, there are not only Cycles of length q-1 but there are also Cycles of length (q-1)/2.
If the Mersenne number is not prime, it is possible that some Cycles of length (q-1)/2 still exist. But, I think that it is not possible to go through 2 "connected" Cycles of length (q-1)/2 when Mq is not prime.
"Connected" here means that we jump from a Cycle of length (q-1)/2 to another Cycle of same length in such a way that the iterations done in the second Cycle can be added to the iterations done in the first Cycle. I think this is true if we use the llth : x --> x^3-3*x mod Mq function. {This is already true for the Tree, as said D. Shanks : if you apply 1) llt and then 2) llth at each iteration, you reach 0 in (q-1) iterations. llt(llth(x)) = llth(llt(x))}
So, if the Mersenne number is prime, succeeding to go through 2 connected Cycles of length (q-1)/2 should show that Mq is prime. Failing at first or second Cycle should show that Mq is composite. Failing at first Cycle is very interesting since it would require only (q-1)/2 iterations.

My experimental study of the Cycles generated with q=13 and q=17 shows that it works: there are at least 2 Cycles of length (q-1)/2 that are connected by the llth function. The problem is to find a starting point: S_0=(3^n+1/3^n) \ \pmod{Mq}. I've found there are relationships between the factors of n and the factors of 2M_{q-1}.

Also, there exist proofs of LLT-like tests for Fermat numbers. And the paper of Shallit and Vasiga show that the DiGraph under x^2-2 modulo a Fermat prime is also made of one Tree and many Cycles.
If someone can provide a proof of my ideas for Mersenne numbers, then this could surely be extended to Fermat numbers. It would be very nice to be able to prove that F34 is not prime in less than 2^34=17179869184 iterations (1000 years of computation with 1 fast CPU, if I remember well) !!

Also, since there are also Cycles of length (q-1)/d , it should be possible to divide the Cycle-LLT in d smaller parts.


I've built these idea on experimental studies of the Cycles of q=5,7,11,13 and 17 . I may be wrong. Or maybe it is impossible to build a proof (it is far over my skills !!).
However I'm optimistic: few people have studied the properties of LLT-Cycles.
Even if the probability to succeed is very small, I think it is worth to increase our knowledge about the properties of LLT-Cycles. People having ideas and Mathematical skills (much more than mine) are welcome to provide comments and ideas (and theorems !).
If you think my idea is worth, please talk about it to other people.
If you think I'm wrong, please let me know.

Regards,

Tony
T.Rex is offline   Reply With Quote
Old 2006-05-09, 05:09   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

100000000001012 Posts
Default

Even though this is way over my head, I would love to see what R. Silverman has to say.
Uncwilly is offline   Reply With Quote
Old 2006-05-09, 09:36   #6
hhh
 
hhh's Avatar
 
Jun 2005

373 Posts
Default

Quote:
Originally Posted by T.Rex
I've checked this is true for all Mersenne primes from ...
Tony
You are speaking about equivalences, right? Without even reading your conjecture, I wonder if you checked it for all "Mersenne composites", too?
I confess, though, not to be able to any further help nor criticism.
H.
hhh is offline   Reply With Quote
Old 2006-05-09, 12:37   #7
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16178 Posts
Default

Quote:
Originally Posted by hhh
You are speaking about equivalences, right ?
Yes
Quote:
Without even reading your conjecture, I wonder if you checked it for all "Mersenne composites", too ?
If you talk about the conjecture providing a LLT-like test based on Cycles, Yes I've checked it for all q prime: a PARI program based on the one below said "Prime" for all Mersenne primes up to M26 and "Composite" for all Mersenne composites up to M26.

T.

Code:
q=5: S0=16 -> 6 -> 3 -> 7 -> 16

q=7: S0=122 -> 23-> 19 -> 105 -> 101 -> 39 -> 122

q=11: S0=464 -> 359 -> 1965 -> 581 -> 1851 -> 1568 -> 175 -> 1965 -> 581 -> 1851 -> 1568

q=13: S0=7290 -> 890 -> 5762 -> 2519 -> 5525 -> 5957 -> 2435 -> 7130 -> 3552 -> 2562 -> 2851 -> 2727 -> 7290

PARI/gp:

LLGT(q)=
{
M=2^q-1; S0=(3^2+1/3^2)%M; print(S0); S=S0;
for(i=1, q-1, S=(S^2-2)%M; print(S));
if(S==S0, print("Prime !"), print("Composite"))
}
T.Rex is offline   Reply With Quote
Old 2006-05-09, 12:40   #8
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Quote:
Originally Posted by Uncwilly
... I would love to see what R. Silverman has to say.
Mee too.
T.
T.Rex is offline   Reply With Quote
Old 2006-05-09, 16:20   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

52·11·41 Posts
Default

Hi, Tony:

I think it would be very useful for you to do an asymptotic-work (and storage) estimation for the cost of *identifying* cycles for large M(p). Knowing that there *exist* cycles for composite M(p) would be of little use if actually ferreting them out proves to be prohibitively expensive in terms of runtime or memory. I'm not sure if Floyd's cycle-finding algorithm is still the state of the art there, but I expect a work estimate based on it would tell us quite a lot.

Last fiddled with by ewmayer on 2006-05-09 at 16:22
ewmayer is offline   Reply With Quote
Old 2006-05-09, 16:26   #10
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

Quote:
Originally Posted by T.Rex
\large S_0=3^x+1/3^x , \ S_{i+1}=S_i^2-2 , \text{ then: } \ S_{(q-1)/2} \ \neq \ S_0 \ \pmod{M_q}  \ \Longrightarrow  \ M_q \text{ is not prime }  .

Quote:
Originally Posted by T.Rex
q=5: S0=16 -> 6 -> 3 -> 7 -> 16
??
J
bearnol is offline   Reply With Quote
Old 2006-05-09, 16:41   #11
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

btw, the LL test is (very close to) a theoretical maximum of efficiency for any primality test...
J
bearnol 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
Conjectured Primality Test for Specific Class of Mersenne Numbers primus Miscellaneous Math 1 2014-10-12 09:25
Conjectured Primality Test for Specific Class of k6^n-1 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15
there is another way to test the primality of a no shawn Miscellaneous Math 5 2007-07-17 17:55
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 13:05.

Sat Jul 4 13:05:09 UTC 2020 up 101 days, 10:38, 2 users, load averages: 2.14, 1.77, 1.60

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.