Hyperelliptic curve order How to compute order of a hyperelliptic curve ($y^2=f(x)$, $deg(f)=2 \cdot g+1$, $g=4$), over $F_p$ for small $p$ ($p$ prime)? Are there any efficient algorithms to do so? Is it possible with Pari/Magma/Sage? Are there any efficient algorithms for solving the discrete logarithm problem for such curves?
 A: For these curves, we always have one point at infinity: (0:1:0).
The simplest way to count the other points is to plug in all possible $x$-values, and see if $f(x)$ is a square in $F_p$.  If it's a nonzero square, we have two points: $(x, \pm \sqrt{f(x)})$.  If $f(x)=0$, we have one point: $(x,0)$.  And if it's not a square, we have no points for that $x$-value.
So, if $N_p$ is the order of the curve, we have $1 \leq N_p \leq 2p+1$ and 
$$N_p = 1 + \sum_{x=0}^{p-1}\left(\left(\frac{f(x)}{p}\right) + 1\right)$$
where $\left(\frac{a}{p}\right)$ is the Legendre symbol.
We can rearrange this to 
$$N_p = p+1 + \sum_{x \in F_p} (f(x))^{\frac{p-1}{2}}$$
and then take the sum over each term in $(f(x))^{\frac{p-1}{2}}$ separately.
Since $\sum_{x \in F_p} x^n$ is 0 unless $p-1|n$ and $n \neq 0$, we only need to know a few coefficients of $(f(x))^{\frac{p-1}{2}}$.  
Let $a_{p,i}$ be the coefficient of $x^{i(p-1)}$ in $f(x)^{(p-1)/2}$ for $i=1, \ldots, g$ (these are the only terms contributing to our sum); and let $a_p = a_{p,1} + \ldots + a_{p,g}$.  
Then $N_p \equiv p+1-a_p \pmod{p}$. 
Since $|N_p - (p+1)| \leq 2g\sqrt{p}$ (by the Weil conjectures) if the curve has good reduction over $F_p$, we can choose $p$ large enough that $a_p$ completely determines $N_p$.
I know there are other methods for counting points, but this one is very simple, and is the fastest method if $f(x)$ is a sparse polynomial (most coefficients are 0).  Note that you don't have to compute all of $(f(x))^{\frac{p-1}{2}}$ to find the coefficients $a_{p,i}$, and you only need to compute them modulo $p$.
