number of roots of a polynomial in finite field 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?
 A: 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.
A: @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?
