Searching for primitive roots in finite fields

Victor Shoup

Research output: Contribution to journalArticlepeer-review

Abstract

Let GF(pn) be the finite field with pn elements, where p is prime. We consider the problem of how to deterministically generate in polynomial time a subset of GF(pn) that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements in GF(pn). We present three results. First, we present a solution to this problem for the case where p is small, i.e., p = nO(1). Second, we present a solution to this problem under the assumption of the Extended Riemann Hypothesis (ERH) for the case where p is large and n = 2. Third, we give a quantitative improvement of a theorem of Wang on the least primitive root for GF(p), assuming the ERH.

Original languageEnglish (US)
Pages (from-to)369-380
Number of pages12
JournalMathematics of Computation
Volume58
Issue number197
DOIs
StatePublished - Jan 1992

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Searching for primitive roots in finite fields'. Together they form a unique fingerprint.

Cite this