<s>[INST] Primality test for specific class of Proth numbers Can you provide a proof or a counterexample for the following claim :

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)$


Let $N=k\cdot 2^n+1$ such that $n>2$ , $0< k <2^n$ and


$\begin{cases} k \equiv 1,7 \pmod{30} \text{ with } n \equiv 0 \pmod{4}  \\ k \equiv 11,23 \pmod{30} \text{ with } n \equiv 1 \pmod{4}  
\\ k \equiv 13,19 \pmod{30} \text{ with } n \equiv 2 \pmod{4} 
\\ k \equiv 17,29 \pmod{30} \text{ with } n \equiv 3 \pmod{4} \end{cases}$


Let $S_i=S_{i-1}^2-2$ with $S_0=P_k(8)$  , then $N$ is prime iff $S_{n-2} \equiv 0 \pmod N$ .

You can run this test here . A list of Proth primes sorted by coefficient $k$ can be found here . I have tested this claim for many random values of $k$ and $n$ and there were no counterexamples .
Note that for $k=1$ we have Inkeri's primality test for Fermat numbers . Reference : Tests for primality, Ann. Acad. Sci. Fenn. Ser. A I 279 (1960), 1-19.
 [/INST] Your criterion is equivalent to: 
$$(4+\sqrt{15})^{k2^{n-1}}\equiv (4+\sqrt{15})^{\frac{N-1}{2}}\equiv -1 (\bmod N \mathbb{Z}[\sqrt{15}]).$$ 
The point is that $P_m(8)=(4+\sqrt{15})^m+(4-\sqrt{15})^m$. Moreover, $S_i=(4+\sqrt{15})^{k2^i}+(4-\sqrt{15})^{k2^i}$, which one may prove by induction, using the fact that $x\mapsto x^2-2$ is semi-conjugate to $z\mapsto z^2$ under the relation $x=z+1/z$. Then the condition 
$S_{n-2} = (4+\sqrt{15})^{k2^{n-2}}+(4-\sqrt{15})^{k2^{n-2}} \equiv 0 (\bmod N)$ is equivalent to $(4+\sqrt{15})^{k2^{n-1}} \equiv -1 (\bmod N)$. 
By Fermat's little theorem (see Theorem 1 of this paper) in the quadratic number field $\mathbb{Q}[\sqrt{15}]$, for any odd prime $p$, one has
$(4+\sqrt{15})^{p-\left(\frac{15}{p}\right)}\equiv 1 (\bmod p)$, where $\left(\frac{15}{p}\right)$ is the Legendre symbol (note that $(4+\sqrt{15})(4-\sqrt{15})=1$, so $4+\sqrt{15}$ is a unit in the ring of integers $\mathbb{Z}[\sqrt{15}]$).
One also has by Theorem 2 of this paper that if $l$ is the smallest integer with $(4+\sqrt{15})^l \equiv -1 (\bmod p)$, and $(4+\sqrt{15})^K\equiv -1(\bmod p)$, then $K=lu$, where $u$ is odd. Also, the smallest integer with $(4+\sqrt{15})^e \equiv 1 (\bmod p)$ is $e=2l$. 
Now, let's show that your criterion implies that $N$ is prime. 
For contradiciton, let $p < N$ be a prime factor of $N$, then by your criterion,
$(4+\sqrt{15})^{k2^{n-1}}\equiv -1 (\bmod p)$. Then $k2^{n-1} = l u$, where $l$ is the smallest exponent $>0$ with $(4+\sqrt{15})^k\equiv -1(\bmod p)$, and $u$ is an odd integer by Theorem 2. So $l=2^{n-1}\delta$, with $\delta | k$, and hence $e \geq 2^n$. 
Theorem 1 implies that $(4+\sqrt{15})^{p\pm 1}\equiv 1(\bmod p)$. Then $p\pm 1\geq 2^n$, for every prime $p | N$. $N$ is not a square from your congruence conditions on $k$ and $n$ (check $(\bmod 15)$), so it has a factorization $pq$ with $p\geq 2^n-1$, $q\geq p+2$. But then $N = p\cdot q \geq p(p+2)\geq (2^n-1)(2^n+1)=2^n\cdot 2^n-1 > k 2^n +1 =N$ since $k < 2^n$, a contradiction. 
Going in the reverse direction (following the proof of Theorem 1 of this paper), your congruence conditions imply that $N\equiv 2,8 (\bmod 15)$ and $N\equiv 1(\bmod 8)$, hence $\left(\frac{15}{N}\right)=1, \left(\frac{2}{N}\right)=1,\left(\frac{5}{N}\right)=-1$. We have $(4+\sqrt{15})=\frac{5+\sqrt{15}}{5-\sqrt{15}}$. 
Hence $$(4+\sqrt{15})^{\frac{N-1}{2}}\equiv -1 (\bmod N)$$ if and only if 
$$(5+\sqrt{15})^{\frac{N-1}{2}}\equiv - (5-\sqrt{15})^{\frac{N-1}{2}} (\bmod N)$$ if and only if 
$$(5+\sqrt{15})^{N-1} \equiv - 10^{\frac{N-1}{2}} \equiv - 2^{\frac{N-1}{2}} 5^{\frac{N-1}{2}} \equiv - \left(\frac{2}{N}\right) \left(\frac{5}{N}\right ) \equiv 1 (\bmod N),$$
which holds by Theorem 1 and the properties of Legendre symbols. 
</s>