I need to find all the common roots of the two polynimials $10x^{15}+9x^2+1$ and $10x^{15}+8x^2+2$ over $GF(19)$. 1 is not a root of either. The only method that I can come up with is trying brute force to just divide the polynomials by $x-r$ where $r \in GF(19)$. What am I not seeing here that I can only come up with this method? What did I not understand?
In general, is there an efficient way to find the roots of a polynomial over a finite field?
Thank you for your help.
Certainly $x=-1$ is a common root, since $f(-1)=g(-1)=0$ in $\mathbb{F}_{19}$. Suppose that $a$ is another common root. Then $x-a$ divides $f(x), g(x)$ and hence also $$f(x)-g(x)=x^2-1=(x-1)(x+1).$$ Since $1$ is not a common root, we are done. With more work we also see that $\gcd(f(x),g(x))=x+1$. Here $f(x)$ has another linear factor $x+3$, and $g(x)$ another linear factor $x+10$.
Edit: $f(x)=10x^{15}+9x^2+1$ and $g(x)=10x^{15}+8x^2+2$.