We study the complexity of deciding whether a given homogeneous multivariate polynomial has a nontrivial root over a finite field. Given a homogeneous algebraic circuit $C$ that computes an $n$-variate polynomial $p(x)$ of degree $d$ over a finite field $\mathbb{F}_q$, we wish to determine if there exists a nonzero $x \in \F_q^n$ with $C(x) = 0$. For constant $n$ there are known algorithms for doing this efficiently. However for linear $n$, the problem becomes \NP hard. In this paper, using interesting algebraic techniques, we show that if $d$ is prime and $n > d/2$, the problem can be solved over sufficiently large finite fields in randomized polynomial time. We complement this result by showing that relaxing any of these constraints makes the problem intractable again.