![]() |
![]() |
#1 |
Feb 2004
France
92710 Posts |
![]()
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 : 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 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 |
![]() |
![]() |
![]() |
#2 | |
Feb 2004
France
32·103 Posts |
![]() Quote:
Maybe it is easy to build a proof. Tony |
|
![]() |
![]() |
![]() |
#3 |
Feb 2004
France
32·103 Posts |
![]()
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 (q-1)/2 which jumps to himself (S_0=-4093) through: - there is 1 Cycle of length (q-1)/2 which jumps to a Cycle of length (q-1)/4 (S_0=2255) again through: - and there are cycles that are not generated by Tony Last fiddled with by T.Rex on 2006-04-29 at 10:08 |
![]() |
![]() |
![]() |
#4 |
Feb 2004
France
32·103 Posts |
![]()
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: 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 |
![]() |
![]() |
![]() |
#5 |
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
245638 Posts |
![]()
Even though this is way over my head, I would love to see what R. Silverman has to say.
|
![]() |
![]() |
![]() |
#6 | |
Jun 2005
373 Posts |
![]() Quote:
I confess, though, not to be able to any further help nor criticism. H. |
|
![]() |
![]() |
![]() |
#7 | ||
Feb 2004
France
16378 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^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")) } |
||
![]() |
![]() |
![]() |
#8 | |
Feb 2004
France
11100111112 Posts |
![]() Quote:
T. |
|
![]() |
![]() |
![]() |
#9 |
∂2ω=0
Sep 2002
República de California
2DD816 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 |
![]() |
![]() |
![]() |
#10 | ||
Sep 2005
127 Posts |
![]() Quote:
Quote:
J |
||
![]() |
![]() |
![]() |
#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 | |
![]() |
||||
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 |