I have looked (a bit) at questions like finding the number of roots of $x^n =1$ over a finite field.
Now I would like to understand how to solve polynomial equations over finite fields. From what I understand the solution to the quadratic equation has the same solution formula. That means that it all comes down to finding square roots.
I know that there are formulas for solving higher degree equations, but I am wondering if some of these things look different in some way over a finite field.
I am asking for a reference that specifically deals with solving polynomial equations over finite fields. It would be nice if the reference is accessible to an advanced undergraduate student.
Best Answer
Solving polynomials in one variable over finite fields is substantially easier than solving polynomials in general. To find out if $f(x) = 0$ has any roots over $\mathbb{F}_q$ you just need to compute $\gcd(f(x), x^q - x)$ using the Euclidean algorithm, since the roots of $x^q - x$ are precisely the elements of $\mathbb{F}_q$. An elaboration of this idea leads to an efficient algorithm for not only solving but even factoring polynomials over finite fields; see Berlekamp's algorithm for details.