# Finding Primitive Elements in Finite Fields of Small Characteristic

We describe a deterministic algorithm for finding a generating element of the multiplicative group of the finite field $\F {p^n}$ where $p$ is a prime. In time polynomial in $p$ and $n$, the algorithm either outputs an element that is provably a generator or declares that it has failed in finding one. The algorithm relies on a relation generation technique in Jouxs heuristically $L(1-4)$-method for discrete logarithm computation. Based on a heuristic assumption, the algorithm does succeed in finding a generator. For the special case when the order of $p$ in $(\Z-n\Z)^\times$ is small (that is $(\log p(n))^{\mathcal{O}(1)}$), we present a modification with greater guarantee of success while making weaker heuristic assumptions.

Author: Ming-Deh Huang; Anand Kumar Narayanan

Source: https://archive.org/