# Primality test similar to the AKS test

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) 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 .

• Could you estimate whether this gives any improvement over the AKS? Or, if your aim is different, describe it? Understand me correctly please, this is certainly very intriguing, I would just like to know what you are up to. – მამუკა ჯიბლაძე Dec 2 '17 at 15:08
• Also in step 2, if $r$ and $n$ are not coprime, cannot you just finish and declare $n$ composite? – მამუკა ჯიბლაძე Dec 2 '17 at 15:25
• How this is different from mathoverflow.net/q/286304 ? – Max Alekseyev Dec 2 '17 at 17:03
• @მამუკაჯიბლაძე I am just curious to know whether this modified algorithm is correct . I have fixed step 2.....thanks... – Peđa Terzić Dec 2 '17 at 19:07

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.