Abstract
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.