×

Counting points on hyperelliptic curves of type \(y^2=x^{2g+1}+ax^{g+1}+bx\). (English) Zbl 1455.11168

Summary: In this work, we investigate hyperelliptic curves of type \(C:y^2=x^{2g+1}+ax^{g+1}+bx\) over the finite field \(\mathbb{F}_q,q=p^n\), \(p>2\). For the case of \(g=3\) we propose an algorithm to compute the number of points on the Jacobian of the curve with complexity \(\widetilde{O}(\log^4p)\) over \(\mathbb{F}_p\). In case of \(g=4\) we present a point counting algorithm with complexity \(\widetilde{O}(\log^8q)\) over \(\mathbb{F}_q\). The Jacobian \(J_C\) splits over an extension of the field \(\mathbb{F}_q\) on the Jacobians of the curves defined by the Dickson polynomials \(D_g(x, 1)\) of degree \(g\). For these curves of genus \(2, 3, 5\) with equation \(y^2=D_g(x,1)+a\) and curves of genus \(2, 4\) with equation \(y^2=(x+2)(D_g(x,1)+a)\), we give the lists of possible characteristic polynomials of the Frobenius endomorphism modulo \(p\).

MSC:

11Y16 Number-theoretic algorithms; complexity
14H45 Special algebraic curves and curves of low genus
14Q05 Computational aspects of algebraic curves
11G20 Curves over finite and local fields
11T06 Polynomials over finite fields

Software:

SageMath; M4GB
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Satoh, T., Generating genus two hyperelliptic curves over large characteristic finite fields, (Annual International Conference on the Theory and Applications of Cryptographic Techniques (2009), Springer), 536-553 · Zbl 1239.94065
[2] Guillevic, A.; Vergnaud, D., Genus 2 hyperelliptic curve families with explicit jacobian order evaluation and pairing-friendly constructions, (International Conference on Pairing-Based Cryptography (2012), Springer), 234-253 · Zbl 1305.94053
[3] Novoselov, S. A., Hyperelliptic curves, cartier-manin matrices and legendre polynomials, Priklad. Diskret. Mat., 37, 20-31 (2017) · Zbl 1481.11061
[4] Brillhart, J.; Morton, P., Class numbers of quadratic fields, hasse invariants of elliptic curves, and the supersingular polynomial, J. Number Theory, 106, 1, 79-111 (2004) · Zbl 1083.11036
[5] Sun, Z.-H., Congruences concerning legendre polynomials ii, J. Number Theory, 133, 6, 1950-1976 (2013) · Zbl 1277.11002
[6] Sun, Z.-H., Congruences involving \(\begin{pmatrix} 2 k \\ k \end{pmatrix}^2 \begin{pmatrix} 3 k \\ k \end{pmatrix} \), J. Number Theory, 133, 5, 1572-1595 (2013)
[7] Sun, Z.-H., Legendre polynomials and supercongruences, Acta Arith., 159, 2, 169-200 (2013) · Zbl 1287.11004
[8] Chou, K.-M. J.; Kani, E., Simple geometrically split abelian surfaces over finite fields, J. Ramanujan Math. Soc., 29, 1, 31-62 (2014) · Zbl 1309.11052
[9] Furukawa, E.; Kawazoe, M.; Takahashi, T., Counting points for hyperelliptic curves of type \(y^2 = x^5 + a x\) over finite prime fields, (International Workshop on Selected Areas in Cryptography (2003), Springer), 26-41 · Zbl 1081.94023
[10] Haneda, M.; Kawazoe, M.; Takahashi, T., Suitable curves for genus-4 hcc over prime fields: point counting formulae for h yperelliptic curves of type \(y^2 = x^{2 k + 1} + a x\), (International Colloquium on Automata, Languages, and Programming (2005), Springer), 539-550 · Zbl 1084.94016
[11] Tautz, W.; Top, J.; Verberkmoes, A., Explicit hyperelliptic curves with real multiplication and permutation polynomials, Can. J. Math., 43, 5, 1055-1064 (1991) · Zbl 0793.14022
[12] Bouw, I. I.; Diem, C.; Scholten, J., Ordinary elliptic curves of high rank over \(\overline{\mathbb{F}}_p(x)\) with constant j-invariant, Manuscr. Math., 114, 4, 487-501 (2004) · Zbl 1128.11029
[13] Smith, B. A., Explicit endomorphisms and correspondences (2005), University of Sydney, Ph.D. thesis
[14] Kohel, D. R.; Smith, B. A., Efficiently computable endomorphisms for hyperelliptic curves, (International Algorithmic Number Theory Symposium (2006), Springer), 495-509 · Zbl 1143.14312
[15] Paulhus, J., Elliptic factors in jacobians of low genus curves (2007), University of Illinois at Urbana-Champaign, Ph.D. thesis
[16] Paulhus, J., Decomposing jacobians of curves with extra automorphisms, Acta Arith., 132, 3, 231-244 (2008) · Zbl 1142.14017
[17] Carlitz, L., Some arithmetic properties of the legendre polynomials, Acta Arith., 4, 2, 99-107 (1958) · Zbl 0089.02902
[18] Honda, T., Two congruence properties of legendre polynomials, Osaka J. Math., 13, 1, 131-133 (1976) · Zbl 0345.12101
[19] Morton, P., Legendre polynomials and complex multiplication, i, J. Number Theory, 130, 8, 1718-1731 (2010) · Zbl 1200.11093
[20] Morton, P., Explicit congruences for class equations, Funct. Approx. Comment. Math., 51, 1, 77-110 (2014) · Zbl 1364.11112
[21] Cohen, H.; Frey, G.; Avanzi, R.; Doche, C.; Lange, T.; Nguyen, K.; Vercauteren, F., Handbook of Elliptic and Hyperelliptic Curve Cryptography (2005), CRC Press
[22] Kani, E.; Rosen, M., Idempotent relations and factors of jacobians, Math. Ann., 284, 2, 307-327 (1989) · Zbl 0652.14011
[23] Brandt, R.; Stichtenoth, H., Die automorphismengruppen hyperelliptischer kurven, Manuscr. Math., 55, 1, 83-92 (1986) · Zbl 0588.14022
[24] Bujalance, E.; Gamboa, J.; Gromadzki, G., The full automorphism groups of hyperelliptic riemann surfaces, Manuscr. Math., 79, 1, 267-282 (1993) · Zbl 0788.30031
[25] Bhargava, M.; Zieve, M. E., Factoring dickson polynomials over finite fields, Finite Fields Appl., 5, 2, 103-111 (1999) · Zbl 0929.11060
[26] Pila, J., Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comput., 55, 192, 745-763 (1990) · Zbl 0724.11070
[27] Lidl, R.; Mullen, G. L.; Turnwald, G., Dickson Polynomials, Vol. 65 (1993), Chapman & Hall/CRC · Zbl 0823.11070
[28] Manin, Y. I., The hasse-witt matrix of an algebraic curve, Izv. Akad. Nauk SSSR, Ser. Mat., 25, 1, 153-172 (1961) · Zbl 0102.27802
[29] Yui, N., On the jacobian varieties of hyperelliptic curves over fields of characteristic \(p > 2\), J. Algebra, 52, 2, 378-410 (1978) · Zbl 0404.14008
[30] Schoof, R., Counting points on elliptic curves over finite fields, J. Théor. Nr. Bordx., 7, 1, 219-254 (1995) · Zbl 0852.11073
[31] Stichtenoth, H., Algebraic Function Fields and Codes, Vol. 254 (2009), Springer Science & Business Media · Zbl 1155.14022
[32] Von Zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2013), Cambridge University Press · Zbl 1277.68002
[33] Abelard, S.; Gaudry, P.; Spaenlehauer, P.-J., Improved complexity bounds for counting points on hyperelliptic curves, Found. Comput. Math., 19, 3, 591-621 (2019) · Zbl 1470.11170
[34] Abelard, S., Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus, J. Complex., 57, Article 101440 pp. (2020) · Zbl 1432.11065
[35] Faugere, J.-C., A new efficient algorithm for computing gröbner bases (f4), J. Pure Appl. Algebra, 139, 1-3, 61-88 (1999) · Zbl 0930.68174
[36] Makarim, R. H.; Stevens, M., M4gb: an efficient gröbner-basis algorithm, (Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation (2017)), 293-300 · Zbl 1457.68329
[37] Cohen, H., A Course in Computational Algebraic Number Theory, Vol. 138 (2013), Springer Science & Business Media
[38] Lindhurst, S., An analysis of shanks’s algorithm for computing square roots in finite fields, (Number Theory. Number Theory, Ottawa, 1996. Number Theory. Number Theory, Ottawa, 1996, CRM Proc. Lecture Notes, vol. 19 (1999)), 231-242 · Zbl 0928.11055
[39] Müller, S., On the computation of square roots in finite fields, Des. Codes Cryptogr., 31, 3, 301-312 (2004) · Zbl 1052.11084
[40] Cantor, D. G., Computing in the jacobian of a hyperelliptic curve, Math. Comput., 48, 177, 95-101 (1987) · Zbl 0613.14022
[41] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 9.0) (2019)
[42] Novoselov, S. A.; Boltnev, Y. F., Characteristic polynomials of the curve \(y^2 = x^7 + a x^4 + b x\) over finite fields, Priklad. Diskret. Mat. Suppl, 12, 44-46 (2019)
[43] Gaudry, P.; Schost, É., Genus 2 point counting over prime fields, J. Symb. Comput., 47, 4, 368-400 (2012) · Zbl 1267.11127
[44] Huang, M.-D.; Ierardi, D., Counting points on curves over finite fields, J. Symb. Comput., 25, 1, 1-21 (1998) · Zbl 0919.11046
[45] Novoselov, S. A., Counting points on hyperelliptic curves of type \(y^2 = x^{2 g + 1} + a x^{g + 1} + b x\), Priklad. Diskret. Mat. Suppl, 11, 30-33 (2018)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.