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$

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

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

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

If $n \le r$ , output prime .

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 .

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 .