kaz29Вестник Казахстанско-Британского технического университетаHerald of the Kazakh-British Technical University1998-66882959-8109Казахстанско-Британский Технический Университет10.55452/1998-6688-2024-21-1-85-93kaz29-1025Research ArticleМАТЕМАТИЧЕСКИЕ НАУКИMATHEMATICAL SCIENCESИССЛЕДОВАНИЕ АЛГОРИТМОВ ПОИСКА ПРИМИТИВНЫХ ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ БОЛЬШОГО ПОРЯДКАRESEARCH OF ALGORITHMS FOR SEARCHING PRIMITIVE ELEMENTS OF A FINITE FIELD OF HIGH ORDERhttps://orcid.org/0000-0002-0591-2143ТурусбековаУ. К.TurusbekovaU. K.

PhD

010000, г. Астана

PhD

010000, Astana

   

umut.t@mail.ruhttps://orcid.org/0000-0003-2197-4982МуратбековМ. М.MuratbekovM. M.

PhD

010008, г. Астана

PhD

010008, Astana

Madimm@list.ruhttps://orcid.org/0000-0002-8435-7773АлтынбекС. А.AltynbekS. A.

PhD

010000, г. Астана

PhD

010000, Astana

serik_aa@bk.ruEsil UniversityКазахстанEsil UniversityKazakhstanЕвразийский национальный университет им. Л.Н. ГумилеваКазахстанL.N. Gumilyov Eurasian National UniversityKazakhstanКазахский университет технологии и бизнесаКазахстанKazakh University of Technology and BusinessKazakhstan2024250320242118593Copyright © Турусбекова У.К., Муратбеков М.М., Алтынбек С.А., 20242024Турусбекова У.К., Муратбеков М.М., Алтынбек С.А.Turusbekova U.K., Muratbekov M.M., Altynbek S.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.kbtu.edu.kz/jour/article/view/1025

Одной из наиболее важных нерешенных и заведомо трудных задач в вычислительной теории конечных полей является разработка быстрого алгоритма для построения примитивных корней в конечном поле. С другой стороны, для многих приложений вместо примитивного корня достаточно элемента высокого мультипликативного порядка. Такие приложения включают, помимо прочего, криптографию, теорию кодирования, генерацию псевдослучайных чисел и комбинаторные схемы. Явные построения элементов высокого порядка обычно полагаются на методы комбинаторики, которые могут обеспечить доказуемую нижнюю границу порядка, но не вычисляют его точный порядок. Выполнение таких построений обычно основано на том, что факторизация порядка уже известна. В идеале мы должны иметь возможность получить примитивный элемент для любого конечного поля за разумное время. Однако если простая факторизация порядка группы неизвестна, этого сложно добиться. Таким образом, ставят менее амбициозную задачу – задачу построения элемента достаточно высокого порядка. В данной статье мы рассматриваем различные алгоритмы, которые находят элемент высокого порядка как для общих, так и для специальных конечных полей. Кроме того, в этой работе мы касаемся теории периодов Гаусса над конечными полями, их обобщениями и аналогами, которые, как известно, уже доказали свою полезность для ряда различных приложений.

One of the most important unsolved and notoriously difficult problems in computational finite field theory is the development of a fast algorithm for constructing primitive roots in a finite field. It is known that for many applications, instead of a primitive root, just an element of high multiplicative order is sufficient. Such applications include, but are not limited to, cryptography, coding theory, pseudorandom number generation, and combinatorial schemes. Explicit constructions of high-order elements usually rely on combinatory methods that can provide a provable lower bound on the order, but this does not compute the exact order. Its execution usually implies knowledge of the factorization of the order. Ideally, we should be able to get a primitive element for any finite field in a reasonable amount of time. However, if the simple factorization of the group order is unknown, it is difficult to achieve the goal. Thus, we set the task of constructing an element, probably of a high order. This article discusses various algorithms that find a high-order element for general or special finite fields. This work also represents another contribution to the theory of Gauss periods over finite fields and their generalizations and analogues, which have already proven their usefulness for a number of different applications.

конечное полепримитивный элементпростое числопростая факторизацияпериоды Гауссаfinite fieldprimitive elementprime numbersimple factorizationGauss periodsРабота выполнена при поддержке Министерства науки и высшего образования Республики Казахстан в рамках проекта AP19677733 «Разработка интеллектуальной распределенной системы параллельного анализа научных текстов», за что авторы выражают огромную благодарность.ReferencesPrachar K. Primzahlverteilung, Springer, Berlin, 1957, pp. 77, doi: https://doi.org/10.2307/3608911.Prachar K. Primzahlverteilung, Springer, Berlin, 1957, pp. 77, doi: https://doi.org/10.2307/3608911.Wang Y. On the least primitive root of a prime, Acta Math. Sinica, 9, 1959, pp. 432–441. (English translation in Sci. Sinica 10 (1961)).Wang Y. On the least primitive root of a prime, Acta Math. Sinica, 9, 1959, pp. 432–441. (English translation in Sci. Sinica 10 (1961)).Shoup V. Searching for primitive roots in finite fields, Math. Comp., 58, 1992, pp. 369–380.Shoup V. Searching for primitive roots in finite fields, Math. Comp., 58, 1992, pp. 369–380.Bach E. Comments on search procedures for primitive roots, Math. Comp., 66(220), 1997, pp. 1719– 1727.Bach E. Comments on search procedures for primitive roots, Math. Comp., 66(220), 1997, pp. 1719– 1727.Shparlinski I.E. On finding primitive roots in finite fields, Theoret. Comput. Sci., 157, 1997, pp. 273– 275.Shparlinski I.E. On finding primitive roots in finite fields, Theoret. Comput. Sci., 157, 1997, pp. 273– 275.Shparlinski I.E. Finite fields: Theory and computation, Kluwer Academic Publishers, Dordrecht, 1999.Shparlinski I.E. Finite fields: Theory and computation, Kluwer Academic Publishers, Dordrecht, 1999.Gao S. Elements of provable high orders in finite fields, Proc. Amer. Math. Soc., 127, 1999, pp.1615– 1623.Gao S. Elements of provable high orders in finite fields, Proc. Amer. Math. Soc., 127, 1999, pp.1615– 1623.Conflitti A. On elements of high order in finite fields, in: Cryptography and Computational Number Theory, Birkhauser, Basel, 2001, pp. 11–14.Conflitti A. On elements of high order in finite fields, in: Cryptography and Computational Number Theory, Birkhauser, Basel, 2001, pp. 11–14.Von zur Gathen J. and Shparlinski I. Orders of Gauss periods in finite fields, Applicable Algebra in Engineering, Comm. Comput., 9, 1999, pp.15–24.Von zur Gathen J. and Shparlinski I. Orders of Gauss periods in finite fields, Applicable Algebra in Engineering, Comm. Comput., 9, 1999, pp.15–24.Von zur Gathen J. and Shparlinski I. Constructing elements of large order in finite fields, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: AAECC-13, Lecture Notes in Computer Science, Springer, Berlin, 1719, 1999, pp. 404–409.Von zur Gathen J. and Shparlinski I. Constructing elements of large order in finite fields, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: AAECC-13, Lecture Notes in Computer Science, Springer, Berlin, 1719, 1999, pp. 404–409.Von zur Gathen and Shparlinski I. Gauss periods in finite fields, Proceedings of the Fifth Conference of Finite Fields and their Applications, Springer, Berlin, 1999, P. 162–177.Von zur Gathen and Shparlinski I. Gauss periods in finite fields, Proceedings of the Fifth Conference of Finite Fields and their Applications, Springer, Berlin, 1999, P. 162–177.Cheng Q. Constructing finite field extensions with large order elements, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004, pp. 1123–1124, https://doi.org/10.1137/S0895480104445514.Cheng Q. Constructing finite field extensions with large order elements, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004, pp. 1123–1124, https://doi.org/10.1137/S0895480104445514.Cheng Q. Primality proving via one round in ECPP and one iteration in AKS, D. Boneh (Ed.), Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO), Lecture Notes in Computer Science, Santa Barbara, Springer, Berlin, 2729, 2003, pp. 338–348.Cheng Q. Primality proving via one round in ECPP and one iteration in AKS, D. Boneh (Ed.), Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO), Lecture Notes in Computer Science, Santa Barbara, Springer, Berlin, 2729, 2003, pp. 338–348.Voloch J.F. On some subgroups of the multiplicative group of finite rings, 2003, http://www.ma.utexas.edu/users/voloch/preprint.html.Voloch J.F. On some subgroups of the multiplicative group of finite rings, 2003, http://www.ma.utexas.edu/users/voloch/preprint.html.Shparlinski I.E. On constructing primitive roots in finite fields with advice. IEEE Trans. Inform. Theory, 64, 2018, pp. 7132–7136.Shparlinski I.E. On constructing primitive roots in finite fields with advice. IEEE Trans. Inform. Theory, 64, 2018, pp. 7132–7136.Bhowmick A. and Lê T. H. On primitive elements in finite fields of low characteristic, Finite Fields Appl., 35, 2015, pp. 64–77.Bhowmick A. and Lê T. H. On primitive elements in finite fields of low characteristic, Finite Fields Appl., 35, 2015, pp. 64–77.

The authors declare that there are no conflicts of interest present.