number of roots of a polynomial in finite field

Question

Is there any way to determine the number of roots of a polynomial in finite field, more specifically, $GF(2^q)$, without actually solving the equation and find all roots?

Answer 1

Yes. This is possible, because the field is finite.

If $p(x)$ is your polynomial, all you need to do is to calculate the greatest common divisor $$ d(x):=\gcd(p(x),x^{2^q}-x). $$ The number of zeros of $p(x)$ in the field $GF(2^q)$ is then equal to the degree of $d(x)$. This is because the polynomial $x^{2^q}-x$ has all the elements of $GF(2^q)$ as simple zeros.

Observe that even though that exponent $2^q$ may be quite large, the computation of the gcd using Euclid's algorithm is still reasonably fast as long as the degree of $p(x)$ is not too high. This is because calculating the remainder of $x^{2^q}$ when divided by $p(x)$ is really just repeated squaring. And this is then the only step dealing with high degree polynomials.

Answer 2

@Jyrki: After read some material on the repeated squaring, I think what you were referring was as:

$x^2~mod ~p(x) = (x ~mod ~p(x))^2 ~mod ~p(x)$

$x^4 ~mod ~p(x) = (x^2 ~mod ~p(x))^2 ~mod ~p(x)$

...

Do you think this is the most efficient way to calculate

$x^{2^q} ~mod ~p(x)$?

Seems to me that most complexity lies in squaring the polynomials.

Another point is that I think for my application, it is enough to only calculate

$x^{2^q} -x~mod ~p(x)$

if the above term is not zero, that means $p(x)$ definitely does not have enough number of roots (which would be equal to its degree if it is a valid polynomial). So the expensive Chien search can be skipped for this one. Do you agree with me?