Primality test for specific class of $N=k \cdot b^n-1$

Question

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 .

Answer 1

Not a full answer (but maybe need to fill computational details): If I am not mistaken, you are using the group law of a conic $C$ to iterate a point $p_0$ by multiplication by $b$. In fact, $S_{n-2}$ is the $x$ coordinate of the point $b^{n-2}(kp_0)$ in $C$ of order $4$, therefore, $S_{n-1}$ of a point of order $2$ and finally $S_n$ for the $x$ coordinate of the identity of $C$. These $x$ coordinates are $0,-1,1$. If you find such a sequence (which corresponds to the iteration of a fixed point $kp_0$ by multiplication by $b$) then it means that $C(\mathbb{Z}/N)\cong \mathbb{Z}/(N+1)\mathbb{Z}=\mathbb{Z}/kb^n\mathbb{Z}$. Therefore prime. Your restriction $k<2^n$ I think can be $k<b^n$. I did not have time to calculate $C$ but it should be something doable.