Primality test similar to the AKS test

Question

Let us define polynomials $P_n^{(a)}(x)$ as follows :

$P_n^{(a)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+a}\right)^n+\left(x+\sqrt{x^2+a}\right)^n\right)$

We can define these polynomials by the recurrence relation also :

$P_0^{(a)}(x)=1$

$P_1^{(a)}(x)=x$

$P_{n+1}^{(a)}(x)=2xP_n^{(a)}(x)+aP_{n-1}^{(a)}(x)$

Note that $T_n(x)=P_n^{(-1)}(x)$ , where $T_n(x)$ is Chebyshev polynomial of the first kind .

Next , let us formulate the following claim :

Let $a \in \mathbb{Z}$ , $n \in \mathbb{N}$ , $n \ge 3$ and $\operatorname{gcd}(a,n)=1$ . Then $n$ is prime if and only if $P_n^{(a)}(x) \equiv x^n \pmod{n}$ .

You can run this test here .

The AKS test goes like this :

Input : integer $n>1$

1. If $n=a^b$ for $a \in \mathbb{N}$ and $b>1$ , output composite .

2. Find the smallest $r$ such that $\operatorname{ord}_r{n}>(\log_2n)^2$ .

3. If $1 < \operatorname{gcd}(a,n) <n$ for some $a \le r$ , output composite .

4. If $n \le r$ , output prime .

5. For $a=1$ to $ \left\lfloor \sqrt{\varphi(r)} \log_2(n) \right\rfloor$ do

   if $(x+a)^n \not\equiv x^n+a \pmod {x^r-1,n}$ , output composite .

6. Output prime .

Question . Under assumption that a claim given above is correct can we change step 5 into :

For $a=1$ to $ \left\lfloor \sqrt{\varphi(r)} \log_2(n) \right\rfloor$ do

if $P_n^{(a)}(x) \not\equiv x^n \pmod {x^r-1,n}$ , output composite .

and still have a correct algorithm ?

You can run this modified version here .

Answer 1

I'd like to point out that the claim can hardly be tested for large $n$ as it required computing polynomials of degree $n$.

At the same time, verifying it for any particular value of $x$ won't be sufficient. For example, when $a=-1$, such verification will fail to identify elements of OEIS A299799 as composite (unless one find a divisor of $n$). For $n$ from this sequence, we have $$T_n(b)\equiv b\equiv b^n\pmod{n}$$ for any integer $b$ coprime to $n$. Here, the former congruence is the property of Chebyshev pseudoprimes, while the latter one is the property of Carmichael numbers, and elements of A299799 are both.