Conjectured compositeness tests for $N=k \cdot 2^n \pm c$ How to prove that these conjectures are true ?
Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ~\text{are nonnegative integers} .$
Conjecture 1 : $ \text{Let} ~N=k\cdot 2^n-c ~\text{such that}~ n>2c ,  k>0 , c>0 ~\text{and}~ c\equiv 3,5 \pmod{8}$
$$\text{Let}~ S_i=P_2(S_{i-1})~ \text{with}~ S_0=P_k(6) , ~\text{thus} $$
$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv -P_{\lfloor c/2 \rfloor}(6) \pmod{N}$$
Searching for counterexample (Pari GP) :
CEk2c(k,c,g)=
{
for(n=2*c+1,g,a=6;
N=k*2^n-c;
my(s=Mod(2*polchebyshev(k,1,a/2),N)); 
for(i=1,n-1, s=s^2-2); 
if(!(s==N-2*polchebyshev(floor(c/2),1,a/2)) && isprime(N),print(n)))
}

Conjecture 2 : $ \text{Let} ~N=k\cdot 2^n-c ~\text{such that}~ n>2c ,  k>0 , c>0 ~\text{and}~ c\equiv 1,7 \pmod{8}$
$$\text{Let}~ S_i=P_2(S_{i-1})~ \text{with}~ S_0=P_k(6) , ~\text{thus} $$
$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv P_{\lceil c/2 \rceil}(6) \pmod{N}$$
Searching for counterexample (Pari GP) :
CEk2c(k,c,g)=
{
for(n=2*c+1,g,a=6;
N=k*2^n-c;
my(s=Mod(2*polchebyshev(k,1,a/2),N)); 
for(i=1,n-1, s=s^2-2); 
if(!(s==2*polchebyshev(ceil(c/2),1,a/2)) && isprime(N),print(n)))
}

Conjecture 3 : $ \text{Let} ~N=k\cdot 2^n+c ~\text{such that}~ n>2c ,  k>0 , c>0 ~\text{and}~ c\equiv 3,5 \pmod{8}$
$$\text{Let}~ S_i=P_2(S_{i-1})~ \text{with}~ S_0=P_k(6) , ~\text{thus} $$
$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv -P_{\lceil c/2 \rceil}(6) \pmod{N}$$
Searching for counterexample (Pari GP) :
CEk2c(k,c,g)=
{
for(n=2*c+1,g,a=6;
N=k*2^n+c;
my(s=Mod(2*polchebyshev(k,1,a/2),N)); 
for(i=1,n-1, s=s^2-2); 
if(!(s==N-2*polchebyshev(ceil(c/2),1,a/2)) && isprime(N),print(n)))
}

Conjecture 4 : $ \text{Let} ~N=k\cdot 2^n+c ~\text{such that}~ n>2c ,  k>0 , c>0 ~\text{and}~ c\equiv 1,7 \pmod{8}$
$$\text{Let}~ S_i=P_2(S_{i-1})~ \text{with}~ S_0=P_k(6) , ~\text{thus} $$
$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv P_{\lfloor c/2 \rfloor}(6) \pmod{N}$$
Searching for counterexample (Pari GP) :
CEk2c(k,c,g)=
{
for(n=2*c+1,g,a=6;
N=k*2^n+c;
my(s=Mod(2*polchebyshev(k,1,a/2),N)); 
for(i=1,n-1, s=s^2-2); 
if(!(s==2*polchebyshev(floor(c/2),1,a/2)) && isprime(N),print(n)))
}

Any hint is appreciated .
 A: First thing I would do is simplify $P_2(x)$
$$P_2(x)=\dfrac{(x-\sqrt{x^2-4})^2+(x+\sqrt{x^2-4})^2}{4}=\dfrac{x^2-2x\sqrt{x^2-4}+x^2-4+x^2+2\sqrt{x^2-4}+x^2-4}{4}=\dfrac{4x^2-8}{4}=x^2-2$$
How did you come up with these conjectures? And why do you think they would work? Because,if we know that, it's way easier to prove them.
A: Your $P_m(x)$ is exactly the $C_n(x)$ that appears in H.C. Williams' book "Edouard Lucas and Primality Testing" page 77 and 78. But $C_n(x)$ is defined in a much simpler way: $C_0(x)=2$, $C_1(x)=x$, $C_{i+1}(x)= xC_i(x) - C_{i-1}(x)$.
If we consider the digraph under $x^2-2 \pmod N$, I think I remember that cycles are connected when using $C_3(x)$ (I mean to say that you jump from a cycle to another cycle by applying $C_3$ to a member of a cycle), to be checked.
A: About conjecture 2, with $k=1$ and $c=1$, $N=2^n-1$ is a Mersenne number (with q prime).
Then: $S_0=P_1(6)=6$ and the final test is: $S_{n-1} \equiv P_1(6)=6$ .
So, your conjecture is equivalent to say that N is prime iff we run a complete $n-1$ cycle of the digraph under $x^2-2 \pmod N$ starting with seed $S_0=6$ (and returning back to 6 after $n-1$ iterations). And this test is very close to a primality test conjecture I wrote for Mersenne numbers, where I used $S_0=3^2+\frac{1}{3^2}$ and also $q-1$ iterations. See: http://tony.reix.free.fr/Mersenne/ConjectureLLTCyclesMersenne.pdf .
Please note that I added another condition : $\prod_{1}^{q-1}S_i\equiv1 \pmod N$. This condition also holds for you. Maybe this additional condition may help for proving the converse (if property(N) then N is prime).
Now, for conjecture 1, with $k=1$ and $c=3$, we have : $N=2^n-3$, and $S_0=P_1(6)=6$ and the final test is $S_{n-1}\equiv-P_1(6)=-6$ . However, if we say that $S_O=P_2(6)=34$ and the final test is $S_{n-1} \equiv S_0$, that changes nothing to your test but, again, the test consists to run through a complete cycle of length $n-1$, starting from 34 and ending in 34.
So, I'm asking myself if all your tests can be transformed in:
1) reach the beginning of a cycle: $S_0$ ;
2) run $n-1$ iterations ;
3) return back to the seed $S_0$.
If yes, that would create a link with digraph theory, where there are binary trees and cycles. Running from a universal initial value ($4$ for LLT for Mersenne numbers) to $0$ means go through a branch of the big binary tree. Running from a universal initial value ($6$ in your case) back to it means go through a cycle of the digraph.
A: This is not an answer, but this would not enter a comment.
Here is a PARI/gp program that implements a unic formula that manages all 4 conjectures, showing that they are related and can be generalized into only one, showing that it looks to be a deep property.
I've found no counter-example with the two verification loops provided after.
You have found something deep, I think. However, it needs a proof now ! ;)
CEk2c(k,c,g)=
{
a=6;
if(c>0,s=1,s=-1;c=-c);
for(n=2*c+1,g,
N=k*2^n+s*c;
e=c%4;if(e!=1,e=-1);
d=((c-e)%8)/4;
A=(-1)^d;
B=(c-A*s)/2;
s0=Mod(2*polchebyshev(k,1,a/2),N);
sn=Mod(A*2*polchebyshev(B,1,a/2),N);
my(s=s0);
for(i=1,n-1,s=Mod(s^2-2,N));
if(s!=sn && isprime(N),print("k: ",k," c: ",c," n: ",n))
)
}

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100)))
for(k=1,100,for(c=0,50,CEk2c(k,-(2*c+1),100)))

New conjecture summarizing the 4 conjectures:
$$\text{Let } ~N=k\cdot 2^n+ s \cdot c ~\text{ such that: }$$
$$ n>2c ,  k>0 , c>0 ~\text{ and }~ s = \pm 1 ~\text{ and }~ c \equiv 4 \cdot d ~ \pm 1 \pmod 8 ~\text{ and }~ d=0,1$$
$$\text{Let }~ S_i \equiv P_2(S_{i-1}) \pmod{N} ~ \text{ with } ~ S_0=P_k(6) ~ \text{ , thus: }$$
$$\text{If } ~ N ~\text{ is prime then }~ S_{n-1} \equiv {(-1)}^d \cdot P_{(c - {(-1)^d \cdot s})/2} ~ (6) \pmod{N}$$
A: Now that the conjecture has been proven, by a nice proof, I'm interested in the converse: if the number has the property, is it a prime ? Or: are there (many) pseudoprimes for the test ?
With program below (which requires that $S_i \ne  S_{n-1} ~ \text{, for}~  i<n-1$, and with some search, I've found that, for $N= k*2^n + c ~ , c ~\text{odd} > 0$, it looks that there are pseudoprimes ONLY when $c \equiv 1 \pmod{8}$. For now, I've only found the following values for c : 1, 17, 25, 33, 41, 57, 73, 81, 89, 105, 129, 137, 145 .
Examples: 1*2^3+1 , 97*2^48+17 , 54*2^220+25 , 64*2^119+33 , 419*2^117+41 , 343*2^291+57 , 471*2^393+73 , 467*2^259+81 , 419*2^267+89 , 307*2^319+105 , 256*2^319+129 , 136*2^396+137 , 171*2^379+145 
(k should be set as odd in CEk2c(), for sure.)
CEk2c(k,c,g)=
{
a=6;
h=a/2;
if(c>0,s=1,s=-1;c*=-1);
for(n=c<<1+1,g,
N=k<<n+s*c;
e=c%4;
if(e==1,,e=-1);
d=((c-e)%8)/4;
f=((-1)^d);
B=f*s;
A=(c-B)/2;
s0=Mod(polchebyshev(k,1,h)<<1,N);
sn=Mod(f*polchebyshev(A,1,h)<<1,N);
my(s=s0);
z=0;
forstep(i=n,3,-1,s=sqr(s)-2;if(s==sn,z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn, if(!isprime(N), print(k,"*2^",n,"+",c)))
);
}

for(k=1,100,for(c=0,200,CEk2c(k,2*c+1,400)))

