Geodesic
On the number of points on the curve $y^2 = x^{7} + ax^4 + bx$ over a finite field
Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 2, pp. 62-79.

Voir la notice de l'article provenant de la source Math-Net.Ru

We provide explicit formulae for the number of points on a genus $3$ hyperelliptic curve of type $y^2 = x^{7} + a x^{3} + b x$ 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. 
@article{DA_2022_29_2_a3,
     author = {S. A. Novoselov and Yu. F. Boltnev},
     title = {On the number of points on the curve $y^2 = x^{7} + ax^4 + bx$ over a finite field},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {62--79},
     publisher = {mathdoc},
     volume = {29},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2022_29_2_a3/}
}
TY  - JOUR
AU  - S. A. Novoselov
AU  - Yu. F. Boltnev
TI  - On the number of points on the curve $y^2 = x^{7} + ax^4 + bx$ over a finite field
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2022
SP  - 62
EP  - 79
VL  - 29
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2022_29_2_a3/
LA  - ru
ID  - DA_2022_29_2_a3
ER  - 
%0 Journal Article
%A S. A. Novoselov
%A Yu. F. Boltnev
%T On the number of points on the curve $y^2 = x^{7} + ax^4 + bx$ over a finite field
%J Diskretnyj analiz i issledovanie operacij
%D 2022
%P 62-79
%V 29
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2022_29_2_a3/
%G ru
%F DA_2022_29_2_a3
S. A. Novoselov; Yu. F. Boltnev. On the number of points on the curve $y^2 = x^{7} + ax^4 + bx$ over a finite field. Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 2, pp. 62-79. http://geodesic.mathdoc.fr/item/DA_2022_29_2_a3/

[1] Information technology. Cryptographic data security. Signature and verification processes of electronic digital signature, GOST 34.10–2018, Standartinform, M., 2018 (Russian)

[2] FIPS 186-4. Digital signature standard (DSS), NIST, Gaithersburg, MD, 2013 (Available at accessed Mar. 9, 2022) | DOI

[3] Koblitz N., “Hyperelliptic cryptosystems”, J. Cryptol., 1:3 (1989), 139–150 | DOI | MR | Zbl

[4] Handbook of elliptic and hyperelliptic curve cryptography, Chapman Hall/CRC, Boca Raton, FL, 2006, 808 pp. | Zbl

[5] Schoof R., “Counting points on elliptic curves over finite fields”, J. Théor. Nombres Bordx., 7:1 (1995), 219–254 | DOI | MR | Zbl

[6] Abelard S., Gaudry P., Spaenlehauer P. J., “Improved complexity bounds for counting points on hyperelliptic curves”, Found. Comput. Math., 19:3 (2019), 591–621 | DOI | MR | Zbl

[7] Gaudry P., Schost É., “Genus $2$ point counting over prime fields”, J. Symb. Comput., 47:4 (2012), 368–400 | DOI | MR | Zbl

[8] Abelard S., Counting points on hyperelliptic curves in large characteristic: Algorithms and complexity, PhD thes., Univ. Lorraine, Nancy, 2018

[9] Dobson S., Galbraith S. D., Smith B., “Trustless unknown-order groups”, J. Math. Cryptol. (to appear)

[10] Boneh D., Bonneau J., Bünz B., Fisch B., “Verifiable delay functions”, Advances in cryptology – CRYPTO 2018, Proc. 38th Annu. Int. Cryptol. Conf. (Santa Barbara, CA, USA, Aug. 19–23, 2018), v. I, Lect. Notes Comput. Sci., 10991, Springer, Cham, 2018, 757–788 | DOI | MR | Zbl

[11] Rivest R. L., Shamir A., Wagner D. A., Time-lock puzzles and timed-release Crypto, Tech. rep. MIT-LCS-TR-684, MIT, Cambridge, MA, 1996, 9 pp.

[12] Benaloh J., de Mare M., “One-way accumulators: A decentralized alternative to digital signatures”, Advances in cryptology – EUROCRYPT'93, Proc. Workshop Theory Appl. Cryptogr. Tech. (Lofthus, Norway, May 23–27, 1993), Lect. Notes Comput. Sci., 765, Springer, Heidelberg, 1994, 274–285 | DOI | MR | Zbl

[13] Satoh T., “Generating genus two hyperelliptic curves over large characteristic finite fields”, Advances in cryptology – EUROCRYPT 2009, Proc. 28th Annu. Int. Conf. Theory Appl. Cryptogr. Tech. (Cologne, Germany, Apr. 26–30, 2009), Lect. Notes Comput. Sci., 5479, Springer, Heidelberg, 2009, 536–553 | DOI | MR | Zbl

[14] Guillevic A., Vergnaud D., “Genus $2$ hyperelliptic curve families with explicit Jacobian order evaluation and pairing-friendly constructions”, Pairing-based cryptography – Pairing 2012, Rev. Sel. Pap. 5th Int. Conf. (Cologne, Germany, May 16–18, 2012), Lect. Notes Comput. Sci., 7708, Springer, Heidelberg, 2013, 234–253 | DOI | MR | Zbl

[15] Novoselov S. A., “Counting points on hyperelliptic curves of type $y^2 = x^{2g+1} + ax^{g+1} + bx$”, Finite Fields Appl., 68 (2020), 101757, 27 pp. | DOI | MR | Zbl

[16] Mumford D., Abelian varieties, Oxford Univ. Press, Oxford, 1974 | MR | Zbl

[17] Tate J., “Endomorphisms of Abelian varieties over finite fields”, Invent. Math., 2:2 (1966), 134–144 | DOI | MR | Zbl

[18] Blanco-Chacón I., Chapman R., Fordham S., McGuire G., “Divisibility of L-polynomials for a family of curves”, Contemporary Developments in Finite Fields and Applications, World Sci, Singapore, 2016, 1–10 | MR | Zbl

[19] Singh V., McGuire G., Zaytsev A., “Classification of characteristic polynomials of simple supersingular Abelian varieties over finite fields”, Funct. Approximatio, Comment. Math., 51:2 (2014), 415–436 | MR | Zbl

[20] Chou K. M. J., Kani E., “Simple geometrically split Abelian surfaces over finite fields”, J. Ramanujan Math. Soc., 29:1 (2014), 31–62 | MR | Zbl

[21] Stichtenoth H., Algebraic function fields and codes, Grad. Texts Math., 254, Springer, Heidelberg, 2009 | DOI | MR | Zbl

[22] Cohen H., A course in computational algebraic number theory, Grad. Texts Math., 138, Springer, Heidelberg, 1993 | DOI | MR | Zbl

[23] Stein W., SageMath, , 2021 (Available at accessed Mar. 11, 2022) https://www.sagemath.org

[24] Harvey D., “Kedlaya's algorithm in larger characteristic”, Int. Math. Res. Not., 2007:22 (2007), rnm095, 29 pp. | MR | Zbl

[25] Harvey D., Hypellfrob, , 2008 (Available at accessed Mar. 11, 2022) https://web.maths.unsw.edu.au/d̃avidharvey/code/hypellfrob

[26] Novoselov S. A., Boltnev Yu. F., “Characteristic polynomials of the curve $y^2=x^7+ax^4+bx$ over finite fields”, Prikl. diskret. matematika. Pril., 2019, no. 12, 44–46

[27] Novoselov S. A., 14th Algorithmic Number Theory Symp., poster (Auckland, New Zealand, June 29–July 4, 2020), Univ. Auckland, Auckland, 2020 (Available at accessed Mar. 11, 2022) https://www.math.auckland.ac.nz/s̃gal018/ANTS/posters/Novoselov.pdf