Can you provide a proof or counterexample for the following claim ?
Let $P_a(x)=2^{-a}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{a}+\left(x+\sqrt{x^2-4}\right)^{a}\right)$ . Let $N=k \cdot b^m \pm 1$ with $b$ an even positive integer , $0<k<b^m$ and $m>2$ . Let $F_n$ be the nth Fibonacci number and let $S_i=P_b(S_{i-1})$ with $S_0=P_{kb/2}(P_{b/2}(F_n))$ , then $N$ is prime iff there exists $F_n$ for which $S_{m-2} \equiv 0 \pmod N$ .
I have tested this claim for many random values of $k$ , $b$ and $m$ but haven't found a counterexample .
This is a partial answer.
Let $N_1:=k\cdot b^m-1,N_2:=k\cdot b^m+1$.
This answer proves that
From $(1)(2)$, we can see that in order to prove that
it is sufficient to prove that
respectively where $\left(\dfrac{q}{p}\right)$ denotes the Legendre symbol.
We can get some partial results as follows :
For prime $N_1$ such that $N_1\equiv 2,3\pmod{5}$, we can take $F_4=3$ since $$\small 2S_{m-2}^2\equiv 5\cdot 5^{(N_1-1)/2}+1+4\equiv 5\cdot (-1)+1+4\equiv 0\pmod{N_1}\implies S_{m-2}\equiv 0\pmod{N_1}$$
For prime $N_1$ such that $N_2\equiv 1\pmod 3$ and $N_2\equiv 3,5,6\pmod 7$, we can take $F_5=5$ since $$2S_{m-2}^2\equiv 7\cdot 7^{(N_1-1)/2}+3\cdot 3^{(N_1-1)/2}+4\equiv 7\cdot (-1)+3\cdot 1+4\equiv 0\pmod{N_1}$$
For prime $N_1$ such that $N_1\equiv 1,3,4,5,9\pmod{11}$ and $N_1\equiv 2,7,8,11,13,14\pmod{15}$, we can take $F_7=13$ since $$2S_{m-2}^2\equiv 15\cdot 15^{(N_2-1)/2}+11\cdot 11^{(N_2-1)/2}+4\equiv 15\cdot (-1)+11\cdot 1+4\equiv 0\pmod{N_1}$$
For prime $N_1$ such that $N_1\equiv 1,4,5,6,7,9,11,16,17\pmod{19}$ and $N_1\equiv 5,7,10,11,14,15,17,19,20,21,22\pmod{23}$, we can take $F_8=21$ since $$2S_{m-2}^2\equiv 23\cdot 23^{(N_1-1)/2}+19\cdot 19^{(N_1-1)/2}+4\equiv 23\cdot (-1)+19\cdot 1+4\equiv 0\pmod{N_1}$$
For prime $N_2$ such that $N_2\equiv 2\pmod 3$ and $N_2\equiv 3,5,6\pmod 7$, we can take $F_5=5$ since $$\small 2S_{m-2}^2\equiv 7\cdot 7^{(N_2-1)/2}-3\cdot 3^{(N_2-1)/2}+4\equiv 7\cdot (-1)-3\cdot (-1)+4\equiv 0\pmod{N_2}$$
For prime $N_2$ such that $N_2\equiv 2\pmod 3$ and $N_2\equiv 2,3\pmod 5$, we can take $F_6=8$ since $N_2\equiv 1\pmod 8$ implies $2^{(N_2-1)/2}\equiv 1\pmod{N_2}$, and so$$\small 2S_{m-2}^2\equiv 10\cdot 5^{(N_2-1)/2}-6\cdot 3^{(N_2-1)/2}+4\equiv 10\cdot (-1)-6\cdot (-1)+4\equiv 0\pmod{N_2}$$
For prime $N_2$ such that $N_2\equiv 2,6,7,8,10\pmod{11}$ and $N_2\equiv 2,7,8,11,13,14\pmod{15}$, we can take $F_7=13$ since $$\small 2S_{m-2}^2\equiv 15\cdot 15^{(N_2-1)/2}-11\cdot 11^{(N_2-1)/2}+4\equiv 15\cdot (-1)-11\cdot (-1)+4\equiv 0\pmod{N_2}$$
For prime $N_2$ such that $N_2\equiv 2,3,8,10,12,13,14,15,18\pmod{19}$ and $N_2\equiv 5,7,10,11,14,15,17,19,20,21,22\pmod{23}$, we can take $F_8=21$ since $$\small 2S_{m-2}^2\equiv 23\cdot 23^{(N_2-1)/2}-19\cdot 19^{(N_2-1)/2}+4\equiv 23\cdot (-1)-19\cdot (-1)+4\equiv 0\pmod{N_2}$$
Let us prove $(1)(2)$.
Let $\alpha=\frac{F_n-\sqrt{F_n^2-4}}{2},\beta=\frac{F_n+\sqrt{F_n^2-4}}{2}$ where $\alpha\beta=1$.
First of all, let us prove by induction that $$S_i=\alpha^{kb^{i+2}/4}+\beta^{kb^{i+2}/4}\tag3$$ The base case : $$\small\begin{align}S_0&=P_{kb/2}(P_{b/2}(F_n))\\\\&=P_{kb/2}(\alpha^{b/2}+\beta^{b/2})\\\\&=2^{-kb/2}\cdot \left(\left(\alpha^{b/2}+\beta^{b/2}-\sqrt{(\alpha^{b/2}+\beta^{b/2})^2-4}\right)^{kb/2}+\left(\alpha^{b/2}+\beta^{b/2}+\sqrt{(\alpha^{b/2}+\beta^{b/2})^2-4}\right)^{kb/2}\right)\\\\&=2^{-kb/2}\cdot \left(\left(\alpha^{b/2}+\beta^{b/2}-\sqrt{(\alpha^{b/2}-\beta^{b/2})^2}\right)^{kb/2}+\left(\alpha^{b/2}+\beta^{b/2}+\sqrt{(\alpha^{b/2}-\beta^{b/2})^2}\right)^{kb/2}\right)\\\\&=2^{-kb/2}\cdot \left(\left(\alpha^{b/2}+\beta^{b/2}-(\beta^{b/2}-\alpha^{b/2})\right)^{kb/2}+\left(\alpha^{b/2}+\beta^{b/2}+(\beta^{b/2}-\alpha^{b/2})\right)^{kb/2}\right)\\\\&=2^{-kb/2}\cdot \left((2\alpha^{b/2})^{kb/2}+(2\beta^{b/2})^{kb/2}\right)\\\\&=\alpha^{kb^2/4}+\beta^{kb^2/4}\end{align}$$
Supposing that $(3)$ holds for some $i$ gives $$\begin{align}S_{i+1}&=P_b(S_i)\\\\&=2^{-b}\left(\alpha^{kb^{i+2}/4}+\beta^{kb^{i+2}/4}-\sqrt{(\alpha^{kb^{i+2}/4}+\beta^{kb^{i+2}/4})^2-4}\right)^{b}\\\\&\qquad\quad +2^{-b}\left(\alpha^{kb^{i+2}/4}+\beta^{kb^{i+2}/4}+\sqrt{(\alpha^{kb^{i+2}/4}+\beta^{kb^{i+2}/4})^2-4}\right)^{b}\\\\&=2^{-b}\left(\alpha^{kb^{i+2}/4}+\beta^{kb^{i+2}/4}-\sqrt{(\alpha^{kb^{i+2}/4}-\beta^{kb^{i+2}/4})^2}\right)^{b}\\\\&\qquad\quad +2^{-b}\left(\alpha^{kb^{i+2}/4}+\beta^{kb^{i+2}/4}+\sqrt{(\alpha^{kb^{i+2}/4}-\beta^{kb^{i+2}/4})^2}\right)^{b}\\\\&=2^{-b}\left(\alpha^{kb^{i+2}/4}+\beta^{kb^{i+2}/4}-(\beta^{kb^{i+2}/4}-\alpha^{kb^{i+2}/4})\right)^{b}\\\\&\qquad\quad +2^{-b}\left(\alpha^{kb^{i+2}/4}+\beta^{kb^{i+2}/4}+(\beta^{kb^{i+2}/4}-\alpha^{kb^{i+2}/4})\right)^{b}\\\\&=\alpha^{kb^{i+3}/4}+\beta^{kb^{i+3}/4}\qquad\blacksquare\end{align}$$
It follows from $(3)$ that $$S_{m-2}=\alpha^{kb^{m}/4}+\beta^{kb^{m}/4}=\alpha^{(N_1+1)/4}+\beta^{(N_1+1)/4}$$ $$S_{m-2}=\alpha^{kb^m/4}+\beta^{kb^m/4}=\alpha^{(N_2-1)/4}+\beta^{(N_2-1)/4}$$ where $N_1:=k\cdot b^m-1,N_2:=k\cdot b^m+1$.
By the way, since $$\begin{align}\left(\frac{F_n\pm\sqrt{F_n^2-4}}{2}\right)^{1/2}&=\left(\frac{2F_n\pm2\sqrt{F_n^2-4}}{4}\right)^{1/2}=\left(\frac{(\sqrt{F_n+2}\pm\sqrt{F_n-2})^2}{4}\right)^{1/2}\\\\&=\frac{\sqrt{F_n+2}\pm\sqrt{F_n-2}}{2}\end{align}$$ we have $$\begin{align}S_{m-2}&=\alpha^{(N_1+1)/4}+\beta^{(N_1+1)/4}\\\\&=\left(\frac{\sqrt{F_n+2}-\sqrt{F_n-2}}{2}\right)^{(N_1+1)/2}+\left(\frac{\sqrt{F_n+2}+\sqrt{F_n-2}}{2}\right)^{(N_1+1)/2}\end{align}$$ $$\begin{align}S_{m-2}&=\alpha^{(N_2-1)/4}+\beta^{(N_2-1)/4}\\\\&=\left(\frac{\sqrt{F_n+2}-\sqrt{F_n-2}}{2}\right)^{(N_2-1)/2}+\left(\frac{\sqrt{F_n+2}+\sqrt{F_n-2}}{2}\right)^{(N_2-1)/2}\end{align}$$
It follows from these that $$S_{m-2}^2=\left(\frac{\sqrt{F_n+2}-\sqrt{F_n-2}}{2}\right)^{N_1+1}+\left(\frac{\sqrt{F_n+2}+\sqrt{F_n-2}}{2}\right)^{N_1+1}+2$$ $$S_{m-2}^2=\left(\frac{\sqrt{F_n+2}-\sqrt{F_n-2}}{2}\right)^{N_2-1}+\left(\frac{\sqrt{F_n+2}+\sqrt{F_n-2}}{2}\right)^{N_2-1}+2$$
So, using the binomial theorem with $\binom{N_1}i\equiv 0\pmod{N_1}$ for $1\le i\le N_1-1$ where $N_1$ is prime, $$\begin{align}2^{N_1+1}S_{m-2}^2&=(\sqrt{F_n+2}-\sqrt{F_n-2})(\sqrt{F_n+2}-\sqrt{F_n-2})^{N_1}\\\\&\qquad\quad+(\sqrt{F_n+2} +\sqrt{F_n-2})(\sqrt{F_n+2} +\sqrt{F_n-2})^{N_1}+2^{N_1+2}\\\\&=\sqrt{F_n+2}\sum_{i=0}^{N_1}\binom{N_1}{i}(\sqrt{F_n+2})^{N_1-i}((-\sqrt{F_n-2})^i+(\sqrt{F_n-2})^i)\\\\&\qquad\quad -\sqrt{F_n-2}\sum_{i=0}^{N_1}\binom{N_1}{i}(\sqrt{F_n+2})^{N_1-i}((-\sqrt{F_n-2})^i-(\sqrt{F_n-2})^i)+2^{N_1+2}\\\\& =2\sum_{j=0}^{(N_1-1)/2}\binom{N_1}{2j}(\sqrt{F_n+2})^{N_1-2j+1}(F_n-2)^{j}\\\\&\qquad\quad +2\sum_{j=1}^{(N_1+1)/2}\binom{N_1}{2j-1}(\sqrt{F_n+2})^{N_1-(2j-1)}(F_n-2)^{j}+2^{N_1+2}\\\\&\equiv 2(F_n+2)^{(N_1+1)/2}+2(F_n-2)^{(N_1+1)/2}+2^{N_1+2}\pmod{N_1}\end{align}$$ which implies that $$2S_{m-2}^2\equiv (F_n+2)^{(N_1+1)/2}+(F_n-2)^{(N_1+1)/2}+4\pmod{N_1}\tag1$$ since $2^{N_1-1}\equiv 1\pmod{N_1}$ and $\gcd(2,N_1)=1$.
Similarly, using that $\frac{(\sqrt{F_n+2}-\sqrt{F_n-2})(\sqrt{F_n+2}+\sqrt{F_n-2})}{4}=1$, we get $$\small\begin{align}2^{N_2}S_{m-2}^2&=2(\sqrt{F_n+2}-\sqrt{F_n-2})^{N_2-1}+2(\sqrt{F_n+2}+\sqrt{F_n-2})^{N_2-1}+2^{N_2+1}\\\\&=2(\sqrt{F_n+2}-\sqrt{F_n-2})^{N_2-1}\cdot \frac{(\sqrt{F_n+2}-\sqrt{F_n-2})(\sqrt{F_n+2}+\sqrt{F_n-2})}{4}\\\\&\qquad\quad +2(\sqrt{F_n+2}+\sqrt{F_n-2})^{N_2-1}\cdot \frac{(\sqrt{F_n+2}-\sqrt{F_n-2})(\sqrt{F_n+2}+\sqrt{F_n-2})}{4}+2^{N_2+1}\\\\&=\frac{\sqrt{F_n+2}+\sqrt{F_n-2}}{2}(\sqrt{F_n+2}-\sqrt{F_n-2})^{N_2}\\\\&\qquad\quad +\frac{\sqrt{F_n+2}-\sqrt{F_n-2}}{2}(\sqrt{F_n+2}+\sqrt{F_n-2})^{N_2}+2^{N_2+1}\\\\&=\frac{\sqrt{F_n+2}}{2}\sum_{i=0}^{N_2}\binom{N_2}{i}(\sqrt{F_n+2})^{N_2-i}((-\sqrt{F_n-2})^i+(\sqrt{F_n-2})^i)\\\\&\qquad\quad +\frac{\sqrt{F_n-2}}{2}\sum_{i=0}^{N_2}\binom{N_2}{i}(\sqrt{F_n+2})^{N_2-i}((-\sqrt{F_n-2})^i-(\sqrt{F_n-2})^i)+2^{N_2+1}\\\\&=\sum_{j=0}^{(N_2-1)/2}\binom{N_2}{2j}(\sqrt{F_n+2})^{N_2-2j+1}(F_n-2)^{j}\\\\&\qquad\quad -\sum_{j=1}^{(N_2+1)/2}\binom{N_2}{2j-1}(\sqrt{F_n+2})^{N_2-(2j-1)}(F_n-2)^{j}+2^{N_2+1}\\\\&\equiv (F_n+2)^{(N_2+1)/2}-(F_n-2)^{(N_2+1)/2}+2^{N_2+1}\pmod{N_2}\end{align}$$ which implies that $$2S_{m-2}^2\equiv (F_n+2)^{(N_2+1)/2}-(F_n-2)^{(N_2+1)/2}+4\pmod{N_2}\tag2$$ since $2^{N_2}\equiv 2\pmod{N_2}$.