{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:22Z","timestamp":1750307002714,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            We give the first polynomial-time algorithm for checking whether the Galois group Gal(\n            <jats:italic>f<\/jats:italic>\n            ) of an input polynomial\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>X<\/jats:italic>\n            ) \u2208 Q[\n            <jats:italic>X<\/jats:italic>\n            ] is nilpotent: the running time of our algorithm is bounded by a polynomial in the size of the coefficients of\n            <jats:italic>f<\/jats:italic>\n            and the degree of\n            <jats:italic>f<\/jats:italic>\n            . Additionally, we give a deterministic polynomial-time algorithm that, when given as input a polynomial\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>X<\/jats:italic>\n            ) \u2208 Q[\n            <jats:italic>X<\/jats:italic>\n            ] with nilpotent Galois group, computes for each prime factor\n            <jats:italic>p<\/jats:italic>\n            of # Gal(\n            <jats:italic>f<\/jats:italic>\n            ), a polynomial\n            <jats:italic>\n              g\n              <jats:sub>p<\/jats:sub>\n            <\/jats:italic>\n            (\n            <jats:italic>X<\/jats:italic>\n            )\u2208 Q[\n            <jats:italic>X<\/jats:italic>\n            ] whose Galois group of is the\n            <jats:italic>p<\/jats:italic>\n            -Sylow subgroup of Gal(\n            <jats:italic>f<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/2229163.2229176","type":"journal-article","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T14:41:09Z","timestamp":1343313669000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing nilpotence of galois groups in polynomial time"],"prefix":"10.1145","volume":"8","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai, India"}]},{"given":"Piyush P.","family":"Kurur","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Kanpur, India"}]}],"member":"320","published-online":{"date-parts":[[2012,7,24]]},"reference":[{"volume-title":"Permutation Group Algorithms. Number 152 in Cambridge Tracts in Mathematics","author":"\u00c1kos Seress","key":"e_1_2_1_1_1","unstructured":"\u00c1kos Seress . 2003. Permutation Group Algorithms. Number 152 in Cambridge Tracts in Mathematics . Cambridge University Press . \u00c1kos Seress. 2003. Permutation Group Algorithms. Number 152 in Cambridge Tracts in Mathematics. Cambridge University Press."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11821069_12"},{"volume-title":"A Course in Computational Number Theory","author":"Cohen H.","key":"e_1_2_1_3_1","unstructured":"Cohen , H. 1993. A Course in Computational Number Theory . Springer . Cohen, H. 1993. A Course in Computational Number Theory. Springer."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-03-01620-X"},{"key":"e_1_2_1_5_1","first-page":"271","article-title":"Analyse d'un m\u00e9moire sur la r\u00e9solution alg\u00e9brique des \u00e9quations","author":"Galois","year":"1830","unstructured":"Galois , \u00c9. 1830 a. Analyse d'un m\u00e9moire sur la r\u00e9solution alg\u00e9brique des \u00e9quations . Bull. Sci. Math. XIII , 271 . Galois, \u00c9. 1830a. Analyse d'un m\u00e9moire sur la r\u00e9solution alg\u00e9brique des \u00e9quations. Bull. Sci. Math. XIII, 271.","journal-title":"Bull. Sci. Math."},{"key":"e_1_2_1_6_1","first-page":"413","article-title":"Note sur la r\u00e9solution des \u00e9quations num\u00e9riques","author":"Galois","year":"1830","unstructured":"Galois , \u00c9. 1830 b. Note sur la r\u00e9solution des \u00e9quations num\u00e9riques . Bull. Sci. Math. XIII , 413 . Galois, \u00c9. 1830b. Note sur la r\u00e9solution des \u00e9quations num\u00e9riques. Bull. Sci. Math. XIII, 413.","journal-title":"Bull. Sci. Math."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2000.0377"},{"key":"e_1_2_1_8_1","volume-title":"The Theory of Groups","author":"Hall","unstructured":"Hall Jr ., M. 1959. The Theory of Groups , 1 st ed. The Macmillan Company , New York . Hall Jr., M. 1959. The Theory of Groups, 1st ed. The Macmillan Company, New York.","edition":"1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90038-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646671.699149"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90013-3"},{"key":"e_1_2_1_14_1","volume-title":"Algebra","author":"Lang S.","unstructured":"Lang , S. 1999. Algebra , 3 rd ed. Addison-Wesley . Lang, S. 1999. Algebra, 3rd ed. Addison-Wesley.","edition":"3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1992-00284-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/011\/11"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-97-00831-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2000.0389"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Mignotte M. 1974. An inequality about factors of polynomials. Math. Comput. 28 128 1153--1157.  Mignotte M. 1974. An inequality about factors of polynomials. Math. Comput. 28 128 1153--1157.","DOI":"10.1090\/S0025-5718-1974-0354624-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/309831.309859"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(85)90022-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1973-0327712-4"},{"key":"e_1_2_1_25_1","unstructured":"Tschebotar\u00f6w N. and Schwerdtfeger N. 1950. Grundz\u00fcge der galoischen theorie. In Groningen Djakarta Noordhoff.  Tschebotar\u00f6w N. and Schwerdtfeger N. 1950. Grundz\u00fcge der galoischen theorie. In Groningen Djakarta Noordhoff."},{"key":"e_1_2_1_26_1","volume-title":"Algebra","author":"van der Waerden B. L.","unstructured":"van der Waerden , B. L. 1991. Algebra , 7 th ed. Vol. I . Springer . van der Waerden, B. L. 1991. Algebra, 7th ed. Vol. I. Springer.","edition":"7"},{"volume-title":"Finite Permutation Groups","author":"Wielandt H.","key":"e_1_2_1_27_1","unstructured":"Wielandt , H. 1964. Finite Permutation Groups . Academic Press , New York . Wielandt, H. 1964. Finite Permutation Groups. Academic Press, New York."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229176","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2229163.2229176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:52Z","timestamp":1750236532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1145\/2229163.2229176"],"URL":"https:\/\/doi.org\/10.1145\/2229163.2229176","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,7]]},"assertion":[{"value":"2008-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}