Computational efficiency of character sums for counting finite field points on a curve It is a well-known fact that one can compute the number of points on a curve over a finite field via character sums. For instance,
$$5+1+\sum_{x\in GF(5)}\varphi(x(1-x)(1-2x))$$
counts the number of points in $GF(5)$ on the curve $y^2=x(1-x)(1-2x)$, where $\varphi$ is the Legendre symbol.
In large scale, how efficient these sorts of computations are versus simply checking all possible points?
 A: For numbers as small as $5$, it should make virtually no difference. Let me interpret this question as asking for a method to do it over any finite field. I will also restrict to the case of $\mathbb F_p$ for $p$ a prime, rather than a prime power.
Counting points in the most obvious fashion is terribly inefficient - it will require you to check $p^2$ points (or roughly as much if you use some shortcuts, like there being at most two $y$ for each $x$).
Finding this value using character sums amounts to computing the $p$ values of the Legendre symbol. These computations can be made very efficient using quadratic reciprocity (for Jacobi symbol, to avoid the need to factorize). I will refer you to an example on Wikipedia. In general the computations should take $O(\log p)$ arithmetic operations, which gives the efficiency of the algorithm on the order of $O(p\log p)$ arithmetic operations, much  better than $p^2$ we had above.
Of course, there are more efficient methods available - in the case of elliptic curves in particular, one of the most efficient methods is Schoof's algorithm, which exploits the niceties of arithmetic of elliptic curves in various ways and runs in polylogarithmic time. Further improvements to it are also available.
That said, the method of character sums has its advantages - in the same way you can count points on hyperelliptic curves, and with some extra work you can generalize it to some other curves and varieties, using sums of characters of higher order. One should also mention that character sums are a powerful theoretical tool - for instance, Weil has famously used them to verify his conjectures on zeta functions for "Fermat varieties", given by equations of the form $a_0x_0^{n_0}+\dots+a_kx_k^{n_k}=b$. You can find an exposition of that in Ireland-Rosen's book, or in Weil's original article.
