Hyperelliptic curves, Cartier--Manin matrices and Legendre polynomials

S. A. Novoselov

Prikladnaâ diskretnaâ matematika, no. 3 (2017), pp. 20-31.

Résumé

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

Détail

Keywords: hyperelliptic curve cryptography
Mots-clés : Cartier–Manin matrix, Legendre polynomials.

Bibliographie

[1] Koblitz N., “Hyperelliptic cryptosystems”, J. Cryptology, 1:3 (1989), 139–150 | DOI | MR | Zbl

[2] Enge A., Gaudry P., “A general framework for subexponential discrete logarithm algorithms”, Acta Arith., 102 (2000), 83–103 | DOI | MR

[3] Enge A., Gaudry P., Thomé E., “An $L(1/3)$ discrete logarithm algorithm for low degree curves”, J. Cryptology, 24:1 (2011), 24–41 | DOI | MR | Zbl

[4] Gaudry P., Thomé E., Thériault N., Diem C., “A double large prime variation for small genus hyperelliptic index calculus”, Math. Comput., 76:257 (2007), 475–492 | DOI | MR | Zbl

[5] Barbulescu R., Gaudry P., Joux A., Thomé E., “A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic”, LNCS, 8441, 2014, 1–16 | MR | Zbl

[6] Manin Yu. I., “The Hasse–Witt matrix of an algebraic curve”, Izv. Akad. Nauk SSSR Ser. Mat., 25:1 (1961), 153–172 (in Russian) | MR | Zbl

[7] Bostan A., Gaudry P., Schost E., “Linear recurrences with polynomial coefficients and application to integer factorization and Cartier–Manin operator”, SIAM J. Comput., 36:6 (2007), 1777–1806 | DOI | MR | Zbl

[8] Harvey D., Sutherland A.V., “Hasse–Witt matrices of hyperelliptic curves in average polynomial time”, LMS J. Comput. Math., 17:A (2014), 257–273 | DOI | MR

[9] Yui N., “Jacobi quartics, Legendre polynomials and formal groups”, Lecture Notes in Mathematics, 1326, 1988, 182–215 | DOI | MR | Zbl

[10] Miller L., “The Hasse–Witt-matrix of special projective varieties”, Pacific J. Math., 43:2 (1972), 443–455 | DOI | MR | Zbl

[11] Miller L., “Curves with invertible Hasse–Witt-matrix”, Math. Ann., 197 (1972), 123–127 | DOI | MR | Zbl

[12] Leprevost F., Morain F., “Revêtements de courbes elliptiques à multiplication complexe par des courbes hyperelliptiques et sommes de caractères”, J. Number Theory, 64:2 (1997), 165–182 | DOI | MR | Zbl

[13] Brillhart J., Morton P., “Class numbers of quadratic fields, Hasse invariants of elliptic curves, and the supersingular polynomial”, J. Number Theory, 106:1 (2004), 79–111 | DOI | MR | Zbl

[14] Satoh T., “Generating genus two hyperelliptic curves over large characteristic finite fields”, LNCS, 5479, 2009, 536–553 | MR | Zbl

[15] Freeman D. M., Satoh T., “Constructing pairing-friendly hyperelliptic curves using Weil restriction”, J. Number Theory, 131:5 (2011), 959–983 | DOI | MR | Zbl

[16] Guillevic A., Vergnaud D., “Genus 2 hyperelliptic curve families with explicit Jacobian order evaluation and pairing-friendly constructions”, LNCS, 7708, 2012, 234–253 | MR

[17] Garcia-Planas M. I., Magret M. D., “Eigenvectors of permutation matrices”, Adv. Pure Math., 5:7 (2015), 390–393 | DOI

[18] Carlitz L., “Congruence properties of the polynomials of Hermite, Laguerre and Legendre”, Mathematische Zeitschrift, 59 (1953), 474–483 | DOI | MR

[19] Weaver J. R., “Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors”, Amer. Math. Monthly, 92:10 (1985), 711–717 | DOI | MR | Zbl

[20] Yui N., “On the Jacobian varieties of hyperelliptic curves over fields of characteristic $p>2$”, J. Algebra, 52:2 (1978), 378–410 | DOI | MR | Zbl

[21] Novoselov S. A., “Hyperelliptic curves, Cartier–Manin matrices and Legendre polynomials”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2017, no. 10, 29–32