Lucas Probable Primes

Lucas numbers can be defined as $L_0$ $=$ $2$, $L_1$ $=$ $1$ and $L_n$ $=$ $L_{n-2}$ $+$ $L_{n-1}$. This is equivalent to considering the trace defined as the sum of the diagonal elements of the matrix $ \left( \begin{array}{cc} 1&1\\ 1&0 \end{array}\right)^n. $

The Lucas characteristic equation is $x^2$ $-$ $Px$ $+$ $Q$ $=$ $0$. From this we can calculate powers of $x$ using the recursion $x^2$ $=$ $Px$ $-$ $Q$. For example $x^3$ = $x\times x^2$ $=$ $x\times (Px-Q)$ $=$ $Px^2$ $-$ $Qx$ $=$ $P\times (Px - Q)$ $-$ $Qx$ $=$ $P^2x$ $-$ $PQ$ $-$ $Qx$ $=$ $(P^2-Q)x$ $-$ $PQ$. Alternatively we can use the trace of the matrix: $ \left( \begin{array}{cc} P&-Q\\ 1&0 \end{array}\right)^n. $

The strong case happens when the Jacobi symbol of $P^2$ $-$ $4Q$ over $n$ is $-1$ and we can guarantee that $x^{n+1}$ $\equiv$ $Q$ $\pmod{n, x^2-Px+Q}$ for prime $n$. Of course there are Lucas pseudoprimes for which this holds.