{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:10:41Z","timestamp":1776795041148,"version":"3.51.2"},"reference-count":38,"publisher":"American Mathematical Society (AMS)","issue":"277","license":[{"start":{"date-parts":[[2012,5,10]],"date-time":"2012-05-10T00:00:00Z","timestamp":1336608000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>In this paper we develop a general technique to eliminate the assumption of the Generalized Riemann Hypothesis (GRH) from various deterministic polynomial factoring algorithms over finite fields. It is the first bona fide progress on that issue for more than 25 years of study of the problem. Our main results are basically of the following form: either we construct a nontrivial factor of a given polynomial or compute a nontrivial automorphism of the factor algebra of the given polynomial. Probably the most notable application of such automorphisms is efficiently finding zero divisors in noncommutative algebras. The proof methods used in this paper exploit virtual roots of unity and lead to efficient actual polynomial factoring algorithms in special cases.<\/p>","DOI":"10.1090\/s0025-5718-2011-02505-6","type":"journal-article","created":{"date-parts":[[2011,5,10]],"date-time":"2011-05-10T08:00:12Z","timestamp":1305014412000},"page":"493-531","source":"Crossref","is-referenced-by-count":8,"title":["Trading GRH for algebra: Algorithms for factoring polynomials and related structures"],"prefix":"10.1090","volume":"81","author":[{"given":"G\u00e1bor","family":"Ivanyos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lajos","family":"R\u00f3nyai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2011,5,10]]},"reference":[{"issue":"192","key":"1","doi-asserted-by":"publisher","first-page":"705","DOI":"10.2307\/2008443","article-title":"Computing irreducible representations of finite groups","volume":"55","author":"Babai, L\u00e1szl\u00f3","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1006\/ffta.2000.0306","article-title":"Factoring polynomials over special finite fields","volume":"7","author":"Bach, Eric","year":"2001","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"key":"3","doi-asserted-by":"publisher","first-page":"1853","DOI":"10.1002\/j.1538-7305.1967.tb03174.x","article-title":"Factoring polynomials over finite fields","volume":"46","author":"Berlekamp, E. R.","year":"1967","journal-title":"Bell System Tech. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0005-8580","issn-type":"print"},{"key":"4","isbn-type":"print","first-page":"149","article-title":"A deterministic algorithm for factorizing polynomials of \ud835\udc39_{\ud835\udc5e}[\ud835\udc4b]","author":"Camion, Paul","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/0444865128"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/10722028_12","article-title":"Factoring polynomials over finite fields and stable colorings of tournaments","author":"Cheng, Qi","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540676953"},{"key":"6","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1145\/258726.258751","article-title":"Polynomial time algorithms for modules over finite dimensional algebras","author":"Chistov, Alexander","year":"1997"},{"key":"7","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-4049(97)00010-8","article-title":"Finding the radical of an algebra of linear transformations","volume":"117\/118","author":"Cohen, Arjeh M.","year":"1997","journal-title":"J. Pure Appl. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4049","issn-type":"print"},{"issue":"154","key":"8","doi-asserted-by":"publisher","first-page":"587","DOI":"10.2307\/2007663","article-title":"A new algorithm for factoring polynomials over finite fields","volume":"36","author":"Cantor, David G.","year":"1981","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"9","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"},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/3-540-58691-1_58","article-title":"Factorization of polynomials over finite fields in subexponential time under GRH","author":"Evdokimov, Sergei","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[FR85] K. Friedl, L. R\u00f3nyai, Polynomial time solutions of some problems of computational algebra; Proc. 17th ACM STOC (1985), pp. 153-162.","DOI":"10.1145\/22145.22162"},{"issue":"1-2","key":"12","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1006\/jsco.1999.1001","article-title":"On the deterministic complexity of factoring polynomials","volume":"31","author":"Gao, Shuhong","year":"2001","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"1-2","key":"13","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"},{"issue":"2","key":"14","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jalgebra.2005.06.022","article-title":"A Lie algebra method for rational parametrization of Severi-Brauer surfaces","volume":"303","author":"de Graaf, Willem A.","year":"2006","journal-title":"J. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0021-8693","issn-type":"print"},{"key":"15","isbn-type":"print","first-page":"95","article-title":"Finding splitting elements and maximal tori in matrix algebras","author":"de Graaf, Willem A.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0824703677"},{"issue":"3","key":"16","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01272074","article-title":"Computing Frobenius maps and factoring polynomials","volume":"2","author":"von zur Gathen, Joachim","year":"1992","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1016\/0196-6774(91)90014-P","article-title":"Generalized Riemann hypothesis and factoring polynomials over finite fields","volume":"12","author":"Huang, Ming-Deh A.","year":"1991","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"18","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-5119-2","volume-title":"Elliptic curves","volume":"111","author":"Husemoller, Dale","year":"1987","ISBN":"https:\/\/id.crossref.org\/isbn\/0387963715"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[IKS08] G. Ivanyos, M. Karpinski, N. Saxena, Schemes for Deterministic Polynomial Factoring, Proc. 34th ISSAC (2009), 191-198.","DOI":"10.1145\/1576702.1576730"},{"issue":"1-2","key":"20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","article-title":"Derandomizing polynomial identity tests means proving circuit lower bounds","volume":"13","author":"Kabanets, Valentine","year":"2004","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"issue":"223","key":"21","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1090\/S0025-5718-98-00944-2","article-title":"Subquadratic-time factoring of polynomials over finite fields","volume":"67","author":"Kaltofen, Erich","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"22","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/s00037-007-0219-8","article-title":"Complexity of ring morphism problems","volume":"15","author":"Kayal, Neeraj","year":"2006","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[KU08] K. Kedlaya, C. Umans, Fast modular composition in any characteristic, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (2008) pp. 146-155.","DOI":"10.1109\/FOCS.2008.13"},{"key":"24","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0853-2","volume-title":"Algebraic number theory","volume":"110","author":"Lang, Serge","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0387942254","edition":"2"},{"key":"25","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0041-0","volume-title":"Algebra","volume":"211","author":"Lang, Serge","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/038795385X","edition":"3"},{"issue":"193","key":"26","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":"12","key":"27","first-page":"467","article-title":"Calcul d\u00e9terministe des racines d\u2019un polyn\u00f4me dans un corps fini","volume":"306","author":"Mignotte, Maurice","year":"1988","journal-title":"C. R. Acad. Sci. Paris S\\'{e}r. I Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0249-6291","issn-type":"print"},{"issue":"137","key":"28","doi-asserted-by":"publisher","first-page":"235","DOI":"10.2307\/2005794","article-title":"On the efficiency of algorithms for polynomial factoring","volume":"31","author":"Moenck, Robert T.","year":"1977","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"29","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":"2","key":"30","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1137\/0209024","article-title":"Probabilistic algorithms in finite fields","volume":"9","author":"Rabin, Michael O.","year":"1980","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"3","key":"31","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"},{"issue":"2","key":"32","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF02124680","article-title":"Factoring polynomials modulo special primes","volume":"9","author":"R\u00f3nyai, L.","year":"1989","journal-title":"Combinatorica","ISSN":"https:\/\/id.crossref.org\/issn\/0209-9683","issn-type":"print"},{"issue":"3","key":"33","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/S0747-7171(08)80017-X","article-title":"Computing the structure of finite algebras","volume":"9","author":"R\u00f3nyai, Lajos","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"3","key":"34","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/0405026","article-title":"Galois groups and factoring polynomials over finite fields","volume":"5","author":"R\u00f3nyai, Lajos","year":"1992","journal-title":"SIAM J. Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4801","issn-type":"print"},{"issue":"170","key":"35","doi-asserted-by":"publisher","first-page":"483","DOI":"10.2307\/2007968","article-title":"Elliptic curves over finite fields and the computation of square roots mod \ud835\udc5d","volume":"44","author":"Schoof, Ren\u00e9","year":"1985","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"36","isbn-type":"print","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1017\/CBO9780511525988.026","article-title":"Factoring cyclotomic polynomials over large finite fields","author":"Stein, Greg","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/052156736X"},{"issue":"235","key":"37","doi-asserted-by":"publisher","first-page":"1237","DOI":"10.1090\/S0025-5718-00-01233-3","article-title":"Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields","volume":"70","author":"Stein, Greg","year":"2001","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"38","isbn-type":"print","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1145\/1073884.1073932","article-title":"Deterministic equation solving over finite fields","author":"van de Woestijne, Christiaan","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/1595930957"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2012-81-277\/S0025-5718-2011-02505-6\/S0025-5718-2011-02505-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2012-81-277\/S0025-5718-2011-02505-6\/S0025-5718-2011-02505-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:03:29Z","timestamp":1776791009000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2012-81-277\/S0025-5718-2011-02505-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,10]]},"references-count":38,"journal-issue":{"issue":"277","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["S0025-5718-2011-02505-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2011-02505-6","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":[[2011,5,10]]}}}