Wow. This deserves a separate answer.

As I mentioned in a comment, motivated by the question, in a previous comment, by [Igor Rivin](https://mathoverflow.net/users/11142/igor-rivin) whether an efficient primality test can be made if the statement in the question is true, I asked a separate question about whether one could efficiently compute $T_n(x)$ modulo $x^r-1,n$. That question got a [brilliant answer](https://mathoverflow.net/a/286639/41291) by [Lucia](https://mathoverflow.net/users/38624/lucia), which enables to really demonstrate that if the statement in the question is true, one really obtains a very efficient primality test based on it.

I made this quick-and-dirty Mathematica code

    polmul[f_, g_, r_, n_] := 
    Table[Mod[Sum[f[[i]] g[[Mod[k - i + 1, r, 1]]], {i, r}], n], {k, r}]

    matmul[a_, b_, r_, n_] :=
    {{Mod[polmul[a[[1, 1]], b[[1, 1]], r, n] + polmul[a[[1, 2]], b[[2, 1]], r, n], n],
      Mod[polmul[a[[1, 1]], b[[1, 2]], r, n] + polmul[a[[1, 2]], b[[2, 2]], r, n], n]},
     {Mod[polmul[a[[2, 1]], b[[1, 1]], r, n] + polmul[a[[2, 2]], b[[2, 1]], r, n], n],
      Mod[polmul[a[[2, 1]], b[[1, 2]], r, n] + polmul[a[[2, 2]], b[[2, 2]], r, n], n]}}

    matsq[a_, r_, n_] := matmul[a, a, r, n]

    matpow[a_, k_, r_, n_] := If[k == 1, a,
     If[EvenQ[k],
      matpow[matsq[a, r, n], k/2, r, n], 
      matmul[a, matpow[matsq[a, r, n], (k - 1)/2, r, n], r, n]
     ]
    ]

    xmat[r_, n_] :=
     {{PadRight[{0, 2}, r], PadRight[{n - 1}, r]},
      {PadRight[{1}, r], ConstantArray[0, r]}}

    isprime[n_] := With[{r = smallestr[n]}, 
     If[r == 0, False,
      With[{xp = matpow[xmat[r, n], n - 1, r, n]},
       Mod[
        polmul[xp[[1, 1]], PadRight[{0, 1}, r], r, n]
         + polmul[xp[[1, 2]], PadRight[{1}, r], r, n]
       , n] === PadRight[Append[ConstantArray[0, Mod[n, r]], 1], r]
      ]
     ]
    ]

where `smallestr` is as in my other answer.

Running this on $n$ up to 100000 (all answers correct) gives the following timing:

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

Seems that it is of at worst logarithmic order (as that answer by Lucia suggests) - actually the graph of $\log(\operatorname{time}(n))/\log\log(n)$ looks like never going above zero:

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


Since the algorithm involves a recursive procedure for matrix powers, in principle one also has to check memory use. Here I must confess results are strange, maybe it is something hardware-specific.
$$
\begin{array}{r|l}
\text{amount of memory}&\text{number of cases (out of 100000)}\\
\hline
32&1407\\
64&94408\\
80&1\\
288&1\\
320&42\\
352&3\\
392&8\\
424&2316\\
456&1812\\
3452552&1
\end{array}
$$
This last amount 3452552 corresponds to $n=65969$, I have no idea why it needed so much memory. As I said this might be something machine specific - maybe some garbage collection occurred at that point or something like that. Anyway, as opposed to memory measurement timing data seem to be very accurate, I used the Mathematica command `AbsoluteTiming` and documentation says it gives actual processor time used for the calculation with quite high precision.


  [1]: https://i.sstatic.net/y5rdZ.png
  [2]: https://i.sstatic.net/sBoL2.png