mersenneforum.org > Math Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1)
 Register FAQ Search Today's Posts Mark Forums Read

 2006-04-28, 13:52 #1 T.Rex     Feb 2004 France 32×103 Posts 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
2006-04-29, 09:47   #2
T.Rex

Feb 2004
France

32·103 Posts

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

 2006-04-29, 10:05 #3 T.Rex     Feb 2004 France 32·103 Posts 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
 2006-05-08, 14:46 #4 T.Rex     Feb 2004 France 32×103 Posts 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
 2006-05-09, 05:09 #5 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 10,243 Posts Even though this is way over my head, I would love to see what R. Silverman has to say.
2006-05-09, 09:36   #6
hhh

Jun 2005

373 Posts

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.

2006-05-09, 12:37   #7
T.Rex

Feb 2004
France

39F16 Posts

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"))
}

2006-05-09, 12:40   #8
T.Rex

Feb 2004
France

32×103 Posts

Quote:
 Originally Posted by Uncwilly ... I would love to see what R. Silverman has to say.
Mee too.
T.

 2006-05-09, 16:20 #9 ewmayer ∂2ω=0     Sep 2002 República de California 23·3·487 Posts 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
2006-05-09, 16:26   #10
bearnol

Sep 2005

12710 Posts

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

 2006-05-09, 16:41 #11 bearnol     Sep 2005 127 Posts btw, the LL test is (very close to) a theoretical maximum of efficiency for any primality test... J

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 primus Miscellaneous Math 1 2014-10-12 09:25 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15 shawn Miscellaneous Math 5 2007-07-17 17:55 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 12:29.

Sun Jan 23 12:29:12 UTC 2022 up 184 days, 6:58, 0 users, load averages: 0.87, 1.06, 1.16