$f(x)$is any nth degree equation $n>0$, how to find roots of $f(x)$ over prime modulo.

  • 1
    $\begingroup$ Is there any difference between the quadratic equation mentioned in the title of your question and the equation of arbitrary degree $n$ in the text of the question? For quadratic polynomials and $p > 2$, the standard quadratic equation formula $$\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ works, but the roots might be in the extension field GF$(p^2)$. For the case $p = 2$, the standard quadratic formula cannot be used. Can you tell why? $\endgroup$ – Dilip Sarwate Feb 7 '16 at 16:39
  • $\begingroup$ @DilipSarwate: actually (assuming $p>2$), the standard quadratic equation, with the squareroot and the division evaluated modulo $p$ should work; no need to bring an extension field into play... $\endgroup$ – poncho Feb 7 '16 at 18:27
  • $\begingroup$ @poncho : ​ It's analogous to how "the roots might be in" $\mathbb{C}$ even if the coefficients are all in $\mathbb{R}$. ​ ​ ​ ​ $\endgroup$ – user991 Feb 7 '16 at 19:30
  • 1
    $\begingroup$ @poncho Errr no. In a finite field of characteristic $p > 2$, half the nonzero elements have square roots in the field, while the square roots of the other half lie in the extension field. For example, $1$ has square roots $\pm 1 = \{1,2\}$ in GF$(3)$ while the other nonzero element $-1 = 2$ does not have square roots in GF$(3)$, they lie in GF$(3^2)$. This is analogous to what Ricky Demer has said above; the coefficients of $x^2+1$ are in GF$(3)$ but the roots are in GF$(3^2)$ just as $x^2+1$ can be regarded as a polynomial with coefficients in $\mathbb R$ but roots in $\mathbb C$. $\endgroup$ – Dilip Sarwate Feb 7 '16 at 19:57
  • $\begingroup$ How are F and f related. Is f in the title the sames a s f in the text? What have you tried and what is your problem? Please improve your question. $\endgroup$ – miracle173 Feb 7 '16 at 19:59

Let $r_0$ be the root of $f(x)$, so $r_0$ should be in $\{0,...,p-1\}$ and $f(r_0)=0 \pmod p $. If we cant find such $r_0$, our polynomial haven't root in $F_p$.

If $p$ be small we can easily find such $r_i$(root of $f^i(x)$) and compute $f^n(x)=\frac{f^{n-1}(x)}{x-r_{n-1}}$ where $f^0(x)=f(x)$, then repeat this recursively for $n$. Founded $r_i$'s are roots of $f(x)$.

Program such as MAGMA and sage enable to factor your polynomial with large degree in seconds.

Also this theorem can help you:

Theorem: Let $F_q\in \mathcal{F_1}$ . There is a deterministic polynomial time algorithm solving any polynomial equation over $F_q$ .

For more detail about $\mathcal{F_1}$ you can see this.

| improve this answer | |
  • $\begingroup$ What if $p=3$? What is the root of $x^2+1$ that is in the set $\{0,1,2\}$? $\endgroup$ – Dilip Sarwate Feb 7 '16 at 19:59
  • $\begingroup$ @DilipSarwate, $x^2+1$ haven't root in $F_3$. But in $F_5$, $(x-2)\cdot(x-3)=x^2+1$. $\endgroup$ – Meysam Ghahramani Feb 7 '16 at 20:04
  • $\begingroup$ Yes, but the first paragraph of your answer claims that when $p$ is small, there is a root of $f(x)$ in the set $\{0,1,2, \ldots, p-1$. Or did you mean to say that $p = 3$ is far too large a value of $p$ for your method to be applicable? $\endgroup$ – Dilip Sarwate Feb 7 '16 at 20:27
  • $\begingroup$ I agreed your answer. But how to solve the equation if degree of the polynomial greater than 2? any reference is available. $\endgroup$ – venkat Feb 8 '16 at 15:47
  • $\begingroup$ @venkat, This method is correct for all degree. I edited my answer. $\endgroup$ – Meysam Ghahramani Feb 9 '16 at 5:31

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.