On the construction of finite field elements of large order (Q2566173)

The paper deals with the algorithmic number theory problem of finding elements of large order in a finite field. Such high-order elements, in particular primitive elements, are needed in applications such as Public Key Cryptography. However if the prime factorization of the order of the multiplicative group of the field is unknown it is a hard problem to find a primitive element. In this paper the author discusses some techniques to find elements of order greater than a certain bound (without computing the exact order of such elements). So Section 3 describes a polynomial time algorithm due to \textit{S. Gao} [Proc. Am. Math. Soc. 127, 1615--1623 (1999; Zbl 0923.11166)] which for a given prime power \(q\)\, and an integer \(n\) finds an element in \(\mathbb F_{q^n}\) of order at least \(n^{\frac{\log_q n}{4\log_q(2\log_q n)}-1/2}\). If the field has additional structures the method allows to construct an element of order greater than \(q^{n^c}\)\, for some constant \(c\). Section 4 studies an algorithm proposed by \textit{J. von zur Gathen} and \textit{I. Shparlinski} (based on the properties of Gauss periods) [AAECC-13, Lect. Notes Comput. Sci. 1719, 404--409 (1999; Zbl 0985.11067)] that given \(q\) and a natural number \(N\) finds, in time polynomial on \(N\), an integer \(n=N+O(N/\log^c N)\) and \(\alpha \in \mathbb F_{q^n}\) of order at least \(2^{10q^{-12}n^{1/2}-25}\). Finally Section 5 deals with a new author's technique (related with his improvement of the AKS primality algorithm [CRYPTO 2003, Lect. Notes Comput. Sci. 2729, 338--348 (2003; Zbl 1122.68456)]). He proves that given \(q\), for large enough \(N\) it is possible to compute, in time polynomial on \(N\), an integer \(n\in [N, N+O(N^{0'77})]\) and an element \(\beta\in \mathbb F_{q^n}\) with order greater than \(5.8^{\sqrt{n}}\).