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.

The Art of Computer Programmingvol 2? $\endgroup$ – Zsbán Ambrus Jul 3 '13 at 8:421more comments