Welcome to MathOverflow

Question

4

2

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

edited Nov 11 2010 at 11:33

Francesco Polizzi
19k●2●36●56

asked Nov 11 2010 at 11:01

Mikhail Bondarko
5,876●1●4●21

3

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. – Felipe Voloch Nov 11 2010 at 13:23

Francesco Polizzi · Accepted Answer · 2010-11-11 11:36:24Z UTC

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

A silly question: is the number of points on a Jacobian (of a curve, over a finite field) known?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.