Remote Access Mathematics of Computation
Green Open Access

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

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