Algorithm for representing a polynomial as a composition of lower degree polynomials Let $q$ be a large prime and $e$ an integer such that $GCD(e,q-1)=1$. Let $p(x)$ be a polynomial of degree $e^n$ with coefficients in $\mathbb Z_q$ such that there exists a progression of polynomials (the "composition")


*

*$p_i(x) = a_i(p_{i-1}(x))^e+b_i$, $a_i, b_i \ne 0$ with 

*$p_0(x) = x$ and 

*$p(x) = p_n(x)$


Given $q$ and $p(x)$, how do I find any such composition?
Note: The condition $GCD(e,q-1)$ implies that each $p_i(x)$ is a permutation over $\mathbb Z_q$. I ask because I am trying to find an efficient algorithm for finding the roots of $p(x)-c$ for any $c$. It is possible my approach is inadequate, but unfortunately it means I am not helped by answers that presuppose that I am already able to find such roots. I am not, that's what I am trying to figure out.
 A: As in my comment, I will assume that $p(x)$ and all $p_i(x)$ are monic.  I will also assume that $\gcd(e,q)=1$.  All of these hypotheses can be removed easily.  To make the problem nontrivial, assume that $e>1$.  The only issue is to determine $b_n$; if that can be done, then $p_{n-1}(x)$ is the unique monic $e$-th root of $p(x)-b_n$, and one can similarly determine $b_{n-1},p_{n-2},b_{n-2},...,p_1$.  One way to determine $b_n$ is to compute the resultant with respect to $y$ of $p'(y)$ and $p(y)-x$. This resultant will be a polynomial in $x$ of degree $2e^n-2$ which has $b_n$ as a root of multiplicity at least $e^n-e^{n-1}$, so $b_n$ can be read off from the resultant.
Another approach is to compute the coefficients of $x^{-1},x^{-2},...,x^{-e^{n-1}}$ in the expansion of the $e$-th root of $p(x)/x^{e^n}$ in $\mathbb{Z}_q[[1/x]]$ (made to be unique by requiring constant term $1$).  If $r(x)$ is the unique monic polynomial of degree $e^{n-1}$ such that 
$$
\frac{p(x)}{x^{e^n}} - \Bigl(\frac{r(x)}{x^{e^{n-1}}}\Bigr)^e$$ is in $x^{-e^{n-1}-1}\mathbb{Z}_q[[1/x]]$, then $r(x)$ is also the unique monic polynomial of degree $e^{n-1}$ such that $p(x)-r(x)^e$ has degree less than $e^n-e^{n-1}$. Since $p(x)-p_{n-1}(x)^e$ is constant we must have $p_{n-1}(x)=r(x)$, and then $b_n=p(x)-r(x)^e$ can be determined.
