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 language | English (US) |
---|---|
Pages (from-to) | 369-380 |
Number of pages | 12 |
Journal | Mathematics of Computation |
Volume | 58 |
Issue number | 197 |
DOIs | |
State | Published - Jan 1992 |
ASJC Scopus subject areas
- Algebra and Number Theory
- Computational Mathematics
- Applied Mathematics