Elements of provable high orders in finite fields (Q4235576)

It is a well-known open problem to find an efficient algorithm for constructing primitive elements in finite fields. While this problem appears to be very difficult, in practice it is usually sufficient to be able to find elements of ``high order'' efficiently, where by an element of high order in \(GF(q^n)\) we mean an element whose order is larger than any polynomial in \(n \log q\) as \(q^n \to \infty\). The method proposed in this paper for solving the latter problem is the following. Fix \(q\) and let \(\overline n\) be the smallest power of \(q\) that is bigger than or equal to \(n\). For each polynomial \(g (x) \in GF ( q) [x]\) of degree at most \(2\log_q n\), check if \(x^{\overline n}- g (x)\) has an irreducible factor of degree \(n\). If so, terminate the algorithm. Then any root of such an irreducible factor is shown to be an element of \(GF (q^n)\) of high order. Moreover, this algorithm runs in polynomial time for fixed \(q\). Computer data for \(q=2\) and \(n \leq 300\) verifies the existence of a polynomial \(g (x) \in GF (2) [x]\) of degree at most \(2\log_2n\) such that \(x^{\overline n}- g (x)\) has an irreducible factor of degree \(n\). It is conjectured that this is always the case for any prime power \(q\) and any integer \(n > 1\). It is also shown in this paper by a relatively straightforward inclusion/exclusion argument that the probability of a random polynomial in \(GF(q)[x]\) of degree \(m \geq n\) having at least one irreducible factor of degree \(n\) is asymptotically \({1\over n}\) as \(n \to \infty\), uniformly for \(q\) and \(m \geq n\).