In a cryptography book I read that people does not known how to compute the number of points on a Jacobian of a hyperelliptic curve $C$ over a finite field $F_q$? Is this true? It seems easy to compute it knowing the eigenvalues of the Frobenius action on $H^1(C)$, which could be recovered knowing $\sharp C(F_{q^l})$ for all $l$ between $1$ and the genus of $C$.
$\begingroup$
$\endgroup$
1
asked Nov 11, 2010 at 11:01
-
3$\begingroup$ In the context of cryptography "compute" means "efficiently compute". The way you propose finding the number of points in the jacobian is correct but not efficient. Francesco's answer gives you some references to look at. $\endgroup$– Felipe VolochCommented Nov 11, 2010 at 13:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Some algorithms working in polynomial time are available, but for high values of the genus the exponent is high and the implementation is difficult. A nice survey is the paper of Gaudry and Harley
"Counting Points on Hyperelliptic Curves over Finite Fields"
Lecture Notes in Computer Science, 2000, Volume 1838/2000, 313-332,
which also contains some explicit computations on Jacobians in the case of genus $2$.
answered Nov 11, 2010 at 11:19