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.



Algorithm for representing a polynomial as a composition of lower degree polynomials
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.


