Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1992-1106981-9
PII: S 0025-5718(1992)1106981-9
Article copyright: © Copyright 1992 American Mathematical Society