This question is successor of Compositeness test for specific class of $N=k \cdot b^n-1$ .

Can you provide a proof or a counterexample to 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 b^n-1$ such that $k>0$ , $3 \not\mid k$ , $k<2^n$ , $b>0$ , $b$ is even number, $3 \not\mid b$ and $n > 2$ . Let $S_i=P_b(S_{i-1})$ with $S_0=P_{kb/2}(P_{b/2}(4))$ , then if $S_{n-2} \equiv 0\pmod{N}$ then $N$ is a prime .

You can run this test here .

I have verified this claim for many random values of $k$ , $b$ and $n$ .

**P.S.**

A command line program that implements this test can be found here .