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.

  • $\begingroup$ Really? I thought a polynomial of the p-th power has $p$ roots? If you include complex roots. $\endgroup$ Dec 16 '15 at 23:05
  • $\begingroup$ Did you mean yen's algorithm? And did you try googling it? $\endgroup$ Dec 16 '15 at 23:06
  • $\begingroup$ @SimpleArt No, I meant Yen's algorithm. Yes, I did try googling it. I probably should have elaborated a little bit more about what I meant for the $p$th root. $\endgroup$ Dec 16 '15 at 23:18
  • $\begingroup$ @MorganRodgers Added better explanation. $\endgroup$ Dec 16 '15 at 23:24
  • $\begingroup$ I don't believe you can find roots easily past 6-th roots. Sorry. $\endgroup$ Dec 16 '15 at 23:32

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.


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.