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$.
Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:
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:
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.