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

[AntonVrba]

Originally Posted by T.Rex

How did you find this starting value (M-10)/3 ???
Tony

see post 44 - just by looking at the DiGraphs at specific common points

S(0) = (M-10)/3 that is (2^p+1)/3-4 is the common number in the DiGraphs of length (p-1) for Mersenne numbers.

Originally Posted by T.Rex

About the S(0)=(9+1/9) I proposed, with: S(i+1)=S(i)^2-2 (mod M_q) as usual, there is a proof saying: if M_q is prime then S(q-1)=S(0) .
Do you have such a proof ?
Tony

No

[Robot2357]

Originally Posted by AntonVrba

Conjecture:
let p be a prime integer,
S(0) = 2^(p-1)-1 and
S(i) = S(i-1)^2-2 (mod (2^p+1)/3) ;

If S(p)== S(1) then (2^p+1)/3 is prime.

Hello,
i've found this result,and a little generalization,a few years ago.i'm not a mathematician ,so i've proved only the necessary part(the sufficient part is too difficult for me).i've thought that was already know,and so i did make only a few effort on the subject.if i'll find my old hard drive i'll post the result if you are interested.

[AntonVrba]

Originally Posted by Robot2357

Hello,
i've found this result,and a little generalization,a few years ago.i'm not a mathematician ,so i've proved only the necessary part(the sufficient part is too difficult for me).i've thought that was already know,and so i did make only a few effort on the subject.if i'll find my old hard drive i'll post the result if you are interested.

Very much interested please post

best regards
Anton

[T.Rex]

Originally Posted by AntonVrba

Oh if you were wondering about
S(0) = (M-10)/3 that is (2^p+1)/3-4
The common number in the DiGraphs of length (p-1) for Mersenne numbers.

Remember: M=2^p-1.
Let T(p,n) = 3^n + 1/3^n mod(M) .
Amongst the many possible values of n such that T(p,n) = S(0) , I've found that n=2^(p-1) could work for all p (such that M is prime).
I've checked it for p=5,7,13,17,19 . (I do not remember how to write a PARI program faster than: p=31; M=2^p-1; S0=(-10/3)%M; p2=2^(p-1); T=Mod(3^p2+1/3^p2, M) .)
That also works for: n=2^(p-1)-2 .

As an example. For p=13, the smallest n are: 454 and 456. And 455=5*7*13 (Note that: 2^(p-1) - 1=4095=3^2 * 5 * 7 * 13 =9 * 455) .

Tony

[T.Rex]

Here are some news about this Anton's conjecture:

Originally Posted by AntonVrba

Wagstaff:
refer Conjectured primality test for (2^p+1)/3

Conjecture:
Let p be a prime integer and W = (2^p+1)/3 .

S(0) = (W+3)/2 and S(i+1) = S(i)^2 - 2 (mod W) ;

W is prime iff S(p-1) == S(0) .

First, Anton tested this up to 5807 . Using PARI+GMP, I've tested up to 24971. Still checking.

Second, The seed 1/4 works also, as 3/2 from Anton.

Third, the problem of the test is the modular operation.
I do not know why, but this test also works (tested up to 5000) where the modulo is done with 2^p+1 instead of (2^p+1)/3 :

Conjecture:
Let p be a prime integer > 3 , and N = 2^p+1 and W = N/3 .

S(0) = 3/2 (or 1/4) and S(i+1) = S(i)^2 - 2 (mod N) ;

W is prime iff S(p-1) == S(0) (mod W) .

Fourth, Renaud Lifchitz already worked on these numbers, providing a "probable prime test", with a modified version of prime95.

Tony

[T.Rex]

The following LLT-like test for Mersenne numbers Mq shows that the same seed (1/2) starts a root of the tree or a node in a cycle depending on q mod 4 .
Checked up to q=9973 .

Conjecture:

Let p be a prime integer > 2 , and M = 2^q-1 .

S(0) = 1/2 and S(i+1) = S(i)^2 - 2 (mod M) ;

if M = 1 (mod 4) then: M is prime iff S(p-1) == S(0) (mod W) { Cycle }
if M = 3 (mod 4) then: M is prime iff S(p-2) == 0 (mod W) { Tree }

Tony

[m_f_h]

Originally Posted by T.Rex

Conjecture:
Let p be a prime integer > 3 , and N = 2^p+1 and W = N/3 .

S(0) = 3/2 (or 1/4) and S(i+1) = S(i)^2 - 2 (mod N) ;

W is prime iff S(p-1) == S(0) (mod W) .

Do you really mean (mod W) in the last line ?
Then it seems trivial to me that the two are equivalent.

[T.Rex]

Originally Posted by m_f_h

Do you really mean (mod W) in the last line ?
Then it seems trivial to me that the two are equivalent.

Yes, W in last line and N in the main loop. It is a part of modulus I do not master. Please explain.
T.

[m_f_h]

Originally Posted by T.Rex

Yes, W in last line and N in the main loop. It is a part of modulus I do not master. Please explain.
T.

You have x + k W = x + (k\3) N + (k % 3) W
or
(x % N ) % W = x % W = (x % W) % W
or
doing % N removes multiples of 3W, in the end you remove (all remaining) multiples of W

[T.Rex]

Hi,
Does anyone have any idea for completing my proof of my conjecture of the LLT-like test for Mersenne described at: http://tony.reix.free.fr/Mersenne/Co...esMersenne.pdf ?
Or do you know someone who is an expert in Lucas Sequences and their properties ?

Thanks,
Regards,
Tony

[T.Rex]

Originally Posted by T.Rex

Conjecture:
Let p be a prime integer > 3 , and N = 2^p+1 and W = N/3 .
S(0) = 3/2 (or 1/4) and S(i+1) = S(i)^2 - 2 (mod N) ;
W is prime iff S(p-1) == S(0) (mod W) .

I have studied (by program ...) the Digraph produced undex x^2-2 modulo a Wagstaff prime.
The conclusion is that there is no tree, like with Mersenne numbers, which could be used for building a LLT test S(p-2) == 0 (mod W).
There is no tree at all. Only Cycles.
Only a LLT test using a cycle S(p-1) == S(0) (mod W) seems possible.
The cycles seem to follow rules, but they are more complex than with Mersenne or Fermat numbers ...

Regards,
Tony