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

[T.Rex]

Originally Posted by ATH

Was just wondering why you used x=28 in your q=13 example and x=2 in your first general post.

Oh! Sorry. I've mixed two subjects in the same thread (never a good idea ...).
x=2 is used for the first conjecture: a Cycle of length q-1 that can be used instead of LLT (first part of post #1). x=2 is valid for all q.
x=28 is used for the second part of post #1 (rather an 'idea' than a conjecture) when q=13, where 2 cycles of length (q-1)/2 are used. I've not yet found a "universal value" of x (or a formula) that can be used for all q for this 'idea'.
Is that clearer ?
T.

[AntonVrba]

As a Mersenne prime can be written as
1+2+2^2+2^3+2^4... =(2^p-1) and as
1-2+2^2-2^3+2^4... =(2^p+1)/3

led me to investigate if for (2^p+1)/3 a test
similar to the Lucas-Lehmer Mersenne prime test
can be found and applied to prove primality.


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.

Any chance of proving this?

This has been numerically tested for the number
range p = 3 through 5807 at time of writing)
as well as spot values for the known primes
(2^p+1)/3 for p = 10501, 10691, ... 14497


A further interesting observation:
S(p-1)== 2*S(1)+1

Best regards
Anton Vrba

[bearnol]

I don't know whether this is true or not (I haven't even run any numerical examples). It sure would be nice though!! :-) On the downside, the examples given where it works _might_ just be a consequence of Fermat's Little Theorem? (just a suggestion).
However, one thing _does_ strike me:-
Anton says, additionally, that S_(p-1) = 2*S_1 + 1 - so presumably if this is the case, there would be no need to calculate all through the chain, anyway - one could just test whether 4(S_1)^2 + 3S_1 - 1 == 0
J

[AntonVrba]

Originally Posted by bearnol

However, one thing _does_ strike me:-
Anton says, additionally, that S_(p-1) = 2*S_1 + 1 - so presumably if this is the case, there would be no need to calculate all through the chain, anyway - one could just test whether 4(S_1)^2 + 3S_1 - 1 == 0
J

that is valid for all (2^p+1)/3, p an odd integer, you have to calculate through the chain

[T.Rex]

Hello Anton,

Let M=(2^p+1)/3 .

Since S0=M+(M-3)/2 , taking S0=(M-3)/2 < M would be enough.

For q=7 M=43.
S0=20 -> 11 -> 33 -> 12 -> 13 -> 38 -> 23 -> 11 .

I've drawn the DiGraph under x^2-2 modulo (2^p+1)/3 with p=7 .

There are 5 loops, 2 of length 1, 2 of length 5 and 1 of length 3

42 -> 42
0  -> 41 -> 2 -> 2
8  -> 19 -> 15 -> 8
        with: 28->8 , 35->19 , 24->15
23 -> 11 -> 33 -> 12 -> 13 -> 38 -> 23
        with: 5->23 , 20->11 , 32->33, 10->12 , 31->13 , 30->38
4  -> 14 -> 22 -> 9 -> 36 -> 4
        with: 40->7->4 , 3->7
             27->39->14 , 16->39
             26->29->22 , 17->29
             25->21->9 , 18->21
             6->34->36 , 37->34

As you can see, the DiGraph is symmetric (as it is for all prime numbers plus Carmichael numbers).

I guess that, if you use Shallit&Vasiga paper, you can build theorems explaining the number of loops.

If one find a proof, I'm very interested !

Regards,

Tony

[T.Rex]

Originally Posted by T.Rex

... There are 5 loops, 2 of length 1, 2 of length 5 and 1 of length 3

Oooops !
There are 5 loops: 2 of length 1, 1 of length 5, 1 of length 6=q-1, and 1 of length 3.
T.

[AntonVrba]

Originally Posted by T.Rex

Hello Anton,

Let M=(2^p+1)/3 .

Since S0=M+(M-3)/2 , taking S0=(M-3)/2 < M would be enough.

For q=7 M=43.
S0=20 -> 11 -> 33 -> 12 -> 13 -> 38 -> 23 -> 11 .

I've drawn the DiGraph under x^2-2 modulo (2^p+1)/3 with p=7 .

There are 5 loops, 2 of length 1, 2 of length 5 and 1 of length 3

that is why I choose (or rather found) S0=2^(p-1)-1 == (M-3)/2 (mod M) such that S(1)=S(M). I was happy with finding this value to give the consistent loop length that I forgot to do the modular reduction that you kindly pointed out.

Originally Posted by T.Rex

I guess that, if you use Shallit&Vasiga paper, you can build theorems explaining the number of loops.

If one find a proof, I'm very interested !

Thanks for this lead I did not know of S&V and as you said (but re-worded) proof of a loop is not proof of primality - I am sure S&V and others would have loved to have given the proof that if a given loop exist then primality is assured - but lets not give up


Regards
Anton

[AntonVrba]

Originally Posted by AntonVrba

that is why I choose (or rather found) S0=2^(p-1)-1 == (M-3)/2 (mod M) such that S(1)=S(M). I was happy with finding this value to give the consistent loop length that I forgot to do the modular reduction that you kindly pointed out.

That should have read ....such that S(1)==S(p)

[T.Rex]

Hi Anton,

I think your conjecture can be simplified as:

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

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

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


This is because your S0 is equal to -(Si) such that (Si)^2-2=S(1) . -(Si) is in the loop of length p-1 .

This way, your conjecture about (2^p+1)/3 numbers is very close to my one for Mersenne numbers.

I think that the LLT can be used for many kinds of primes. Not only Mersennes, Fermats, (2^p+1)/3, h.2^n+/-1 . The problem is to find a formula giving an element of a/the p-1 loop, for every p.


PARI/gp program:

FA(q)=
{
	print1(q," ");
	M=(2^q+1)/3;
	x=(M+3)/2;
	y=x;
	for(i=1,q-1,x=(x^2-2)%M);
	if(x==y, print("   P"),print("NP"))
}
forprime(q=3,1000,FA(q))

Tony

[T.Rex]

Originally Posted by AntonVrba

... I did not know of S&V ...

Look at: On the iteration of certain quadratic maps over GF(p).
Tony

[AntonVrba]

Originally Posted by T.Rex

I think your conjecture can be simplified as:

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

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

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


This is because your S0 is equal to -(Si) such that (Si)^2-2=S(1) . -(Si) is in the loop of length p-1 .

Hi Tony,

OK - one less multiplication and division.

Possibly for correctness if M stands for Mersenne then we need to use W for Wagstaff for primes of the form (2^p+1)/3 see http://en.wikipedia.org/wiki/Wagstaff_prime. Ironicaly W is an upside down M. I tend to refer to (2^p+1)/3 as conjugate Mersenne as the series expansion is 1+(-2)+(-2)^2+(-2)^3+....(-2)^(p-1) and have equal importance to Mersenne primes so I find the W rather fitting.

And thanks for adding the link - I did find the S&V paper by googling