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.

  • 1
    $\begingroup$ Why?${}{}{}{}{}$ $\endgroup$ – Will Jagy Jul 3 '13 at 1:18
  • $\begingroup$ 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$? $\endgroup$ – Michael Zieve Jul 3 '13 at 2:20
  • $\begingroup$ 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$. $\endgroup$ – Michael Zieve Jul 3 '13 at 2:29
  • $\begingroup$ @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))$. $\endgroup$ – Henrick Hellström Jul 3 '13 at 7:23
  • $\begingroup$ Doesn't Knuth give an algorithm for this in The Art of Computer Programming vol 2? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.