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 about 31000 (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]

On the other hand a rough upper bound on growth can be deduced from the fact that $\log(\text{time}(n))/(n\log(n))$ seems to go down:

[![enter image description here][3]][3]

Some additional remarks.

(0)

Datapoints are only for those $n$ which have positive value of `smallestr`, i. e. such that the corresponding $r$ is smaller than any nontrivial divisor of $n$. Understandably, for other $n$ calculation is qualitatively quicker.

(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 also prove that 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$. Seemingly if $a_j$ is not divisible by $n$ then $j$ is not coprime to $n$; maybe this can help.


  [1]: https://i.sstatic.net/jFuvE.png
  [2]: https://i.sstatic.net/KGe66.png
  [3]: https://i.sstatic.net/IALRI.png