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 [B]LLT Cycles[/B] instead of the [B]LLT Tree[/B] as does the Lucas-Lehmer-Test :

[tex]\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 \ .[/tex]

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 [tex]\frac{q-1}{2}[/tex], I think it is possible to build a test saying:

[tex]\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 } .[/tex]

[tex]\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 } .[/tex]

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

[QUOTE=T.Rex]... since it seems there are always cycles of length [tex]\frac{q-1}{2}[/tex] (under [tex]x^2-2[/tex] modulo a Mersenne prime) ...[/QUOTE] I've checked this is true for all Mersenne primes from M3 to M43.
Maybe it is easy to build a proof.
Tony

An example for q=13
 

Here is an example of what seems possible.

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

We have:

[tex]\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[/tex].

So step 1 is true.

[tex]\large f(101)=-2068[/tex]

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

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: [tex]\large S'_0= f(S_{(q-1)/2})[/tex],
- there is 1 Cycle of length (q-1)/2 which jumps to a Cycle of length (q-1)/4 (S_0=2255) again through:[tex]\large S'_0= f(S_{(q-1)/2})[/tex].
- and there are cycles that are not generated by [tex]\large 3^x+1/3^x[/tex] (does it show a problem in Shallit's theorem ?).

Tony

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 [U]think[/U] 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 [U]think[/U] 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 [B]very[/B] 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: [tex]S_0=(3^n+1/3^n) \ \pmod{Mq}[/tex]. I've found there are relationships between the factors of n and the factors of [tex]2M_{q-1}[/tex].

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

Even though this is way over my head, I would love to see what R. Silverman has to say.

[QUOTE=T.Rex]I've checked this is true for all Mersenne primes from ...
Tony[/QUOTE]

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.

[QUOTE=hhh]You are speaking about equivalences, right ?[/QUOTE] Yes
[QUOTE]Without even reading your conjecture, I wonder if you checked it for all "Mersenne composites", too ? [/QUOTE]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"))
}
[/CODE]

[QUOTE=Uncwilly]... I would love to see what R. Silverman has to say.[/QUOTE]Mee too.
T.

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 [url=http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm]Floyd's cycle-finding algorithm[/url] is still the state of the art there, but I expect a work estimate based on it would tell us quite a lot.

[QUOTE=T.Rex][tex]\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 } .[/tex]
[/QUOTE]


[QUOTE=T.Rex]q=5: S0=16 -> 6 -> 3 -> 7 -> 16[/QUOTE]

??
J

btw, the LL test is (very close to) a theoretical maximum of efficiency for any primality test...
J