Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.