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 x(A) Е Z[A|. By calculating Cartier - Manin matrix, we can recover the polynomial x(A) 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 C1 : y2 = x2g+1 + + ax9+1 + bx and C2 : y2 = x2g+2 + ax9+1 + b over the finite field Fq, q = pn, p > 2. We transform these curves to the form C1,p : y2 = x2g+1 - 2px9+1 + x and C2,p : y2 = x2g+2 - 2px9+1 +1, where p = -a/(2\/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 C1,p and C2,p are equivalent to block-diagonal matrices. In the case of gcd(p,g) = 1, Miller and Lubin proved that the matrices of curves C1 and C2 are monomial. We prove that the polynomial x(A) (mod 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 x(A) (mod p) in the case of gcd(p,g) = 1, g is from 2 to 7 and the curve C1 is over Fp if Vb Е Fp and over Fp2 if Vb Е Fp.
Download file
Counter downloads: 206
- Title Hyperelliptic curves, Cartier - Manin matrices and Legendre polynomials
- Headline Hyperelliptic curves, Cartier - Manin matrices and Legendre polynomials
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 37
- Date:
- DOI 10.17223/20710410/37/2
Keywords
hyperelliptic curve cryptography, Cartier -Manin matrix, гиперэллиптические кривые, матрица Картье - Манина, многочлены Лежандра, Legendre polynomialsAuthors
References
Koblitz N. Hyperelliptic cryptosystems. J. Cryptology, 1989, vol.1, no. 3, pp. 139-150.
Enge A. and Gaudry P. A general framework for subexponential discrete logarithm algorithms. Acta Arith., 2000, vol. 102, pp. 83-103.
Enge A., Gaudry P., and Thome E. An L(1/3) discrete logarithm algorithm for low degree curves. J. Cryptology, 2011, vol.24, no. 1, pp. 24-41.
Gaudry P., Thome E., Theriault N., and Diem C. A double large prime variation for small genus hyperelliptic index calculus. Math. Comput., 2007, vol.76, no. 257, pp. 475-492.
Barbulescu R., Gaudry P., Joux A., and Thome E. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. LNCS, 2014, vol.8441, pp. 1-16.
Manin Yu. I. O matritse Khasse - Vitta algebraicheskoy krivoy [The Hasse-Witt matrix of an algebraic curve]. Izv. Akad. Nauk SSSR, Ser. Mat., 1961, vol.25, no. 1, pp. 153-172. (in Russian)
Bostan A., Gaudry P., and Schost; E. Linear recurrences with polynomial coefficients and application to integer factorization and Cartier - Manin operator. SIAM J. Comput., 2007, vol. 36, no. 6, pp. 1777-1806.
Harvey D. and Sutherland A.V. Hasse - Witt matrices of hyperelliptic curves in average polynomial time. LMS J. Comput. Math., 2014, vol.17, no. A, pp. 257-273.
Yui N. Jacobi quartics, Legendre polynomials and formal groups. Lecture Notes in Mathematics, 1988, vol. 1326, pp. 182-215.
Miller L. The Hasse - Witt-matrix of special projective varieties. Pacific J. Math., 1972, vol.43, no. 2, pp. 443-455.
Miller L. Curves with invertible Hasse - Witt-matrix. Math. Ann., 1972, vol.197, pp.123-127.
Leprevost F. and Morain F. Revetements de courbes elliptiques a multiplication complexe par des courbes hyperelliptiques et sommes de caracteres. J. Number Theory, 1997, vol.64, no.2, pp. 165-182.
Brillhart J. and Morton P. Class numbers of quadratic fields, Hasse invariants of elliptic curves, and the supersingular polynomial. J. Number Theory, 2004, vol.106, no. 1, pp.79-111.
Satoh T. Generating genus two hyperelliptic curves over large characteristic finite fields. LNCS, 2009, vol. 5479, pp. 536-553.
Freeman D. M. and Satoh T. Constructing pairing-friendly hyperelliptic curves using Weil restriction. J. Number Theory, 2011, vol. 131, no. 5, pp. 959-983.
Guillevic A. and Vergnaud D. Genus 2 hyperelliptic curve families with explicit Jacobian order evaluation and pairing-friendly constructions. LNCS, 2012, vol.7708, pp.234-253.
Garcia-Planas M. I. and Magret M. D. Eigenvectors of permutation matrices. Adv. Pure Math., 2015, vol.5, no. 7, pp. 390-393.
Carlitz L. Congruence properties of the polynomials of Hermite, Laguerre and Legendre. Mathematische Zeitschrift, 1953, vol.59, pp. 474-483.
Weaver J. R. Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors. Amer. Math. Monthly, 1985, vol.92, no. 10, pp. 711-717.
Yui N. On the Jacobian varieties of hyperelliptic curves over fields of characteristic p > 2. J. Algebra, 1978, vol.52, no.2, pp.378-410.
Novoselov S. A. Hyperelliptic curves, Cartier - Manin matrices and Legendre polynomials. Prikladnaya Diskretnaya Matematika. Prilozhenie, 2017, no. 10, pp. 30-32.
Hyperelliptic curves, Cartier - Manin matrices and Legendre polynomials | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 37. DOI: 10.17223/20710410/37/2
Download full-text version
Counter downloads: 615