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


We can define these polynomials by the recurrence relation also :




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 .

  • $\begingroup$ 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. $\endgroup$ – მამუკა ჯიბლაძე Dec 2 '17 at 15:08
  • $\begingroup$ Also in step 2, if $r$ and $n$ are not coprime, cannot you just finish and declare $n$ composite? $\endgroup$ – მამუკა ჯიბლაძე Dec 2 '17 at 15:25
  • 1
    $\begingroup$ How this is different from mathoverflow.net/q/286304 ? $\endgroup$ – Max Alekseyev Dec 2 '17 at 17:03
  • $\begingroup$ @მამუკაჯიბლაძე I am just curious to know whether this modified algorithm is correct . I have fixed step 2.....thanks... $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.