This question is related to my previous question.

Can you prove or disprove the following claim:

Let $N=2n+1$ where $n$ is an odd natural number greater than one , let $L_m(x)$ be the mth Lucas polynomial and let $F_m(x)$ denote an irreducible factor of degree $\varphi(m)$ of $L_m(x)$ . If there exists an integer $a$ such that $F_{n}(a) \equiv 0 \pmod{N} $ then $N$ is a prime.

You can run this test here. I have verified this claim only for small values of $N$ , that is $N \in [7,1000]$ with $a \in [1,100]$ , because my PARI/GP implementation of the test is too slow.

**EDIT**

For values of $n$ that are odd prime numbers this test runs in polynomial time (PARI/GP implementation) . List of Sophie Germain primes can be found here.