Подсчёт числа точек на гиперэллиптических кривых вида y2 = x2g+1 + axg+1 + bx | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/9

Подсчёт числа точек на гиперэллиптических кривых вида y2 = x2g+1 + axg+1 + bx

Изучаются гиперэллиптические кривые указанного в названии вида над конечным полем GF(p^n), p>2. Для случая g = 3, 4, p делит 4g и b - корень степени 4g, представлены методы для вычисления числа точек в якобиане кривой.

Counting points on hyperelliptic curves of type y2 = x2g+1 + axg+1 + bx.pdf Let Fq be a finite field, q = pn,p > 2. Hyperelliptic curves with equation C : y2 = x29+i + ax9+i + bx were investigated in [1-3]. For genus 2 case it is known [4] that Jacobian of such curves splits into product of certain elliptic curves over some extension of the base field. There are explicit formulae [5] expressing number of points in the Jacobian of curve in terms of traces of Frobenius of elliptic curves. In this work, we generalize this approach to genus 3, 4 case combining it with computing Cartier - Manin matrices where it's possible. Using the method of Paulhus [6, 7] we can obtain decompositions of the Jacobian over the extensions of the ground field. The Cartier - Manin matrix of the curve allows us to find the number of points on the curve modulo p. But in general it's only computable for finite fields of small characteristic. In the work [2] the curve C is transformed to the curve C : y2 = x2g+1 - 2pxg+1 + x defined over F[v^b] via isomorphism defined over Fq[ Vb], and it is proved that the elements of the Cartier - Manin matrix of this curve can be expressed in terms of Legendre polynomials. But an efficient method to compute Legendre polynomials was not provided. In this work, we show how to compute these polynomials for the case g = 3 and big characteristic. Partial results for the case g > 3 are also provided. 1. Computing Cartier - Manin matrix of the curve C It is known that the number of points on certain elliptic curves can be expressed through Legendre polynomials. Thus some instances of the polynomials from [2, Table 1,2] can be computed for finite fields of big characteristic using the Schoof - Elkies - Atkin [8, § 17.2.2] algorithm. We collect such cases in the following theorem. Theorem 1 [9-11]. Let c e Fp, p > 3. Then (-6 ^ 1) Pp-1 (c) = - t2 (mod p), where t2 is a trace of Frobenius of the elliptic curve p- 2 ' ' V p E2 : y2 = x3 - 3(c2 + 3)x + 2c(c2 - 9); 2) P|3/p|(c) = (p) t3 (mod p), where t3 is a trace of Frobenius of the elliptic curve E3 : y2 = x3 + 3(4c - 5)x + 2(2c2 - 14c + 11); /6\ 3) P[p/4j (c) = ( - I t4 (mod p), where t4 is a trace of Frobenius of the elliptic curve E4 : y2 = x3 - § (3c + 5)x + 9c + 7; 4) P[_p/6j (c) = ( - ) t6 (mod p), where p > 5 and t6 is a trace of Frobenius of the elliptic p curve E6 : y2 = x3 - 3x + 2c. Using this theorem we can compute Cartier - Manin matrix of curve CC of genus 3 completely. For the case of g > 3 we get partial information. For example, the polynomial Pp-i appears in the formulae for g = 5, 7 in [2, Table 1,2]. 2 2. Decomposition of the Jacobian of the curve C over finite field In the work [6] there are decompositions for the curve CC over algebraically closed field. But the method works over any field as long as we know the group of automorphisms or its subgroups. So we need to obtain information about subgroups of this group over finite field. Denote by AutC (Fq) an automorphism group of curve over the finite field Fq, Cm a cyclic group of order m and by Dm a dihedral group of order m. Let also Zm be a primitive m-root of unity. Every hyperelliptic curve has hyperelliptic involution w. Some other automorphisms of the curve CC are collected in the following theorem. Theorem 2. Let C' : y2 = x2g+1 + cxg+1 + x be a genus g hyperelliptic curve defined over the finite field Fq, q = pn. 1) Autc(Fq) contains a non-hyperelliptic involution s : (x,y) M- , and subgroup C2 x C2. 2) If p \ 2g and 2g|(q - 1) then Autc(Fq) contains an automorphism r : (x,y) M M (Zgx,Z2gy) of order 2g and subgroup D4g. Decompositions for the Jacobian of the curve CC follows from Theorem 2 and [7, Th. 4]: - (genus 3) Jc - E x JD if C2 x C2 С AutFq (C') and Jc> - Ef x E2 if Du С AutFq (C'); - (genus 4) Jc - JDl x JD2 if C2 x C2 С AutFq (C') and Jc/ - JD if D16 С AutFq (C') Note that C2 x C2 С AutFq(C') holds in any field, thus we always have corresponding decomposition. But D4g С Autc holds in the field Fq [(2g], so we should work in an extension of Fq of degree up to 2g to get decomposition. The degree of this extension is the smallest integer k such that 2g|(qk - 1). 3. Genus 3 If we apply Theorem 2 to the genus 3 case, we obtain following result. Theorem 3. Let C : y2 = x7 + cx4 + x be a genus 3 hyperelliptic curve defined over the finite field Fq,q = pn,p > 3. Then 1) JCi - E x JD over Fq for some genus 2 curve D and elliptic curve E; 2) Jci - Ef x E2 over Fq if q = 1 (mod 6) and over Fq2 if q = - 1 (mod 6). E1, E2 are elliptic curves E1 : y2 = x3 - 3x + c and E2 : y2 = x3 + cx2 + x; 3) if q = 1 (mod 6), then #JC(Fq) = (1 - t1 + q)2(1 - t2 + q), where t1,t2 are traces of Frobenius of E1, E2 over Fq; 4) if q = -1 (mod 6), then #JC,(Fq2) = (1 - t^ + q2)2(1 - t2)2 + q2), where t^,t2>2 are traces of Frobenius of the curves E1,E2 over Fq2. The Frobenius polynomial of the curve C' over Fq has a form Xc,q (T) = (T2 - tT + q)(T4 - b{T3 + («1,2 + t2 + b1t + bj - q)T2 - qb{T + q2), where «1,2 = -(2*1,2 +1^), t £ Z, |t| ^ b1 £ Z, ^ The traces t1,t2,t1,2,t2,2 can be efficiently computed using SEA-algorithm. By using results from Section 1 to compute polynomials from [2, Table 1, 2] we can efficiently compute Xc(T) (mod p) and therefore determine b1,t. So, theorem 3 provides an efficient method to compute the number of points in the Jacobian of the curve C'. Since the curve C is isomorphic to C over Fq [ theorem 3 also allows us to compute the number of points on C in the case £ Fq. 4. Genus 4 Applying Theorem 2 and [7, Th.4] to the curve C' of genus 4 we obtain following result. Theorem 4. Let CC : y2 = x9 + cx5 + x be a genus 4 hyperelliptic curve defined over the finite field Fq, q = pn, p > 2 and 81(q - 1). Then Jc - JD, where D is a genus 2 curve with equation y2 = (x4 - 4x2 + 2 + c)(x + 2). Since the model of the curve D is known, we can use algorithm [12] to compute number of points in the Jacobian of the curve D and therefore in Jc. This also allows us to compute the number of points on genus 4 hyperelliptic curve C in the case Vb £ Fq. Note that this algorithm has complexity O(log7 p) and less efficient than SEA algorithm with complexity O(log4p), but still more efficient then general algorithms for genus 3 curves. Also, in this case we can't use results from Section 1, because we don't know how to efficiently compute Legendre polynomial P\_p/8\.

Ключевые слова

point counting, Legendre polynomials, Cartier - Manin matrix, hyperelliptic curves, многочлены Лежандра, матрицы Картье - Манина, гиперэллиптические кривые

Авторы

ФИООрганизацияДополнительноE-mail
Новоселов Семен АлександровичБалтийский федеральный университет им. И. Кантаассистент ИФМНиИТsnovoselov@kantiana.ru
Всего: 1

Ссылки

Sun Z.H. Legendre polynomials and supercongruences. Acta Arith., 2013, vol.159, no. 2, pp. 169-200.
Gaudry P. and Schost E. Genus 2 point counting over prime fields. J. Symbolic Comput., 2012, vol.47, no. 4, pp. 368-400.
Cohen H., Frey G, et al. Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, 2005.
Sun Z. H. Congruences concerning Legendre polynomials II. J. Number Theory, 2013, vol. 133, no.6, pp. 1950-1976. Number Theory, 2013, vol. 133, no. 5 pp. 1572-1595.
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.
Paulhus J. R. Decomposing Jacobians of curves with extra automorphisms. Acta Arith., 2008, vol.132, no. 3, pp. 231-244.
Paulhus J. R. Elliptic factors in Jacobians of low genus curves. Phd Thesis, 2007.
Satoh T. Generating genus two hyperelliptic curves over large characteristic finite fields. LNCS, 2009, vol. 5479, pp. 536-553.
Miller L. Curves with invertible Hasse - Witt-matrix. Mathematische Annalen, 1972, vol. 197, no. 2, pp. 123-127.
Novoselov S.A. Hyperelliptic curves, Cartier - Manin matrices and Legendre polynomials. Prikladnaya Diskretnaya Matematika, 2017, no. 37, pp. 20-31.
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.
 Подсчёт числа точек на гиперэллиптических кривых вида  y<sup>2</sup> = x<sup>2g+1</sup> + ax<sup>g+1</sup> + bx | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/9

Подсчёт числа точек на гиперэллиптических кривых вида y2 = x2g+1 + axg+1 + bx | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/9