I have a question about the last part of the AKS algorithm. I already know how to compute $p \pmod{(x^r-1,n)}$ for a given polynomial $p$ but only once $p$ is in canonical form. In order for AKS to have the time complexity claimed it would be necessary to compute $(x+a)^n \pmod{(x^r,n)}$ without actually expanding $(x+a)^n$.
What's the trick for doing this? I've had a look at a few of the C++ implementations of AKS but I've generally been unable to find the relevant part of the code.