Finding Primitive Elements in Finite Fields of Small Characteristic

Abstract

We describe a deterministic algorithm for finding a generating element of the multiplicative group of the finite field ${\mathbb{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 Joux's 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 $(\mathbb{Z}/n\mathbb{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.

Modifications made to the polynomial selection and testing phases