Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
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

PII: S 0025-5718(1992)1106981-9
Article copyright: © Copyright 1992 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia