Finding primitive elements in finite fields of small characteristic
Ming-Deh A. Huang, Anand Kumar Narayanan · Contemporary mathematics - American Mathematical Society · 2015
We describe a deterministic algorithm for finding a generator of the multiplicative group of the finite field with p n p^n elements. In time polynomial in p p and n n , the algorithm either outputs an element that is provably a generator or declares that it has failed in finding one. Under a heuristic assumption, we argue that the algorithm does always succeed in finding a generator. The algorithm relies on a relation generation technique in a recent breakthrough by Antoine Joux’s for discrete logarithm computation in small characteristic finite fields in L ( 1 / 4 , o ( 1 ) ) L(1/4,o(1)) time. For the special case when the order of p p in ( Z / n Z ) × (\mathbb Z/n\mathbb Z)^\times is small (bounded by ( log p n ) O ( 1 ) (\log _pn)^{\mathcal {O}(1)} ), we present a modified algorithm which is reliant on weaker heuristic assumptions.