About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 29, No 2, 2022, P. 62-79
UDC 519.8+518.25
S. A. Novoselov and Yu. F. Boltnev
On the number of points on the curve $y^2 = x^7 + ax^4 + bx$ over a finite field
Abstract:
We provide explicit formulae for the number of points on a genus $3$ hyperelliptic curve of type $y^2 = x^7 + ax^3 + bx$ over a finite field $\mathbb {F}_q$ of characteristic $p > 3$. As an application of these formulae, we prove that point-counting problem on this type of curves has heuristic time complexity of order $O(log^{4} q)$ bit operations.
Tab. 2, bibliogr. 27.
Keywords: hyperelliptic curve, point-counting, characteristic polynomial.
DOI: 10.33048/daio.2022.29.726
Semyon A. Novoselov1
Yurii F. Boltnev1
1. Immanuel Kant Baltic Federal University,
14 Aleksandr Nevskii Street, 236041 Kaliningrad, Russia
e-mail: snovoselov@kantiana.ru, yuri.boltnev@gmail.com
Received October 31, 2021
Revised January 31, 2022
Accepted February 7, 2022
References
[1] Information technology. Cryptographic data security. Signature and verification processes of electronic digital signature, GOST 34.10-2018 (Standartinform, Moscow, 2018) [Russian].[2] Digital signature standard (DSS), FIPS 186-4 (NIST, Gaithersburg, MD, 2013).
Available at https://doi.org/10.6028/NIST.FIPS.186-4 (accessed Mar. 9, 2022).
[3] N. Koblitz, Hyperelliptic cryptosystems, J. Cryptol. 1 (3), 139–150 (1989).
[4] Handbook of Elliptic and Hyperelliptic Curve Cryptography (Chapman Hall/ CRC, Boca Raton, FL, 2006).
[5] R. Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordx. 7 (1), 219–254 (1995).
[6] S. Abelard, P. Gaudry, and P. J. Spaenlehauer, Improved complexity bounds for counting points on hyperelliptic curves, Found. Comput. Math. 19 (3), 591–621 (2019).
[7] P. Gaudry and É. Schost, Genus 2 point counting over prime fields, J. Symb. Comput. 47 (4), 368–400 (2012).
[8] S. Abelard, Counting points on hyperelliptic curves in large characteristic: Algorithms and complexity, PhD Thesis (Univ. Lorraine, Nancy, 2018).
[9] S. Dobson, S. Galbraith, and S. Benjamin, Trustless unknown-order groups, J. Math. Cryptol. [in print].
[10] D. Boneh, J. Bonneau, B. Bünz, and B. Fisch, Verifiable delay functions, in Advances in Cryptology – CRYPTO 2018 (Proc. 38th Annu. Int. Cryptol. Conf., Santa Barbara, CA, USA, Aug. 19–23, 2018), Pt. I (Springer, Cham, 2018), pp. 757–788 (Lect. Notes Comput. Sci., Vol. 10991).
[11] R. L. Rivest, A. Shamir, and D. A. Wagner, Time-lock puzzles and timedrelease crypto. Tech. Rep. MIT-LCS-TR-684 (MIT, Cambridge, MA, 1996).
[12] J. Benaloh and M. de Mare, One-way accumulators: A decentralized alternative to digital signatures, in Advances in Cryptology – EUROCRYPT’93 (Proc. Workshop Theory Appl. Cryptogr. Tech., Lofthus, Norway, May 23–27, 1993) (Springer, Heidelberg, 1994), pp. 274–285 (Lect. Notes Comput. Sci., Vol. 765).
[13] T. Satoh, Generating genus two hyperelliptic curves over large characteristic finite fields, in Advances in Cryptology – EUROCRYPT 2009 (Proc. 28th Annu. Int. Conf. Theory Appl. Cryptogr. Tech., Cologne, Germany, Apr. 26–30, 2009) (Springer, Heidelberg, 2009), pp. 536–553 (Lect. Notes Comput. Sci., Vol. 5479).
[14] A. Guillevic and D. Vergnaud, Genus 2 hyperelliptic curve families with explicit Jacobian order evaluation and pairing-friendly constructions, in PairingBased Cryptography – Pairing 2012 (Rev. Sel. Pap. 5th Int. Conf., Cologne, Germany, May 16–18, 2012) (Springer, Heidelberg, 2013), pp. 234–253 (Lect. Notes Comput. Sci., Vol. 7708).
[15] S. A. Novoselov, Counting points on hyperelliptic curves of type $y^2 = x^{2g+1} + ax^{g+1} + bx$, Finite Fields Appl. 68, ID 101757, 27 p. (2020).
[16] D. Mumford, Abelian Varieties (Oxford Univ. Press, Oxford, 1974).
[17] J. Tate, Endomorphisms of abelian varieties over finite fields, Invent. Math. 2 (2), 134–144 (1966).
[18] I. B. Chacon, R. Chapman, S. Fordham, and G. McGuire, Divisibility of $L$-polynomials for a family of curves, in Contemporary Developments in Finite Fields and Applications (World Sci., Singapore, 2016), pp. 1–10.
[19] V. Singh, G. McGuire, and A. Zaytsev, Classification of characteristic polynomials of simple supersingular abelian varieties over finite fields, Funct. Approximatio, Comment. Math. 51 (2), 415–436 (2014).
[20] K. M. J. Chou and E. Kani, Simple geometrically split abelian surfaces over finite fields, J. Ramanujan Math. Soc. 29 (1), 31–62 (2014).
[21] H. Stichtenoth, Algebraic Function Fields and Codes (Springer, Heidelberg, 2009) (Grad. Texts Math., Vol. 254). 22. H. Cohen, A Course in Computational Algebraic Number Theory (Springer, Heidelberg, 1993) (Grad. Texts Math., Vol. 138).
[23] W. Stein, SageMath (2021). Available at https://www.sagemath.org (accessed Mar. 11, 2022).
[24] D. Harvey, Kedlaya’s algorithm in larger characteristic, Int. Math. Res. Not. 2007 (22), ID rnm095, 29 p. (2007).
[25] D. Harvey, Hypellfrob (2008).
Available at https://web.maths.unsw.edu.au/~davidharvey/code/hypellfrob (accessed Mar. 11, 2022).
[26] S. A. Novoselov and Yu. F. Boltnev, Characteristic polynomials of the curve $y^2 = x^7 + ax^4 + bx$ over finite fields, Prikl. Diskretn. Mat., Prilozh., No. 12, 44–46 (2019).
[27] S. A. Novoselov, Counting points on hyperelliptic curves with geometrically split Jacobians [poster], in 14th Algorithmic Number Theory Symp., Auckland, New Zealand, June 29–July 4, 2020 (Univ. Auckland, Auckland, 2020). Available at https://www.math.auckland.ac.nz/~sgal018/ANTS/posters/ Novoselov.pdf (accessed Mar. 11, 2022).
