4
$\begingroup$

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

$\endgroup$
  • 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 Voloch Nov 11 '10 at 13:23
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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