## Constructing nonresidues in finite fields and the extended Riemann hypothesis

HTML articles powered by AMS MathViewer

- by Johannes Buchmann and Victor Shoup PDF
- Math. Comp.
**65**(1996), 1311-1326 Request permission

## 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

- 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. - 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. - C. J. Everett Jr.,
*Annihilator ideals and representation iteration for abstract rings*, Duke Math. J.**5**(1939), 623–627. MR**13** - Eric Bach,
*Explicit bounds for primality testing and related problems*, Math. Comp.**55**(1990), no. 191, 355–380. MR**1023756**, DOI 10.1090/S0025-5718-1990-1023756-8 - Eric Bach and Jeffrey Shallit,
*Factoring with cyclotomic polynomials*, Math. Comp.**52**(1989), no. 185, 201–219. MR**947467**, DOI 10.1090/S0025-5718-1989-0947467-1 - 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.
- E. Bach, J. von zur Gathen, and H. W. Lenstra, Preprint, 1989.
- Johannes Buchmann,
*On the computation of units and class numbers by a generalization of Lagrange’s algorithm*, J. Number Theory**26**(1987), no. 1, 8–30. MR**883530**, DOI 10.1016/0022-314X(87)90092-8 - Johannes Buchmann,
*On the period length of the generalized Lagrange algorithm*, J. Number Theory**26**(1987), no. 1, 31–37. MR**883531**, DOI 10.1016/0022-314X(87)90093-X - Johannes Buchmann and H. C. Williams,
*On principal ideal testing in algebraic number fields*, J. Symbolic Comput.**4**(1987), no. 1, 11–19. MR**908408**, DOI 10.1016/S0747-7171(87)80049-4 - S. A. Evdokimov,
*Factorization of a solvable polynomial over finite fields and the generalized Riemann hypothesis*, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI)**176**(1989), no. Teor. Slozhn. Vychisl. 4, 104–117, 153 (Russian, with English summary); English transl., J. Soviet Math.**59**(1992), no. 3, 842–849. MR**1023599**, DOI 10.1007/BF01104107 - Joachim von zur Gathen,
*Factoring polynomials and primitive elements for special primes*, Theoret. Comput. Sci.**52**(1987), no. 1-2, 77–89. MR**918114**, DOI 10.1016/0304-3975(87)90081-8 - M. A. Huang, Riemann hypothesis and finding roots over finite fields, In
*17th Annual ACM Symposium on Theory of Computing*, pages 121–130, 1985. - Gerald J. Janusz,
*Algebraic number fields*, Pure and Applied Mathematics, Vol. 55, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR**0366864** - H. W. Lenstra Jr.,
*Finding isomorphisms between finite fields*, Math. Comp.**56**(1991), no. 193, 329–347. MR**1052099**, DOI 10.1090/S0025-5718-1991-1052099-2 - H. W. Lenstra Jr.,
*Algorithms in algebraic number theory*, Bull. Amer. Math. Soc. (N.S.)**26**(1992), no. 2, 211–244. MR**1129315**, DOI 10.1090/S0273-0979-1992-00284-7 - G. I. Perel′muter and I. E. Shparlinskiĭ,
*Distribution of primitive roots in finite fields*, Uspekhi Mat. Nauk**45**(1990), no. 1(271), 185–186 (Russian); English transl., Russian Math. Surveys**45**(1990), no. 1, 223–224. MR**1050940**, DOI 10.1070/RM1990v045n01ABEH002330 - Stephen C. Pohlig and Martin E. Hellman,
*An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance*, IEEE Trans. Inform. Theory**IT-24**(1978), no. 1, 106–110. MR**484737**, DOI 10.1109/tit.1978.1055817 - Lajos Rónyai,
*Factoring polynomials over finite fields*, J. Algorithms**9**(1988), no. 3, 391–400. MR**955147**, DOI 10.1016/0196-6774(88)90029-6 - L. Rónyai, Galois groups and factoring polynomials over finite fields, In
*30th Annual Symposium on Foundations of Computer Science*, pages 99–104, 1989. - A. Schönhage, The fundamantal theorem of algebra in terms of computational complexity, Unpublished manuscript, 1982.
- V. Shoup, Removing randomness from computational number theory (Ph. D. thesis), Technical Report 865, Computer Sciences Department, University of Wisconsin–Madison, 1989.
- Victor Shoup,
*New algorithms for finding irreducible polynomials over finite fields*, Math. Comp.**54**(1990), no. 189, 435–447. MR**993933**, DOI 10.1090/S0025-5718-1990-0993933-0 - Victor Shoup,
*Smoothness and factoring polynomials over finite fields*, Inform. Process. Lett.**38**(1991), no. 1, 39–42. MR**1103697**, DOI 10.1016/0020-0190(91)90212-Z - Victor Shoup,
*Searching for primitive roots in finite fields*, Math. Comp.**58**(1992), no. 197, 369–380. MR**1106981**, DOI 10.1090/S0025-5718-1992-1106981-9 - Yuan Wang,
*On the least primitive root of a prime*, Sci. Sinica**10**(1961), 1–14. MR**130848**

## 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.
- © Copyright 1996 American Mathematical Society
- 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