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} $ $

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$ .)