Decided to make a cw answer with an illustration of time growth.

I've tried on Mathematica this:

    isprime[n_] := 
     With[{r = smallestr[n]}, 
      If[r == 0, False, 
       PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0]
     ]
where

    smallestr[n_] := Module[{r},
      If[EvenQ[n], Return[0]];
      For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
       If[r < n \[And] Mod[n, r] == 0, Return[0]]
      ];
      r
     ]

I've run it on $n$ up to 15000 (all answers are correct); here is the graph of time needed as a function of $n$.

[![enter image description here][1]][1]

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

[![enter image description here][2]][2]

Some additional remarks.

(1)
Finding $r$ is very efficient:
$$
\begin{array}{c|c}
r&\text{smallest $n$ that requires this $r$}\\
\hline
11&29\\
13&419\\
19&1429\\
23&315589\\
29&734161\\
31&1456729
\end{array}
$$

(2)

Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.

(2')

Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To prove it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Experiments show that for composite $n$, while only few of $a$'s are not divisible by $n$, none of the $s_j$ are divisible by $n$.

  [1]: https://i.sstatic.net/PZXGv.png
  [2]: https://i.sstatic.net/0mrOT.png