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?)

  • 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$(p)$ 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

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

American Mathematical Society