This is an immediate successor of Chebyshev polynomials of the first kind and primality testing and does not have any other motivation – although original motivation seems to be huge since a positive answer (if not too complicated) would give a very efficient primality test (see the linked question for details).
Recall that the Chebyshev polynomials $T_n(x)$ are defined by $T_0(x)=1$, $T_1(x)=x$ and $T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)$, and there are several explicit expressions for their coefficients. Rather than writing them down (you can find them at the Wikipedia link anyway), let me just give a couple of examples:
$$
T_{15}(x)=-15x(1-4\frac{7\cdot8}{2\cdot3}x^2+4^2\frac{6\cdot7\cdot8\cdot9}{2\cdot3\cdot4\cdot5}x^4-4^3\frac{8\cdot9\cdot10}{2\cdot3\cdot4}x^6+4^4\frac{10\cdot11}{2\cdot3}x^8-4^5\frac{12}{2}x^{10}+4^6x^{12})+4^7x^{15}
$$
$$
T_{17}(x)=17x(1-4\frac{8\cdot9}{2\cdot3}x^2+4^2\frac{7\cdot8\cdot9\cdot10}{2\cdot3\cdot4\cdot5}x^4-4^3\frac{8\cdot9\cdot10\cdot11}{2\cdot3\cdot4\cdot5}x^6+4^4\frac{10\cdot11\cdot12}{2\cdot3\cdot4}x^8-4^5\frac{12\cdot13}{2\cdot3}x^{10}+4^6\frac{14}{2}x^{12}-4^7x^{14})+4^8x^{17}
$$
It seems that $n$ is a prime if and only if all the ratios in the parentheses are integers; this is most likely well known and easy to show.
The algorithm described in the above question requires determining whether, for an odd $n$, coefficients of the remainder from dividing $T_n(x)-x^n$ by $x^r-1$, for some fairly small prime $r$ (roughly $\sim\log n$) are all divisible by $n$. In other words, denoting by $a_j$, $j=0,1,2,…$ the coefficients of $T_n(x)-x^n$, we have to find out whether the sum $s_j:=a_j+a_{j+r}+a_{j+2r}+…$ is divisible by $n$ for each $j=0,1,…,r-1$.
The question then is: given $r$ and $n$ as above ($n$ odd, $r$ a prime much smaller than $n$), is there an efficient method to find these sums $s_j$ without calculating all $a_j$? I. e., can one compute $T_n(x)$ modulo $x^r-1$ (i. e. in a ring where $x^r=1$) essentially easier than first computing the whole $T_n(x)$ and then dividing by $x^r-1$ in the ring of polynomials?
(As already said, only the question of divisibility of the result by $n$ is required; also $r$ is explicitly given (it is the smallest prime with $n$ not $\pm1$ modulo $r$). This might be easier to answer than computing the whole polynomials mod $x^r-1$.)
Best Answer
There's a rapid algorithm to compute $T_n(x)$ modulo $(n,x^r-1)$. Note that $$ \pmatrix{T_n(x) \\ T_{n-1}(x)} = \pmatrix { 2x & -1 \\ 1&0} \pmatrix{T_{n-1}(x) \\ T_{n-2}(x)} = \pmatrix { 2x & -1 \\ 1&0}^{n-1} \pmatrix{ x\\ 1}. $$ Now you can compute these matrix powers all modulo $(n, x^{r}-1)$ rapidly by repeated squaring. Clearly $O(\log n)$ multiplications (of $2\times 2$ matrices) are required, and the matrices have entries that are polynomials of degree at most $r$ and coefficients bounded by $n$. So the complexity is a polynomial in $r$ and $\log n$.