# How to find roots of equation $f(x)=0 \pmod p$, where $p$ is prime number?

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

• 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? – Dilip Sarwate Feb 7 '16 at 16:39
• @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... – poncho Feb 7 '16 at 18:27
• @poncho : ​ It's analogous to how "the roots might be in" $\mathbb{C}$ even if the coefficients are all in $\mathbb{R}$. ​ ​ ​ ​ – user991 Feb 7 '16 at 19:30
• @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$. – Dilip Sarwate Feb 7 '16 at 19:57
• 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. – miracle173 Feb 7 '16 at 19:59

## 1 Answer

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.

• What if $p=3$? What is the root of $x^2+1$ that is in the set $\{0,1,2\}$? – Dilip Sarwate Feb 7 '16 at 19:59
• @DilipSarwate, $x^2+1$ haven't root in $F_3$. But in $F_5$, $(x-2)\cdot(x-3)=x^2+1$. – Meysam Ghahramani Feb 7 '16 at 20:04
• 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? – Dilip Sarwate Feb 7 '16 at 20:27
• I agreed your answer. But how to solve the equation if degree of the polynomial greater than 2? any reference is available. – venkat Feb 8 '16 at 15:47
• @venkat, This method is correct for all degree. I edited my answer. – Meysam Ghahramani Feb 9 '16 at 5:31