Том 29, номер 2, 2022 г., Стр. 62-79

УДК 519.8+518.25
Новоселов С. А., Болтнев Ю. Ф.
О числе точек на кривой $y^2 = x^7 + ax^4 + bx$ над конечным полем

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

Ключевые слова: гиперэллиптическая кривая, число точек, характеристический многочлен.

DOI: 10.33048/daio.2022.29.726

Новоселов Семён Александрович ¹
Болтнев Юрий Фёдорович ¹
1. Балтийский федеральный университет им. И. Канта,
ул. Александра Невского, 14, 236041 Калининград, Россия
е-mail: snovoselov@kantiana.ru, yuri.boltnev@gmail.com

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

Литература

[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 polynmials 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).