4
$\begingroup$

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?

1 Answers 1

3

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$.