Algoritmo para representar un polinomio como una composición de polinomios de grado inferior

Question

Dejemos que $q$ sea un primo grande y $e$ un número entero tal que $GCD(e,q-1)=1$ . Dejemos que $p(x)$ sea un polinomio de grado $e^n$ con coeficientes en $\mathbb Z_q$ tal que existe una progresión de polinomios (la "composición")

• $p_i(x) = a_i(p_{i-1}(x))^e+b_i$ , $a_i, b_i \ne 0$ con
• $p_0(x) = x$ y
• $p(x) = p_n(x)$

Dado $q$ y $p(x)$ ¿Cómo puedo encontrar una composición de este tipo?

Nota: La condición $GCD(e,q-1)$ implica que cada $p_i(x)$ es una permutación sobre $\mathbb Z_q$ . Lo pregunto porque estoy tratando de encontrar un algoritmo eficiente para encontrar las raíces de $p(x)-c$ para cualquier $c$ . Es posible que mi enfoque sea inadecuado, pero desgraciadamente significa que no me ayudan las respuestas que presuponen que ya soy capaz de encontrar esas raíces. No lo soy, eso es lo que intento averiguar.

Answer 1

Como en mi comentario, asumiré que $p(x)$ y todos $p_i(x)$ son mónicas. También supondré que $\gcd(e,q)=1$ . Todas estas hipótesis se pueden eliminar fácilmente. Para que el problema no sea trivial, supongamos que $e>1$ . La única cuestión es determinar $b_n$ Si eso se puede hacer, entonces $p_{n-1}(x)$ es la única mónica $e$ -raíz de $p(x)-b_n$ y se puede determinar de forma similar $b_{n-1},p_{n-2},b_{n-2},...,p_1$ . Una forma de determinar $b_n$ es calcular la resultante con respecto a $y$ de $p'(y)$ y $p(y)-x$ . Esta resultante será un polinomio en $x$ de grado $2e^n-2$ que tiene $b_n$ como una raíz de multiplicidad al menos $e^n-e^{n-1}$ Así que $b_n$ puede leerse a partir de la resultante.

Otro enfoque consiste en calcular los coeficientes de $x^{-1},x^{-2},...,x^{-e^{n-1}}$ en la expansión del $e$ -raíz de $p(x)/x^{e^n}$ en $\mathbb{Z}_q[[1/x]]$ (que se hace único al requerir un término constante $1$ ). Si $r(x)$ es el único polinomio mónico de grado $e^{n-1}$ tal que $$ \frac{p(x)}{x^{e^n}} - \Bigl(\frac{r(x)}{x^{e^{n-1}}}\Bigr)^e$$ está en $x^{-e^{n-1}-1}\mathbb{Z}_q[[1/x]]$ entonces $r(x)$ es también el único polinomio mónico de grado $e^{n-1}$ tal que $p(x)-r(x)^e$ tiene un grado inferior a $e^n-e^{n-1}$ . Desde $p(x)-p_{n-1}(x)^e$ es constante debemos tener $p_{n-1}(x)=r(x)$ y luego $b_n=p(x)-r(x)^e$ se puede determinar.