Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time?

Geometrically this means we have to sort through a positive proportion of the affine plane before being sure we have counted all solutions (modulo the complexity of addition and multiplication).

Non-example: the solutions of $x+y=0$ are counted in $O(\log p)$ time as there are $p$ solutions.

Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time?

Geometrically this means we have to sort through a positive proportion of the affine plane before being sure we have counted all solutions (modulo the complexity of addition and multiplication).

Non-example: it takes $O(\log p)$ time to count (and output) the $\mathrm{mod}\:p$ solutions of $x+y=0$ as there are $p$ solutions.

Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time?

Geometrically this means we have to sort through a positive proportion of the affine plane before being sure we have counted all solutions.

Non-example: the solutions of $x+y=0$ are counted in $O(\log p)$ time as there are $p$ solutions.

Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time?

Geometrically this means we have to sort through a positive proportion of the affine plane before being sure we have counted all solutions (modulo the complexity of addition and multiplication).

Non-example: the solutions of $x+y=0$ are counted in $O(\log p)$ time as there are $p$ solutions.