ГлавнаяАрхивГиперэллиптические кривые, матрицы Картье - Манина и многочлены Лежандра

Гиперэллиптические кривые, матрицы Картье - Манина и многочлены Лежандра | Прикладная дискретная математика. 2017. № 37. DOI: 10.17223/20710410/37/2

Для использования гиперэллиптических кривых в криптографии необходимо вычисление порядка Якобиана кривой, что эквивалентно вычислению характеристического многочлена эндоморфизма Фробениуса х(А). Вычисление матрицы Картье - Манина кривой позволяет найти многочлен х(А) по модулю характеристики базового поля. Данная информация в дальнейшем может быть использована для вычисления полного многочлена х(А) в комбинации с другими методами. В работе исследуются гиперэллиптические кривые вида C\ : y2 = x2g+1 + axg+1 + bx и C2 : y2 = x2g+2+axg+1 +b над конечным полем Fq, q = pn,p > 2. Кривые приводятся в форму C1>p : y2 = x2g+1 - 2pxg+1 + x и C2,p : y2 = x2g+2 - 2pxg+1 + 1. Доказывается, что в данной форме, элементы соответствующих матриц Картье - Манина являются многочленами Лежандра, а сами матрицы - центросимметричными и эквивалентными блочно-диагональным матрицам. Как следствие, для вычисления матриц достаточно вычислить только половину коэффициентов. В случае (p,g) = 1 известно, что матрицы Картье - Манина кривых C1,C2 являются мономиальными. В данной работе доказывается, что по связанной с мономиальной матрицей перестановке можно восстановить многочлен х(А) (mod p) в факторизованной форме. В качестве приложения разработанных методов для случая (p,g) = 1 получены все возможные многочлены х(А) (mod p) кривой C1 рода g от 1 до 7 над полями Fp и Fp2.
  • Title Гиперэллиптические кривые, матрицы Картье - Манина и многочлены Лежандра
  • Headline Гиперэллиптические кривые, матрицы Картье - Манина и многочлены Лежандра
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 37
  • Date:
  • DOI 10.17223/20710410/37/2
Ключевые слова
hyperelliptic curve cryptography, Cartier -Manin matrix, гиперэллиптические кривые, матрица Картье - Манина, многочлены Лежандра, Legendre polynomials
Авторы
Ссылки
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.
Гиперэллиптические кривые, матрицы Картье - Манина и многочлены Лежандра | Прикладная дискретная математика. 2017. № 37. DOI: 10.17223/20710410/37/2
Гиперэллиптические кривые, матрицы Картье - Манина и многочлены Лежандра | Прикладная дискретная математика. 2017. № 37. DOI: 10.17223/20710410/37/2