Searching for primitive roots in finite fields

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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)
Title of host publicationProc 22nd Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages546-554
Number of pages9
ISBN (Print)0897913612, 9780897913614
DOIs
StatePublished - 1990
EventProceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA
Duration: May 14 1990May 16 1990

Publication series

NameProc 22nd Annu ACM Symp Theory Comput

Other

OtherProceedings of the 22nd Annual ACM Symposium on Theory of Computing
CityBaltimore, MD, USA
Period5/14/905/16/90

ASJC Scopus subject areas

  • Engineering(all)

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

  • Cite this

    Shoup, V. (1990). Searching for primitive roots in finite fields. In Proc 22nd Annu ACM Symp Theory Comput (pp. 546-554). (Proc 22nd Annu ACM Symp Theory Comput). Publ by ACM. https://doi.org/10.1145/100216.100293