Coming from different background, for a long and uninteresting reason I was assigned to create a small program to calculate a characteristic polynomial of the Frobenius endomorphism for hyperelliptic curve based on curve equation (in finite field).
For the last couple of days I was doing a research and diving into algebraic geometry mainly using Cohen & Frey's "Handbook of Elliptic and Hyperelliptic Curve Cryptography" and Koblitz's "Algebraic Aspects of Cryptography". I've also been looking through Sage source code for hyperelliptic curves but without understanding of theory it's just a bunch of strange arithmetic and recursive links.
But not having enough education in the field, I'm really confused by abstract definitions of different ways to accomplish this. As far as I understand, the general way to construct the polynomial is by following formula (Cohen&Frey Th.14.16): $$ \chi(\phi_q)_C(T) = T^{2g} + a_1T^{2g-1} +...+a_1q^{g-1}T+q^g $$ and recurrent formula ($a_0=1$) $$ ia_i=(M_i-(q^i+1))a_0+...+(M_1-(q+1))a_{i-1}. $$
This is fine, but I don't really get how should I calculate numbers $M_i$ of points on the curve. Are there any easy-to-understand ways to do this except brute-forcing all the $\mathbb{F}_{q^i}$ and see if it fits the curve equation? Do I even get it right?
I also stumbled upon calculating the polynomial through constructing Cartier-Manin matrix and I even implemented it, but it gives me polynomial modulo $p$. Is it possible to get the actual polynomial from it?
So basically my questions are:
- How do I get numbers $M_i$ of points on the hyperelliptic curve for recurring formula above?
- Are there any other ways to construct the polynomial? What steps should I make?
P.S. I won't be working with really large fields, so I don't need a sophisticated algorithm: just something that works in the most of simple cases.
You just stumbled upon one of the most beautiful and classical parts of algebraic geometry: These computations are generally done by using the Weil conjectures. Specifically, you just need to calculate some first cases and then you have a closed formula that gives you the answer.
This https://web.maths.unsw.edu.au/~davidharvey/talks/avgpoly.pdf seems to tackle exactly the calculation of the number of points on a hyperelliptic curve. My suggestion is read the Wikipedia page on the Weil conjectures before you try to handle something more specific, or of course feel free to learn more about the subject.
In particular, the Weil conjectures give you that for an elliptic curve the number of points over $\mathbb{F}_{q^m}$ is $1-a^m-b^m+q^m$, and computing the number of points for $m=1$ gives you the number of points for every $m$.