# 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.

-
Why?${}{}{}{}{}$ – Will Jagy Jul 3 '13 at 1:18
Did you want the degree to be $e^n$ (rather than $ne$)? Also, do you really want $e$ to be coprime to $q-1$, or should it be coprime to $q$? – Michael Zieve Jul 3 '13 at 2:20
There's no loss in requiring $a_i=1$ for $i<n$, since you can replace $p_2(x)$ and $p_1(x)$ by $p_2(xa_1)$ and $p_1(x)/a_1$ in order to make $p_1$ be monic, and then you can do the same thing to make $p_2,p_3,...,p_{n-1}$ be monic. So you might as well assume that $p(x)$ is monic and every $a_i=1$. – Michael Zieve Jul 3 '13 at 2:29
@MichaelZieve: You are correct that the degree will be $e^n$, but wrong about $GCD(e,q-1) = 1$. One point is to use the algorithm as a starting point for finding an algorithm for evaluating $p^{-1}(y)$, which has the same time complexity as evaluating $p(x)$ using the algorithm that is implicit in my question, i.e. no worse than $O(nlog(q)^2))$. – Henrick Hellström Jul 3 '13 at 7:23
Doesn't Knuth give an algorithm for this in The Art of Computer Programming vol 2? – Zsbán Ambrus Jul 3 '13 at 8:42

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.