Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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 '10 at 13:23

1 Answer 1

up vote 7 down vote accepted

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

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.