Context :
I'm interested by numbers, prime and composite numbers and their properties, perfect and hyperperfect numbers and primality testing.
Recently, I discovered the Lucas-Lehmer primality test for Mersenne numbers $2^p-1$ where $p$ is a prime number, and more generally the Lucas-Lehmer-Riesel test. I think the Lucas-Lehmer test for Mersenne numbers is interesting because it a fast and deterministic test. And I'm asking if it can work for numbers like $3^n-2$ for example by changing the sequence.
Problematic :
During my research about primality testing, I read a lot of times than the Lucas-Lehmer tests works because, it part, $N+1$ can be easily factorized (in this case, small numbers and each time the same).
But I found later some primality tests that seems working even if $N-1$ or $N+1$ isn't easily factorizable for example here
So the easiness of factorization is really a necessary condition for Lucas-Lehmer or Lucas-Lehmer-Riesel primality test ? I don't understand this and why It should be like that. I think I'm missing something but I don't know what. I'm really interested by explainations for this.
So primality testing for numbers of the form $3^n-2$ shouldn't work here.
But we know already some factors of $3^n-3$, so $N-1$, here, the factor are obviously $2$ and $3$, so it's not enough to start a primality test for $3^n-2$, even probabilistic ? the Lucas-Lehmer-Riesel test works even if the $N+1$ factor are different and not the same numbers.
So what is the "threshold" of the easiness of factorization ?
A probable primality test for $3^n-2$ ?
I don't know if this probable primality test has counterexample but I tried with all $n < 10000$ and no counterexample was found.
The test looks like the Lucas-Lehmer test but with different starting value and sequence :
The test :
Let $R_n = 3^n-2$ when $n$ is a number $\ge 3$.
Let the sequence $S_i = 16 \cdot S_{i-1}^3 + 96 \cdot S_{i-1}^2 + 192 \cdot S_{i-1} + 126 $ where $S_0 = 126$.
Then $R_n$ is prime if $S_{n-2} \equiv 0 \pmod {R_n}$.
How I found the coefficients of the sequence :
Some intuition here, and I think It can help a lot for proving if the test can works or not for all $n$.
I solved this equation system :
$$\begin{cases} a \cdot (2^{3^1-2}-2)^3 + b \cdot (2^{3^1-2}-2)^2 + c \cdot (2^{3^1-2}-2) +d = (2^{3^2-2}-2) \\ a \cdot (2^{3^2-2}-2)^3 + b \cdot (2^{3^2-2}-2)^2 + c \cdot (2^{3^2-2}-2) +d = (2^{3^3-2}-2) \\ a \cdot (2^{3^3-2}-2)^3 + b \cdot (2^{3^3-2}-2)^2 + c \cdot (2^{3^3-2}-2) +d = (2^{3^4-2}-2) \\ a \cdot (2^{3^4-2}-2)^3 + b \cdot (2^{3^4-2}-2)^2 + c \cdot (2^{3^4-2}-2) +d = (2^{3^5-2}-2) \\ \end{cases}$$
This is how I found $a = 16, b = 96, c = 192, d = 126$.
If there are false positive I think these are Carmichael numbers and especially if $3^n-2$ is a Carmichael number but I found none and I don't know if it's possible.
So I have two questions is : Is this test works all the time ? and for $N-1$ and $N+1$ factorization, why this is so important ?