{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:40Z","timestamp":1787340640599,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,2]]},"abstract":"<jats:p>We show that if $f(x)$ is a polynomial in $Z [ \\alpha ][ x ]$, where $\\alpha $ satisfies a monic irreducible polynomial over Z, then $f(x)$ can be factored over $Q(\\alpha )[ x ]$ in polynomial time. We also show that the splitting field of $f(x)$ can be determined in time polynomial in ([Splitting field of $f(x): Q $], $\\log | (x) |$).<\/jats:p>","DOI":"10.1137\/0214015","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"184-195","source":"Crossref","is-referenced-by-count":79,"title":["Factoring Polynomials over Algebraic Number Fields"],"prefix":"10.1137","volume":"14","author":[{"given":"Susan","family":"Landau","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RB-O","doi-asserted-by":"crossref","unstructured":"M. Ben-Or,  Probabilistic algorithms in finite fields,  Proc. Twenty-second Annual IEEE Symposium on Foundations of Computer Science,  1981,  394\u2013398","DOI":"10.1109\/SFCS.1981.37"},{"key":"RBE","volume-title":"Algebraic coding theory","author":"Berlekamp Elwyn R.","year":"1968"},{"key":"RBE2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"RBR1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321664"},{"key":"RBR2","doi-asserted-by":"publisher","DOI":"10.1145\/355791.355795"},{"key":"RBT","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321665"},{"key":"RCAN","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90036-5"},{"key":"RCG","unstructured":"A. L. Chistov, D. Y. Grigoriev,  Polynomial-time factoring of the multivariable polynomials over a general field, USSR Academy of Sciences, Steklov Mathematical Institute, Leningrad,  1982"},{"key":"RCO","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321666"},{"key":"REDM","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.033"},{"key":"RKA1","doi-asserted-by":"crossref","unstructured":"E. Kaltofen,  A polynomial reduction from multivariate to bivariate polynomial factorization,  Proc. Fourteenth Annual ACM Symposium on Theory of Computing,  1982,  261\u2013266","DOI":"10.1145\/800070.802200"},{"key":"RKA2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.56"},{"key":"RKMS","doi-asserted-by":"crossref","unstructured":"E. Kaltofen, D. R. Musser, B. D. Saunders,  A generalized class of polynomials which are hard to factor,  Proc.1981 ACM Symposium on Symbolic and Algebraic Computation,  188\u2013194","DOI":"10.1145\/800206.806394"},{"key":"RKN","volume-title":"The art of computer programming. Vol. 2: Seminumerical algorithms","author":"Knuth D.","year":"1969"},{"key":"RKR","volume-title":"Gr\u00fcndzige Einer Arithmetischen Theorie der Algebraischen Gr\u00f6ssen","author":"Kronecker L.","year":"1882"},{"key":"RLM","doi-asserted-by":"crossref","unstructured":"S. Landau, G. L. Miller,  Solvability by radicals is in polynomial time,  Proc. Fifteenth Annual ACM Symposium on Theory of Computing,  1983,  140\u2013151","DOI":"10.1145\/800061.808743"},{"key":"RL3","unstructured":"A. K. Lenstra, H. W. Lenstra, L. Lovasz,  Factoring polynomials with rational coefficients, Tech. Report, 82\u201305, Dept. Mathematics, Univ. Amsterdam,  1982"},{"key":"RAKL","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra,  Factoring polynomials over algebraic number fields, Tech. Report, IW213\/82, Dept. Computer Science, Stichting Mathematisch Centrum, Amsterdam,  1982","DOI":"10.1007\/3-540-11607-9_4"},{"key":"RLPC","unstructured":"H. W. Lenstra, private communication"},{"key":"RMAR","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9356-6"},{"key":"RMI1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0354624-3"},{"key":"RMI2","doi-asserted-by":"crossref","unstructured":"M. Mignotre,  Some inequalities about univariate polynomials,  Proc. 1981 ACM Symposium on Symbolic and Algebraic Computation,  195\u201399","DOI":"10.1145\/800206.806395"},{"key":"RMU","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321890"},{"key":"RSA","volume-title":"Algebraic Theory of Numbers","author":"Samuel P.","year":"1972"},{"key":"RTR","doi-asserted-by":"crossref","unstructured":"B. Trager,  Algebraic factoring and rational function integration,  Proc.1976 ACM Symposium on Symbolic and Algebraic Computation,  219\u2013226","DOI":"10.1145\/800205.806338"},{"key":"RVDW","volume-title":"Modern Algebra","author":"van der Waerden B. L.","year":"1941"},{"key":"RWEI","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90025-7"},{"key":"RWR","doi-asserted-by":"publisher","DOI":"10.1145\/355705.355709"},{"key":"RWEY1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882809"},{"key":"RZAL","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(69)90047-X"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:22Z","timestamp":1787337742000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,2]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,2]]}},"alternative-id":["10.1137\/0214015"],"URL":"https:\/\/doi.org\/10.1137\/0214015","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,2]]}}}