Let $E: Q(y)=P(x)$ be an equation over a finite field $\mathbb F_p$ given any prime $p$, and any polynomials $Q(y)$ and $P(x)$ (polynomials in $y$ and $x$ respectively). Is there a general approach to computing the cardinality of the group $E \mathbb F_p$, i.e. $|E \mathbb F_p|$? Is it possible to generalize Schoof's algorithm but for higher degree polynomials?
For example, suppose we have
$E: y^4+y^3+6y^2-15y=x^4-8x^2-8x-12$ and $p=31$. We want to compute $|E \mathbb F_{31}|$. The naive approach would be to count all possible $x$ and $y$ which the eqution $E$ is true $\pmod {31}$. Checking $31^2=961$ different combinations gives $34$ possible solutions, plus the point of infinity, $|E \mathbb F_{31}| = 35$. Is there another approach, perhaps one in polynomial time? The complexity of the naive method is $O(p^2)$, and for larger primes, this becomes infeasible, especially with larger degrees. Thanks for help.