Suppose we have polynomial $G(x)$ of degree $d$, where $d$ is a large value (e.g. $10^6$). The polynomial is defined over a finite field $\mathbb{F}_p$ for a large prime number $p$ (e.g. $p$ is 200-bit).
We all know that we can factorize the polynomial and then find the roots of each polynomial of degree one. But factorization computation complexity is $O(d^2)$
Question: Is there any faster way of finding roots of the polynomial?