Elements of provable high orders in finite fields
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\).
- Finite field elements of high order arising from modular curves
- The dynamics of permutations on irreducible polynomials
- The existence of \(\mathbb{F}_q\)-primitive points on curves using freeness
- On multiplicative independence of rational function iterates
- Sharpening of the explicit lower bounds for the order of elements in finite field extensions based on cyclotomic polynomials
- Existence results on \(k\)-normal elements over finite fields
- On multiplicative dependence of values of rational functions and a generalization of the Northcott theorem
- On the multiplicative order of the roots of \(bX^{q^r + 1} - aX^{q^r} + dX - c\)
- Generating sets for the multiplicative groups of algebras over finite fields and expander graphs
- Elements of high order in Artin-Schreier extensions of finite fields
- Irreducible polynomials with consecutive zero coefficients
- On the construction of finite field elements of large order
- Constructing normal bases in finite fields
- High order elements in finite fields arising from recursive towers
- On \(r\)-primitive \(k\)-normal elements over finite fields
- scientific article; zbMATH DE number 1588463 (Why is no real title available?)
- Elements of high order on finite fields from elliptic curves
- Elements of high order in finite fields of the form
- The translate and line properties for 2-primitive elements in quadratic extensions
- Elements of high order in finite fields specified by binomials
- Normal high order elements in finite field extensions based on the cyclotomic polynomials
- Finite field extensions with the line or translate property for \(r\)-primitive elements
- On construction of high order elements in arbitrary finite fields
- Elements of high order in Artin-Schreier extensions of finite fields \(\mathbb{F}_q\)
- On the order of points on curves over finite fields
- Constructing finite field extensions with large order elements
- Constructing high order elements through subspace polynomials
- Groups generated by iterations of polynomials over finite fields
- Pairs of \(r\)-primitive and \(k\)-normal elements in finite fields
- r -primitive k -normal elements in arithmetic progressions over finite fields
- Arithmetic progressions of \(r\)-primitive elements in a field
- Multiplicative dependence of rational values modulo approximate finitely generated groups
- Characteristic functions of (r,n)-free and (f,g)-elements of finite cyclic modul
- Search of primitive polynomials over finite fields
This page was built for publication: Elements of provable high orders in finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4235576)
