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)

 

Constructing nonresidues in finite fields
and the extended Riemann hypothesis


Authors: Johannes Buchmann and Victor Shoup
Journal: Math. Comp. 65 (1996), 1311-1326
MSC (1991): Primary 11Y16
MathSciNet review: 1348040
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new deterministic algorithm for the problem of constructing $k$th power nonresidues in finite fields $% \mathbf {F}_{p^n}$, where $p$ is prime and $k$ is a prime divisor of $p^n-1$. We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed $n$ and $p \rightarrow \infty $, our algorithm runs in polynomial time. Unlike other deterministic algorithms for this problem, this polynomial-time bound holds even if $k$ is exponentially large. More generally, assuming the ERH, in time $(n \log p)^{O(n)}$ we can construct a set of elements that generates the multiplicative group $% \mathbf {F}_{p^n}^*$. An extended abstract of this paper appeared in Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991.


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


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y16

Retrieve articles in all journals with MSC (1991): 11Y16


Additional Information

Johannes Buchmann
Affiliation: Universität des Saarlandes, Fb 14 – Informatik, PF 151150, 66041 Saarbrücken, Germany

Victor Shoup
Affiliation: Bellcore, 445 South St., Morristown, New Jersey 07960

DOI: http://dx.doi.org/10.1090/S0025-5718-96-00751-X
PII: S 0025-5718(96)00751-X
Received by editor(s): March 19, 1993
Received by editor(s) in revised form: February 12, 1995
Additional Notes: This research was done while the second author was a postdoctoral fellow at the University of Toronto.
Article copyright: © Copyright 1996 American Mathematical Society