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

DOI:
https://doi.org/10.1090/S0025-5718-96-00751-X

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 th power nonresidues in finite fields , where is prime and is a prime divisor of . We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed and , our algorithm runs in polynomial time. Unlike other deterministic algorithms for this problem, this polynomial-time bound holds even if is exponentially large. More generally, assuming the ERH, in time we can construct a set of elements that generates the multiplicative group . An extended abstract of this paper appeared in *Proc. 23rd Ann. ACM Symp. on Theory of Computing*, 1991.

**1.**L. M. Adleman and H. W. Lenstra Jr., Finding irreducible polynomials over finite fields, In*18th Annual ACM Symposium on Theory of Computing*, pages 350--355, 1986.**2.**L. M. Adleman, K. Manders, and G. L. Miller, On taking roots in finite fields, In*18th Annual Symposium on Foundations of Computer Science*, pages 175--178, 1977.**3.**N. C. Ankeny, The least quadratic nonresidue,*Ann. of Math.*, 55:65--72, 1952. MR**13:538c****4.**E. Bach, Explicit bounds for primality testing and related problems,*Math. Comp.*, 55:355--380, 1990. MR**91m:11096****5.**E. Bach and J. Shallit, Factoring with cyclotomic polynomials,*Math. Comp.*, 52(185):201--219, 1989. MR**89k:11127****6.**E. Bach and J. von zur Gathen, Deterministic factorization of polynomials over special finite fields, Technical Report 799, Computer Sciences Department, University of Wisconsin--Madison, 1988.**7.**E. Bach, J. von zur Gathen, and H. W. Lenstra, Preprint, 1989.**8.**J. Buchmann, On the computation of units and class numbers by a generalization of Lagrange's algorithm,*J. Number Theory*, 26:8--30, 1987. MR**89b:11104****9.**J. Buchmann, On the period length of the generalized Lagrange algorithm,*J. Number Theory*, 26:31--37, 1987. MR**88g:11078****10.**J. Buchmann and H. C. Williams, On principal ideal testing in algebraic number fields,*J. Symbolic Computation*, 4:11--19, 1987. MR**88m:11093****11.**S. A. Evdokimov, Factoring a solvable polynomial over a finite field and Generalized Riemann Hypothesis,*Zapiski Nauchn. Semin. Leningr. Otdel. Matem. Inst. Acad. Sci. USSR*, 176:104--117, 1989. In Russian. MR**91a:11063****12.**J. von zur Gathen, Factoring polynomials and primitive elements for special primes,*Theoret. Comput. Sci.*, 52:77--89, 1987. MR**89a:11126****13.**M. A. Huang, Riemann hypothesis and finding roots over finite fields, In*17th Annual ACM Symposium on Theory of Computing*, pages 121--130, 1985.**14.**G. J. Janusz,*Algebraic Number Fields*, Academic Press, 1973. MR**51:3110****15.**H. W. Lenstra, Finding isomorphisms between finite fields,*Math. Comp.*, 56:329--347, 1991. MR**91d:11151****16.**H. W. Lenstra, Algorithms in algebraic number theory,*Bull. Amer. Math. Soc.*, 26:211--244, 1992. MR**93g:11131****17.**G. I. Perel'muter and I. E. Shparlinsky, On the distribution of primitive roots in finite fields,*Uspekhi Mat. Nauk*, 45:185--186, 1990. In Russian. MR**91d:11152****18.**S. Pohlig and M. Hellman, An improved algorithm for computing logarithms over GF and its cryptographic significance,*IEEE Trans. Inf. Theory*, 24:106--110, 1978. MR**58:4617****19.**L. Rónyai, Factoring polynomials over finite fields,*J. Algorithms*, 9:391--400, 1988. MR**89k:11124****20.**L. Rónyai, Galois groups and factoring polynomials over finite fields, In*30th Annual Symposium on Foundations of Computer Science*, pages 99--104, 1989.**21.**A. Schönhage, The fundamantal theorem of algebra in terms of computational complexity, Unpublished manuscript, 1982.**22.**V. Shoup, Removing randomness from computational number theory (Ph. D. thesis), Technical Report 865, Computer Sciences Department, University of Wisconsin--Madison, 1989.**23.**V. Shoup, New algorithms for finding irreducible polynomials over finite fields,*Math. Comp.*, 54(189):435--447, 1990. MR**90j:11135****24.**V. Shoup, Smoothness and factoring polynomials over finite fields,*Inform. Process. Lett.*, 38:39--42, 1991. MR**92f:11178****25.**V. Shoup, Searching for primitive roots in finite fields,*Math. Comp.*, 58:369--380, 1992. MR**92e:11140****26.**Y. Wang, On the least primitive root of a prime,*Scientia Sinica*, 10(1):1--14, 1961. MR**24:A702**

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:
https://doi.org/10.1090/S0025-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