Conjectured Primality Test for $N=8\cdot 3^n-1$ Definition
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)$ , where $m$ and $x$ are nonnegative integers .

Conjecture
Let $N=8\cdot 3^n-1$ such that $n>1$ .
Let $S_i=P_3(S_{i-1})$ with $S_0=P_{12}(4)$
thus , 
$N$ is prime iff $S_{n-1} \equiv 4 \pmod{N}$

OEIS sequence of exponents $n$ for wich $N$ is prime .
PARI/GP implementation of test
T831(n)=
{
my(s=Mod(2*polchebyshev(12,1,2),8*3^n-1)); 
for(i=1,n-1, s=s^3-3*s); 
s==4
}

You can run this code here .
Question 
Are there similar criteria for numbers of this form in the literature ?
 A: $\def\ZZ{\mathbb{Z}}$I am really baffled by people coming on this site and writing very detailed conjectures about variants of the Pepin or Lucas-Lehmer primality tests, then claiming no theoretical background. (Prior examples 1 2 3.) How did you find this conjecture if you have no idea how these tests work?
As we will see below, your test will correctly identify all cases where $8 \cdot 3^n-1$ is prime. It is quite likely it doesn't  return any false positives, but I see no theoretical reason it couldn't. This involves some somewhat deep number theory. However, if I may be a bit curmedgeonly, there are also a number of elementary manipulations you could have performed at the start to make this much more readable, and I am baffled as to why you didn't.
Let's unwind your formula. 
$$S_{n-1} = P_{4 \cdot 3^n}(4) = (2+\sqrt{3})^{4 \cdot 3^n} + (2-\sqrt{3})^{4 \cdot 3^n}$$
$$ = (2+\sqrt{3})^{4 \cdot 3^n} + (2+\sqrt{3})^{-4 \cdot 3^n} =(2+\sqrt{3})^{(N+1)/2} + (2+\sqrt{3})^{-(N+1)/2}.$$
You are testing whether or not $S_{n-1} \equiv 4 \bmod N$ or, on other words,
$$(2+\sqrt{3})^{(N+1)/2} + (2+\sqrt{3})^{-(N+1)/2} \equiv 4 \bmod N. \quad (\ast)$$
These are the elementary manipulations I spoke of. Surely, anyone who made this conjecture was aware of something like $(\ast)$ -- why not state it?
If $N$ is prime: (This section is rewritten to use some observations about roots of unity. It may therefore look a bit less motivated.) The prime $N$ is $-1 \bmod 24$, so $N^2 \equiv 1 \bmod 24$ and the finite field $\mathbb{F}_{N^2}$ contains a primitive $24$-th root of unity, call it $\eta$. We have $(\eta+\eta^{-1})^2 = 2 + \sqrt{3}$, for one of the two choices of $\sqrt{3}$ in $\mathbb{F}_N$. (Since $N \equiv -1 \bmod 12$, we have $\left( \frac{3}{N} \right) =1$.) Now, $\eta \not \in \mathbb{F}_N$. However, we compute $(\eta+\eta^{-1})^N = \eta^N + \eta^{-N} = \eta^{-1} + \eta$, since $N \equiv -1 \bmod 24$. So $\eta+\eta^{-1} \in \mathbb{F}_N$ and we deduce that $2+\sqrt{3}$ is a square in $\mathbb{F}_N$.
So $(2+\sqrt{3})^{(N-1)/2}  \equiv 1 \bmod N$ and $(2 + \sqrt{3})^{(N+1)/2} \equiv (2 + \sqrt{3}) \bmod N$. Similarly, $(2 + \sqrt{3})^{-(N+1)/2} \equiv (2+\sqrt{3})^{-1} \equiv 2 - \sqrt{3} \bmod N$ and $(\ast)$ holds.
If $N$ is not prime. Earlier, I said that I saw no way to control whether or not $(\ast)$ held when $N$ was composite. I said that there seemed to be no reason it should hold and that, furthermore, it was surely very rare, because $N$ is exponentially large, so it is unlikely for a random equality to hold modulo $N$.
Since then I had a few more ideas about the problem, which don't make it seem any easier, but clarify to me why it is so hard. To make life easier, let's assume that $N = p_1 p_2 \cdots p_j$ is square free. Of course, $(\ast)$ holds modulo $N$ if and only if it holds modulo every $p_i$. 
Let $\eta$ be a primitive $24$-th root of unity in an appropriate extension of $\mathbb{F}_{p_j}$. The following equations all take place in this extension of $\mathbb{F}_{p_j}$. It turns out that $(\ast)$ factors quite a bit:
$$(2+\sqrt{3})^{(N+1)/2} +  (2+\sqrt{3})^{-(N+1)/2}=4$$
$$ (2+\sqrt{3})^{(N+1)/2} = 2 \pm \sqrt{3}$$
$$ (\eta+\eta^{-1})^{(N+1)} = (\eta+\eta^{-1})^2 \ \mathrm{or} \ (\eta^5+\eta^{-5})^2$$
$$ (\eta+\eta^{-1})^{(N+1)/2} \in \{ \eta+\eta^{-1},\ \eta^3+\eta^{-3},\ \eta^5+\eta^{-5}, \eta^7+\eta^{-7} \}. \quad (\dagger)$$
Here is what I would like to do at this point, to follow the lines of the Lucas-Lehmer test, but cannot. 
(1) I'd like to know that $(\eta+\eta^{-1})^{(N+1)/2} = \eta+\eta^{-1}$, not one of the other options in $(\dagger)$. (This is what actually occurs in the $N$ prime case, as shown previously.) This would imply that $(\eta+\eta^{-1})^{(N-1)/2} =1 \in \mathbb{F}_{p_j}$.
(2) I'd like to know that the order of $\eta+\eta^{-1}$ was precisely $(N-1)/2$, not some divisor thereof.
(3) I'd like to thereby conclude that the multiplicative group of $\mathbb{F}_{p_j}$ was of order divisible by $(N-1)/2$, and thus $p_j \geq (N-1)/2$. This would mean that there was basically only room for one $p_j$, and we would be able to conclude primality.
Now, (1) isn't so bad, because you could directly compute in the ring $\ZZ/(N \ZZ)[\eta]/(\eta^8-\eta^4+1)$, rather than trying to disguise this ring with elementary polynomial formulas. So, while I don't see that your algorithm checks this point, it wouldn't be hard. 
And $(2) \implies (3)$ is correct.
But you have a real problem with $(2)$. This way this works in the Lucas-Lehmer test is that you are trying to prove that $2+\sqrt{3}$ has order precisely $2^p$ in the field $\mathbb{F}_{2^p-1}[\sqrt{3}] \cong \mathbb{F}_{(2^p-1)^2}$. You already know that $(2 + \sqrt{3})^{2^p}=1$. So it is enough to check that $(2 + \sqrt{3})^{2^{p-1}}=-1$, not $1$. 
In the current situation, the analogous thing would be to check that $(\eta+\eta^{-1})^{(N-1)/(2q)} \neq 1$ for every prime $q$ dividing $(N-1)/2$. But I have no idea which primes divide $q$! This seems like an huge obstacle to a  proof that $(\ast)$ implies $N$ is prime. 
To repeat: I think it may well be true that $(\ast)$ implies $N$ is prime, simply because there is no reason that $(\dagger)$ should hold once $N \neq p_j$, and the odds of $(\dagger)$ happening by accident are exponentially small. But I see no global principle implying this.
A: Your algorithm finds the following first n: 4, 10, 17, 50, 170, 184, 194, 209, 641 .
I do not have his book with me now, but I think that $x^3-3x$ does appear in Hugh C. Williams' book about the work of "Édouard Lucas", in a chapter dedicated to Chebitchef. It is also possible (but I should have to read again Lucas' books and papers) that Lucas did use such a sequence. I think I remember now that Williams said that, just before Lucas died suddenly, he was studying 3rd order functions for primality testing.
It is worth to read Williams' book about Lucas !
Your algorithm is remarkable. It makes use of technics I've used, but you are at a higher level, by using $P_m(x)$ for finding the seed (also called "universal initial value").
However, I think that it will be difficult to prove that, if N verifies the property, then it is prime. I had the same issue with a LLT-like algorithm based on cycles of the digraph under $x^2-2\pmod N$ where $N=2^q-1$ (Mersenne numbers) and for $N=\frac{2^q+1}{3}$ (Wagstaff numbers), and we were not able to prove the difficult part.
See: Conjectured new primality test for Mersenne numbers 
I hope you'll find a solution for proving your conjecture !
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)$.
HCW gives also a primality test theorem dealing with $N=A*3^n \pm 1$ , page 273, Theorem 11.3.1, and he makes use of: $S_{i+1}=S_i^3-3S_i^2+3$, with a complex definition for $S_0$ and much more conditions for the use of the primality proof.
