Hyperelliptic curves, Cartier–Manin matrices and Legendre polynomials

Using hyperelliptic curves in cryptography requires the computation of the Jacobian order of a curve. This is equivalent to computing the characteristic polynomial of Frobenius $\chi(\lambda)\in\mathbb Z[\lambda]$. By calculating Cartier–Manin matrix, we can recover the polynomial $\chi(\lambda)$ modulo the characteristic of the base field. This information can further be used for recovering full polynomial in combination with other methods. In this paper, we investigate the hyperelliptic curves of the form $C_1\colon y^2=x^{2g+1}+ax^{g+1}+bx$ and $C_2\colon y^2=x^{2g+2}+ax^{g+1}+b$ over the finite field $\mathbb F_q$, $q=p^n$, $p>2$. We transform these curves to the form $C_{1,\rho}\colon y^2=x^{2g+1}-2\rho x^{g+1}+x$ and $C_{2,\rho}\colon y^2=x^{2g+2}-2\rho x^{g+1}+1$, where $\rho=-a/(2\sqrt b)$, and prove that the coefficients of the corresponding Cartier–Manin matrices for the curves in this form are Legendre polynomials. As a consequence, the matrices are centrosymmetric and therefore, for finding the matrix, it's enough to compute a half of coefficients. Cartier–Manin matrices are determined up to a transformation of the form $S^{(p)}WS^{-1}$. It is known that centrosymmetric matrices can be transformed to the block-diagonal form by an orthogonal transformation. We prove that this transformation can be modified to have a form $S^{(p)}WS^{-1}$ and be defined over the base field of the curve. Therefore, Cartier–Manin matrices of curves $C_{1,\rho}$ and $C_{2,\rho}$ are equivalent to block-diagonal matrices. In the case of $\mathrm{gcd}(p,g)=1$, Miller and Lubin proved that the matrices of curves $C_1$ and $C_2$ are monomial. We prove that the polynomial $\chi(\lambda)\pmod p$ can be found in factored form in terms of Legendre polynomials by using permutation attached to the monomial matrix. As an application of our results, we list all possible polynomials $\chi(\lambda)\pmod p$ in the case of $\mathrm{gcd}(p,g)=1$, $g$ is from $2$ to $7$ and the curve $C_1$ is over $\mathbb F_p$ if $\sqrt b\in\mathbb F_p$ and over $\mathbb F_{p^2}$ if $\sqrt b\not\in\mathbb F_p$.