О числе точек на кривой y2=x7+ax4+bx над конечным полем

О числе точек на кривой $y^2 = x^7 + ax^4 + bx$ над конечным полем

Новоселов С. А., Болтнев Ю. Ф.
Дискретный анализ и исследование операций, 29, 2, 62-79 (2022)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2022.29.726

Аннотация:

Представлены явные формулы для числа точек на гиперэллиптической кривой рода $3$ вида $y^2 = x^7 + ax^4 + bx$ над конечным полем $\mathbb {F}_q$ характеристики $p > 3$. Как следствие, показано, что задача подсчёта точек на данном классе кривых имеет сложность $O(log^{4} q)$ битовых операций. 
Табл. 2, библиогр. 27.

Литература:
  1. ГОСТ 34.10-2018. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. Введ. 01.06.2019. М.: Стандартинформ, 2018. 21 с.
     
  2. FIPS 186-4. Digital signature standard (DSS). Gaithersburg, MD: NIST, 2013. Available at https://doi.org/10.6028/NIST.FIPS.186-4 (accessed Mar. 9, 2022).
     
  3. Koblitz N. Hyperelliptic cryptosystems // J. Cryptol. 1989. V. 1, No. 3. P. 139–150.
     
  4. Handbook of elliptic and hyperelliptic curve cryptography. Boca Raton, FL: Chapman Hall/CRC, 2006. 808 p.
     
  5. Schoof R. Counting points on elliptic curves over finite fields // J. Théor. Nombres Bordx. 1995. V. 7, No. 1. P. 219–254.
     
  6. Abelard S., Gaudry P., Spaenlehauer P. J. Improved complexity bounds for counting points on hyperelliptic curves // Found. Comput. Math. 2019. V. 19, No. 3. P. 591–621.
     
  7. Gaudry P., Schost É. Genus 2 point counting over prime fields // J. Symb. Comput. 2012. V. 47, No. 4. P. 368–400.
     
  8. Abelard S. Counting points on hyperelliptic curves in large characteristic: Algorithms and complexity : PhD thes. Nancy: Univ. Lorraine, 2018.
     
  9. Dobson S., Galbraith S. D., Smith B. Trustless unknown-order groups // J. Math. Cryptol. [in print].
     
  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). Pt. I. Cham: Springer, 2018. P. 757–788. (Lect. Notes Comput. Sci.; V. 10991).
     
  11. Rivest R. L., Shamir A., Wagner D. A. Time-lock puzzles and timed-release Crypto. Tech. rep. MIT-LCS-TR-684. Cambridge, MA: MIT, 1996. 9 p.
     
  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). Heidelberg: Springer, 1994. P. 274–285. (Lect. Notes Comput. Sci.; V. 765).
     
  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). Heidelberg: Springer, 2009. P. 536–553. (Lect. Notes Comput. Sci.; V. 5479).
     
  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). Heidelberg: Springer, 2013. P. 234–253. (Lect. Notes Comput. Sci.; V. 7708).
     
  15. Novoselov S. A. Counting points on hyperelliptic curves of type $y^2 = x^{2g+1} +  ax^{g+1} + bx$ // Finite Fields Appl. 2020. V. 68, ID 101757. 27 p.
     
  16. Mumford D. Abelian varieties. Oxford: Oxford Univ. Press, 1974.
     
  17. Tate J. Endomorphisms of Abelian varieties over finite fields // Invent. Math. 1966. V. 2, No. 2. P. 134–144.
     
  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. Singapore: World Sci., 2016. P. 1–10.
     
  19. Singh V., McGuire G., Zaytsev A. Classification of characteristic polynomials of simple supersingular Abelian varieties over finite fields // Funct. Approximatio, Comment. Math. 2014. V. 51, No. 2. P. 415–436.
     
  20. Chou K. M. J., Kani E. Simple geometrically split Abelian surfaces over finite fields //J. Ramanujan Math. Soc. 2014. V. 29, No. 1. P. 31-62.
     
  21. Stichtenoth H. Algebraic function fields and codes. Heidelberg: Springer, 2009. (Grad. Texts Math.; V. 254).
     
  22. Cohen H. A course in computational algebraic number theory. Heidelberg: Springer, 1993. (Grad. Texts Math.; V. 138).
     
  23. Stein W. SageMath. 2021. Available at https://www.sagemath.org (accessed Mar. 11, 2022).
     
  24. Harvey D. Kedlaya’s algorithm in larger characteristic // Int. Math. Res. Not. 2007. V. 2007, No. 22, ID rnm095. 29 p.
     
  25. Harvey D. Hypellfrob. 2008. Available at https://web.maths.unsw.edu.au/~davidharvey/code/hypellfrob (accessed Mar. 11, 2022).
     
  26. Novoselov S. A., Boltnev Yu. F. Characteristic polynomials of the curve $y^2 = x^7 + ax^4 + bx$ over finite fields // Прикл. дискрет. математика. Прил. 2019. № 12. С. 44–46.
     
  27. Novoselov S. A. Counting points on hyperelliptic curves with geometrically split Jacobians [poster] // 14th Algorithmic Number Theory Symp. (Auckland, New Zealand, June 29–July 4, 2020). Auckland: Univ. Auckland, 2020. Available at https://www.math.auckland.ac.nz/~sgal018/ANTS/posters/Novoselov.pdf (accessed Mar. 11, 2022).

Работа первого автора выполнена при финансовой поддержке Минобрнауки РФ (соглашение № 075–02–2022–872).

Новоселов Семён Александрович
  1. Балтийский федеральный университет им. И. Канта,
    ул. Александра Невского, 14, 236041 Калининград, Россия

E-mail: snovoselov@kantiana.ru

Болтнев Юрий Фёдорович
  1. Балтийский федеральный университет им. И. Канта,
    ул. Александра Невского, 14, 236041 Калининград, Россия

E-mail: yuri.boltnev@gmail.com

Статья поступила 31 октября 2021 г. 
После доработки — 31 января 2022 г. 
Принята к публикации 7 февраля 2022 г.

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.

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 Pairing-Based 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).