{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:03:52Z","timestamp":1776841432724,"version":"3.51.2"},"reference-count":22,"publisher":"American Mathematical Society (AMS)","issue":"235","license":[{"start":{"date-parts":[[2001,3,24]],"date-time":"2001-03-24T00:00:00Z","timestamp":985392000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We examine the problem of factoring the\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"r\">\n                        <mml:semantics>\n                          <mml:mi>r<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">r<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    th cyclotomic polynomial,\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal upper Phi Subscript r Baseline left-parenthesis x right-parenthesis comma\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi mathvariant=\"normal\">\n                                \u03a6\n                                \n                              <\/mml:mi>\n                              <mml:mi>r<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo>,<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\Phi _r(x),<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    over\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper F Subscript p\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mi>p<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {F}_p<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    ,\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"r\">\n                        <mml:semantics>\n                          <mml:mi>r<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">r<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"p\">\n                        <mml:semantics>\n                          <mml:mi>p<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">p<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    distinct primes. Given the traces of the roots of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal upper Phi Subscript r Baseline left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi mathvariant=\"normal\">\n                                \u03a6\n                                \n                              <\/mml:mi>\n                              <mml:mi>r<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\Phi _r(x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    we construct the coefficients of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal upper Phi Subscript r Baseline left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi mathvariant=\"normal\">\n                                \u03a6\n                                \n                              <\/mml:mi>\n                              <mml:mi>r<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\Phi _r(x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    in time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis r Superscript 4 Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>r<\/mml:mi>\n                              <mml:mn>4<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(r^4)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . We demonstrate a deterministic algorithm for factoring\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal upper Phi Subscript r Baseline left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi mathvariant=\"normal\">\n                                \u03a6\n                                \n                              <\/mml:mi>\n                              <mml:mi>r<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\Phi _r(x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    in time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis left-parenthesis r Superscript 1 slash 2 plus epsilon Baseline log p right-parenthesis Superscript 9 Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>r<\/mml:mi>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mn>1<\/mml:mn>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:mo>\/<\/mml:mo>\n                                <\/mml:mrow>\n                                <mml:mn>2<\/mml:mn>\n                                <mml:mo>+<\/mml:mo>\n                                <mml:mi>\n                                  \u03f5\n                                  \n                                <\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mi>log<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>p<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <mml:mn>9<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O((r^{1\/2+\\epsilon }\\log p)^9)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    when\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal upper Phi Subscript r Baseline left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi mathvariant=\"normal\">\n                                \u03a6\n                                \n                              <\/mml:mi>\n                              <mml:mi>r<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\Phi _r(x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal upper Phi Subscript r Baseline left-parenthesis x right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi mathvariant=\"normal\">\n                                \u03a6\n                                \n                              <\/mml:mi>\n                              <mml:mi>r<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\Phi _r(x)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    in time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis r Superscript 6 Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>r<\/mml:mi>\n                              <mml:mn>6<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(r^6)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    .\n                  <\/p>","DOI":"10.1090\/s0025-5718-00-01233-3","type":"journal-article","created":{"date-parts":[[2002,11,6]],"date-time":"2002-11-06T14:02:22Z","timestamp":1036591342000},"page":"1237-1251","source":"Crossref","is-referenced-by-count":4,"title":["Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields"],"prefix":"10.1090","volume":"70","author":[{"given":"Greg","family":"Stein","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0022-314X(82)90058-0","article-title":"Uniform cyclotomy","volume":"14","author":"Baumert, L. D.","year":"1982","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"2","series-title":"Canadian Mathematical Society Series of Monographs and Advanced Texts","isbn-type":"print","volume-title":"Gauss and Jacobi sums","author":"Berndt, Bruce C.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0471128074"},{"key":"3","series-title":"Progress in Theoretical Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0265-3","volume-title":"Polynomial and matrix computations. Vol. 1","author":"Bini, Dario","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0817637869"},{"issue":"154","key":"4","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":"5","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"key":"6","doi-asserted-by":"crossref","unstructured":"L.E. Dickson, Cyclotomy, higher congruences, and Waring\u2019s problem, Amer. J. Math., [57], (1935), pp. 391-424.","DOI":"10.2307\/2371217"},{"key":"7","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":"8","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-7560-0","volume-title":"Disquisitiones arithmeticae","author":"Gauss, Carl Friedrich","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0387962549"},{"issue":"3","key":"9","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":"10","isbn-type":"print","volume-title":"Finite fields","author":"Jungnickel, Dieter","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3411161116"},{"key":"11","series-title":"Addison-Wesley Series in Computer Science and Information Processing","isbn-type":"print","volume-title":"The art of computer programming. Vol. 2","author":"Knuth, Donald E.","year":"1981","ISBN":"https:\/\/id.crossref.org\/isbn\/0201038226","edition":"2"},{"key":"12","volume-title":"Algebra","author":"Lang, Serge","year":"1965"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172769","volume-title":"Introduction to finite fields and their applications","author":"Lidl, Rudolf","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0521460948","edition":"1"},{"key":"14","series-title":"Encyclopedia of Mathematics and its Applications","isbn-type":"print","volume-title":"Finite fields","volume":"20","author":"Lidl, Rudolf","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/0201135191"},{"key":"15","volume-title":"Theory of numbers","author":"Mathews, G. B.","year":"1961"},{"issue":"3","key":"16","doi-asserted-by":"publisher","first-page":"251","DOI":"10.4064\/aa-39-3-251-264","article-title":"Period polynomials and Gauss sums for finite fields","volume":"39","author":"Myerson, Gerald","year":"1981","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"209","key":"17","doi-asserted-by":"publisher","first-page":"347","DOI":"10.2307\/2153339","article-title":"On a new factorization algorithm for polynomials over finite fields","volume":"64","author":"Niederreiter, Harald","year":"1995","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"170","key":"18","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"},{"issue":"189","key":"19","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"},{"key":"20","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"},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1090\/conm\/225\/03213","article-title":"Traces of roots of unity over prime fields","author":"Stein, Greg","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0821808176"},{"key":"22","series-title":"Lectures in Advanced Mathematics, No. 2","volume-title":"Cyclotomy and difference sets","author":"Storer, Thomas","year":"1967"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2001-70-235\/S0025-5718-00-01233-3\/S0025-5718-00-01233-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-235\/S0025-5718-00-01233-3\/S0025-5718-00-01233-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:42:04Z","timestamp":1776724924000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-235\/S0025-5718-00-01233-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3,24]]},"references-count":22,"journal-issue":{"issue":"235","published-print":{"date-parts":[[2001,7]]}},"alternative-id":["S0025-5718-00-01233-3"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01233-3","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":[[2000,3,24]]}}}