{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T06:51:44Z","timestamp":1776840704396,"version":"3.51.2"},"reference-count":26,"publisher":"American Mathematical Society (AMS)","issue":"215","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We present a new deterministic algorithm for the problem of constructing\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n th power nonresidues in finite fields\n \n \n \n \n \n F<\/mml:mi>\n <\/mml:mrow>\n \n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:msub>\n \\mathbf {F}_{p^n}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is prime and\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is a prime divisor of\n \n \n \n \n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n p^n-1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n \n p<\/mml:mi>\n \n \u2192\n \n <\/mml:mo>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:mrow>\n p \\rightarrow \\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , our algorithm runs in polynomial time. Unlike other deterministic algorithms for this problem, this polynomial-time bound holds even if\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is exponentially large. More generally, assuming the ERH, in time\n \n \n \n \n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n p<\/mml:mi>\n \n )<\/mml:mo>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n (n \\log p)^{O(n)}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n we can construct a set of elements that generates the multiplicative group\n \n \n \n \n \n F<\/mml:mi>\n <\/mml:mrow>\n \n \n p<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n \n \u2217\n \n <\/mml:mo>\n <\/mml:msubsup>\n \\mathbf {F}_{p^n}^*<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . An extended abstract of this paper appeared in\n Proc. 23rd Ann. ACM Symp. on Theory of Computing<\/italic>\n , 1991.\n <\/p>","DOI":"10.1090\/s0025-5718-96-00751-x","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:28Z","timestamp":1027707268000},"page":"1311-1326","source":"Crossref","is-referenced-by-count":4,"title":["Constructing nonresidues in finite fields and the extended Riemann hypothesis"],"prefix":"10.1090","volume":"65","author":[{"given":"Johannes","family":"Buchmann","sequence":"first","affiliation":[]},{"given":"Victor","family":"Shoup","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1996]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"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\u2013355, 1986.","DOI":"10.1145\/12130.12166"},{"key":"2","doi-asserted-by":"crossref","unstructured":"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\u2013178, 1977.","DOI":"10.1109\/SFCS.1977.18"},{"key":"3","first-page":"623","article-title":"Annihilator ideals and representation iteration for abstract rings","volume":"5","author":"Everett, C. J., Jr.","year":"1939","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"issue":"191","key":"4","doi-asserted-by":"publisher","first-page":"355","DOI":"10.2307\/2008811","article-title":"Explicit bounds for primality testing and related problems","volume":"55","author":"Bach, Eric","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"185","key":"5","doi-asserted-by":"publisher","first-page":"201","DOI":"10.2307\/2008664","article-title":"Factoring with cyclotomic polynomials","volume":"52","author":"Bach, Eric","year":"1989","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","unstructured":"E. Bach and J. von zur Gathen, Deterministic factorization of polynomials over special finite fields, Technical Report 799, Computer Sciences Department, University of Wisconsin\u2013Madison, 1988."},{"key":"7","unstructured":"E. Bach, J. von zur Gathen, and H. W. Lenstra, Preprint, 1989."},{"issue":"1","key":"8","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/0022-314X(87)90092-8","article-title":"On the computation of units and class numbers by a generalization of Lagrange\u2019s algorithm","volume":"26","author":"Buchmann, Johannes","year":"1987","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"1","key":"9","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0022-314X(87)90093-X","article-title":"On the period length of the generalized Lagrange algorithm","volume":"26","author":"Buchmann, Johannes","year":"1987","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0747-7171(87)80049-4","article-title":"On principal ideal testing in algebraic number fields","volume":"4","author":"Buchmann, Johannes","year":"1987","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"11","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/BF01104107","article-title":"Factorization of a solvable polynomial over finite fields and the generalized Riemann hypothesis","volume":"176","author":"Evdokimov, S. A.","year":"1989","journal-title":"Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI)","ISSN":"https:\/\/id.crossref.org\/issn\/0373-2703","issn-type":"print"},{"issue":"1-2","key":"12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0304-3975(87)90081-8","article-title":"Factoring polynomials and primitive elements for special primes","volume":"52","author":"von zur Gathen, Joachim","year":"1987","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"13","doi-asserted-by":"crossref","unstructured":"M. A. Huang, Riemann hypothesis and finding roots over finite fields, In 17th Annual ACM Symposium on Theory of Computing, pages 121\u2013130, 1985.","DOI":"10.1145\/22145.22159"},{"key":"14","series-title":"Pure and Applied Mathematics, Vol. 55","volume-title":"Algebraic number fields","author":"Janusz, Gerald J.","year":"1973"},{"issue":"193","key":"15","doi-asserted-by":"publisher","first-page":"329","DOI":"10.2307\/2008545","article-title":"Finding isomorphisms between finite fields","volume":"56","author":"Lenstra, H. W., Jr.","year":"1991","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"16","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1090\/S0273-0979-1992-00284-7","article-title":"Algorithms in algebraic number theory","volume":"26","author":"Lenstra, H. W., Jr.","year":"1992","journal-title":"Bull. Amer. Math. Soc. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0273-0979","issn-type":"print"},{"issue":"1","key":"17","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1070\/RM1990v045n01ABEH002330","article-title":"Distribution of primitive roots in finite fields","volume":"45","author":"Perel\u2032muter, G. I.","year":"1990","journal-title":"Uspekhi Mat. Nauk","ISSN":"https:\/\/id.crossref.org\/issn\/0042-1316","issn-type":"print"},{"issue":"1","key":"18","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/tit.1978.1055817","article-title":"An improved algorithm for computing logarithms over \ud835\udc3a\ud835\udc39(\ud835\udc5d) and its cryptographic significance","volume":"IT-24","author":"Pohlig, Stephen C.","year":"1978","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"3","key":"19","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0196-6774(88)90029-6","article-title":"Factoring polynomials over finite fields","volume":"9","author":"R\u00f3nyai, Lajos","year":"1988","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"20","doi-asserted-by":"crossref","unstructured":"L. R\u00f3nyai, Galois groups and factoring polynomials over finite fields, In 30th Annual Symposium on Foundations of Computer Science, pages 99\u2013104, 1989.","DOI":"10.1109\/SFCS.1989.63462"},{"key":"21","unstructured":"A. Sch\u00f6nhage, The fundamantal theorem of algebra in terms of computational complexity, Unpublished manuscript, 1982."},{"key":"22","unstructured":"V. Shoup, Removing randomness from computational number theory (Ph. D. thesis), Technical Report 865, Computer Sciences Department, University of Wisconsin\u2013Madison, 1989."},{"issue":"189","key":"23","doi-asserted-by":"publisher","first-page":"435","DOI":"10.2307\/2008704","article-title":"New algorithms for finding irreducible polynomials over finite fields","volume":"54","author":"Shoup, Victor","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"24","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0020-0190(91)90212-Z","article-title":"Smoothness and factoring polynomials over finite fields","volume":"38","author":"Shoup, Victor","year":"1991","journal-title":"Inform. Process. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-0190","issn-type":"print"},{"issue":"197","key":"25","doi-asserted-by":"publisher","first-page":"369","DOI":"10.2307\/2153041","article-title":"Searching for primitive roots in finite fields","volume":"58","author":"Shoup, Victor","year":"1992","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"26","first-page":"1","article-title":"On the least primitive root of a prime","volume":"10","author":"Wang, Yuan","year":"1961","journal-title":"Sci. Sinica"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1996-65-215\/S0025-5718-96-00751-X\/S0025-5718-96-00751-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-215\/S0025-5718-96-00751-X\/S0025-5718-96-00751-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:13:09Z","timestamp":1776719589000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-215\/S0025-5718-96-00751-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"references-count":26,"journal-issue":{"issue":"215","published-print":{"date-parts":[[1996,7]]}},"alternative-id":["S0025-5718-96-00751-X"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-96-00751-x","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1996]]}}}