Pth Root of Polynomial Over Finite Fields for Yun's Algorithm

While I was implementing Yun's algorithm in java, I could not figure out an algorithm to find the $p$th root of a polynomial in $\mathbf{F}_p$ where the polynomial is a perfect power of $p$. How would you suggest doing this?

For example, I would want to find the square root of a polynomial in $\mathbf{F}_2$. The cubic root of a polynomial in $\mathbf{F}_3$. The quartic root of a polynomial in $\mathbf{F}_4$ ... and so forth. Does anyone know of an algorithm that can do this.

Answer

If one expands $(a+b)^p$ with the binomial theorem and then reduces mod $p$ one gets $a^p+b^p$, so inducting we have $(a+b+\cdots+c)^p\equiv a^p+b^p+\cdots+c^p$. Therefore in $\mathbb{F}_p[x]$,

$$\begin{array}{ll} \big(a_nx^n+\cdots+a_1x+a_0\big)^p & = (a_n^p)x^{pn}+\cdots+(a_1^p)x^p+(a_0^p) \\ & = a_nx^{pn}+\cdots+a_1x^p+a_0 \end{array}$$

In other words, $f(x)^p=f(x^p)$ in $\mathbb{F}_p[x]$. So to extract $f(x)$ from $f(x^p)$ all you have to do is divide the powers of $x$ by $p$. You can generalize this to $\mathbb{F}_{p^{\large e}}$, although there you have to take $p$th roots of coefficients as well (since $a\mapsto a^p$ is the identity on $\mathbb{F}_p$ but is a nontrivial automorphism on $\mathbb{F}_{p^{\large e}}$ otherwise). Note that $\sqrt[\large p^r]{a}=a^{p^{\large e-r}}$ within $\mathbb{F}_{p^{\large e}}$ if you want to go down that path.