Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Searching for primitive roots in finite fields

Author: Victor Shoup
Journal: Math. Comp. 58 (1992), 369-380
MSC: Primary 11T06; Secondary 11Y16
MathSciNet review: 1106981
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ {\text{GF}}({p^n})$ be the finite field with $ {p^n}$ elements, where p is prime. We consider the problem of how to deterministically generate in polynomial time a subset of $ {\text{GF}}({p^n})$ that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements in $ {\text{GF}}({p^n})$. We present three results. First, we present a solution to this problem for the case where p is small, i.e., $ p = {n^{O(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 $ {\text{GF}}(p)$, assuming the ERH.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T06, 11Y16

Retrieve articles in all journals with MSC: 11T06, 11Y16

Additional Information

Article copyright: © Copyright 1992 American Mathematical Society