20060428, 13:52  #1 
Feb 2004
France
1632_{8} Posts 
Conjectured Primality Test for 2^p1, (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 LucasLehmerTest : 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 , I think it is possible to build a test saying: 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 
20060429, 09:47  #2  
Feb 2004
France
2·461 Posts 
Quote:
Maybe it is easy to build a proof. Tony 

20060429, 10:05  #3 
Feb 2004
France
2×461 Posts 
An example for q=13
Here is an example of what seems possible.
Let: . We have: . So step 1 is true. So step 2 is true, too. But, for q=13 :  there is 1 Cycle of length (q1)/2 which jumps to himself (S_0=4093) through: ,  there is 1 Cycle of length (q1)/2 which jumps to a Cycle of length (q1)/4 (S_0=2255) again through:.  and there are cycles that are not generated by (does it show a problem in Shallit's theorem ?). Tony Last fiddled with by T.Rex on 20060429 at 10:08 
20060508, 14:46  #4 
Feb 2004
France
2·461 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 LucasLehmerTest is based on the Tree built by llt : x > x^22 mod Mq. We usually start with S0=4, but there are plenty other starting values. Since we cannot divide the q1 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 q1 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 LLTCycles of length q1 can be used the same way we are using the LLTTree. Now, there are not only Cycles of length q1 but there are also Cycles of length (q1)/2. If the Mersenne number is not prime, it is possible that some Cycles of length (q1)/2 still exist. But, I think that it is not possible to go through 2 "connected" Cycles of length (q1)/2 when Mq is not prime. "Connected" here means that we jump from a Cycle of length (q1)/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^33*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 (q1) iterations. llt(llth(x)) = llth(llt(x))} So, if the Mersenne number is prime, succeeding to go through 2 connected Cycles of length (q1)/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 (q1)/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 (q1)/2 that are connected by the llth function. The problem is to find a starting point: . I've found there are relationships between the factors of n and the factors of . Also, there exist proofs of LLTlike tests for Fermat numbers. And the paper of Shallit and Vasiga show that the DiGraph under x^22 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 (q1)/d , it should be possible to divide the CycleLLT 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 LLTCycles. Even if the probability to succeed is very small, I think it is worth to increase our knowledge about the properties of LLTCycles. 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 
20060509, 05:09  #5 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2·5,059 Posts 
Even though this is way over my head, I would love to see what R. Silverman has to say.

20060509, 09:36  #6  
Jun 2005
565_{8} Posts 
Quote:
I confess, though, not to be able to any further help nor criticism. H. 

20060509, 12:37  #7  
Feb 2004
France
2×461 Posts 
Quote:
Quote:
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^q1; S0=(3^2+1/3^2)%M; print(S0); S=S0; for(i=1, q1, S=(S^22)%M; print(S)); if(S==S0, print("Prime !"), print("Composite")) } 

20060509, 12:40  #8  
Feb 2004
France
2×461 Posts 
Quote:
T. 

20060509, 16:20  #9 
∂^{2}ω=0
Sep 2002
República de California
26634_{8} Posts 
Hi, Tony:
I think it would be very useful for you to do an asymptoticwork (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 cyclefinding 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 20060509 at 16:22 
20060509, 16:26  #10  
Sep 2005
127 Posts 
Quote:
Quote:
J 

20060509, 16:41  #11 
Sep 2005
127 Posts 
btw, the LL test is (very close to) a theoretical maximum of efficiency for any primality test...
J 
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  20180311 23:20 
Conjectured Primality Test for Specific Class of Mersenne Numbers  primus  Miscellaneous Math  1  20141012 09:25 
Conjectured Primality Test for Specific Class of k6^n1  primus  Computer Science & Computational Number Theory  16  20140815 01:15 
there is another way to test the primality of a no  shawn  Miscellaneous Math  5  20070717 17:55 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 