RESEARCH OF ALGORITHMS FOR SEARCHING PRIMITIVE ELEMENTS OF A FINITE FIELD OF HIGH ORDER

ЖОҒАРЫ РЕТТІ АҚЫРЛЫ ӨРІСТІҢ ПРИМИТИВТІ ЭЛЕМЕНТТЕРІН ІЗДЕУ АЛГОРИТМДЕРІН ЗЕРТТЕУ
ИССЛЕДОВАНИЕ АЛГОРИТМОВ ПОИСКА ПРИМИТИВНЫХ ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ БОЛЬШОГО ПОРЯДКА
Turusbekova U.K. Muratbekov M.M. Altynbek S.A.
2024 Kazakh-British Technical University

Herald of the Kazakh British Technical UNiversity
2024 #21 Issue 1 85 - 93 pp.

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 field , Gauss periods , prime number , primitive element , simple factorization

Text of the article Перейти на текст статьи

Esil University, Astana, 010000, Kazakhstan
L.N. Gumilyov, Eurasian National University, Astana, 010008, Kazakhstan
Kazakh University of Technology and Business, Astana, 010000, Kazakhstan

Esil University
L.N. Gumilyov
Kazakh University of Technology and Business

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026