{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:58:54Z","timestamp":1760061534836},"reference-count":58,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2014,4,1]],"date-time":"2014-04-01T00:00:00Z","timestamp":1396310400000},"content-version":"unspecified","delay-in-days":90,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2014]]},"abstract":"Abstract<\/jats:title>The problem of finding a nontrivial factor of a polynomial$f(x)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>over a finite field${\\mathbb{F}}_q$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the art by focusing on prime degree polynomials; let$n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>be the degree. If$(n-1)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>has a \u2018large\u2019$r$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-smooth divisor$s$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then we find a nontrivial factor of$f(x)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>in deterministic$\\mbox{poly}(n^r,\\log q)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>time, assuming GRH and that$s=\\Omega (\\sqrt{n\/2^r})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Thus, for$r=O(1)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>our algorithm is polynomial time. Further, for$r=\\Omega (\\log \\log n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>there are infinitely many prime degrees$n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>for which our algorithm is applicable and better than the best known, assuming GRH. Our methods build on the algebraic-combinatorial framework of$m$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-schemes initiated by Ivanyos, Karpinski and Saxena (ISSAC 2009). We show that the$m$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-scheme on$n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>points, implicitly appearing in our factoring algorithm, has an exceptional structure, leading us to the improved time complexity. Our structure theorem proves the existence of small intersection numbers in any association scheme that has many relations, and roughly equal valencies and indistinguishing numbers.<\/jats:p>","DOI":"10.1112\/s1461157013000296","type":"journal-article","created":{"date-parts":[[2014,4,25]],"date-time":"2014-04-25T08:49:34Z","timestamp":1398415774000},"page":"123-140","source":"Crossref","is-referenced-by-count":3,"title":["Deterministic polynomial factoring and association schemes"],"prefix":"10.1112","volume":"17","author":[{"given":"Manuel","family":"Arora","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e1bor","family":"Ivanyos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2014,4,1]]},"reference":[{"key":"S1461157013000296_r48","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1994.1032"},{"key":"S1461157013000296_r17","first-page":"104","article-title":"Factorization of a solvable polynomial over finite fields and the generalized Riemann hypothesis","volume":"176","author":"Evdokimov","year":"1989","journal-title":"Zap. Nauchn. Sem. LOMI"},{"key":"S1461157013000296_r28","first-page":"175","volume-title":"Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC)","author":"Huang","year":"1984"},{"key":"S1461157013000296_r15","doi-asserted-by":"crossref","unstructured":"15. H. Cohn and C. Umans , \u2018Fast matrix multiplication using coherent configurations\u2019, Preprint, 2012,arXiv:1207.6528.","DOI":"10.1137\/1.9781611973105.77"},{"key":"S1461157013000296_r6","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1967.tb03174.x"},{"key":"S1461157013000296_r31","doi-asserted-by":"crossref","unstructured":"31. G. Ivanyos , M. Karpinski and N. Saxena , \u2018Schemes for deterministic polynomial factoring\u2019, 34th International Symposium on Symbolic and Algebraic Computation, 2009, 191\u2013198.","DOI":"10.1145\/1576702.1576730"},{"key":"S1461157013000296_r58","volume-title":"Theory of association schemes","author":"Zieschang","year":"2005"},{"key":"S1461157013000296_r50","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90081-8"},{"key":"S1461157013000296_r12","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1981-0606517-5"},{"key":"S1461157013000296_r24","doi-asserted-by":"publisher","DOI":"10.1016\/0019-3577(92)90037-L"},{"key":"S1461157013000296_r53","first-page":"12","article-title":"Reduction of a graph to a canonical form and an algebra which appears in this process (Russian)","volume":"9","author":"Weisfeiler","year":"1968","journal-title":"Sci.-Technol. Investig."},{"key":"S1461157013000296_r4","doi-asserted-by":"publisher","DOI":"10.1006\/ffta.2000.0306"},{"key":"S1461157013000296_r26","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-64.2.265"},{"key":"S1461157013000296_r36","first-page":"367","article-title":"Une g\u00e9n\u00e9ralisation de la notion de corps","volume":"17","author":"Krasner","year":"1938","journal-title":"J. Math. Pures Appl."},{"key":"S1461157013000296_r51","doi-asserted-by":"publisher","DOI":"10.1007\/BF01272074"},{"key":"S1461157013000296_r21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.11.005"},{"key":"S1461157013000296_r38","first-page":"467","article-title":"Calcul d\u00e9terministe des racines d\u2019un polyn\u00f4me dans un corps fini","volume":"306","author":"Mignotte","year":"1988","journal-title":"C. R. Math. Acad. Sci."},{"key":"S1461157013000296_r43","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90029-6"},{"key":"S1461157013000296_r13","first-page":"233","volume-title":"Proceedings of the 4th ANTS","author":"Cheng","year":"2000"},{"key":"S1461157013000296_r56","first-page":"45","article-title":"Presuperschemes and colored directed graphs","volume":"38","author":"Wojdy\u0142o","year":"2001","journal-title":"JCMCC"},{"key":"S1461157013000296_r40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.26493\/1855-3974.121.885","article-title":"On pseudocyclic association schemes","volume":"5","author":"Muzychuk","year":"2012","journal-title":"ARS Math. Contemp."},{"key":"S1461157013000296_r20","first-page":"189","article-title":"Characterization of cyclotomic schemes and normal Schur rings over a cyclic group","volume":"14","author":"Evdokimov","year":"2003","journal-title":"St. Petersburg Math. J."},{"key":"S1461157013000296_r39","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0422193-8"},{"key":"S1461157013000296_r14","volume-title":"The Riemann hypothesis and Hilbert\u2019s tenth problem","author":"Chowla","year":"1965"},{"key":"S1461157013000296_r41","doi-asserted-by":"publisher","DOI":"10.1137\/0209024"},{"key":"S1461157013000296_r57","unstructured":"57. T. Xylouris , \u2018\u00dcber die Nullstellen der Dirichletschen L-Funktionen und die Kleinste Primzahl in einer Arithmetischen Progression\u2019, PhD Thesis, Mathematisch-Naturwissenschaftliche Fakult\u00e4t der Universit\u00e4t Bonn, 2011."},{"key":"S1461157013000296_r45","doi-asserted-by":"publisher","DOI":"10.1137\/0405026"},{"key":"S1461157013000296_r27","first-page":"1","article-title":"Coherent configurations I","volume":"44","author":"Higman","year":"1970","journal-title":"Rend. Semin. Mat. Univ. Padova"},{"key":"S1461157013000296_r32","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-98-00944-2"},{"key":"S1461157013000296_r46","unstructured":"46. C. Saha , \u2018Factoring polynomials over finite fields using balance test\u2019, 25th STACS (2008) 609\u2013620."},{"key":"S1461157013000296_r47","doi-asserted-by":"crossref","first-page":"345","DOI":"10.4064\/aa-4-3-185-208","article-title":"Sur certaines hypoth\u00e8ses concernant les nombres premiers","volume":"4","author":"Schinzel","year":"1958","journal-title":"Acta Arith."},{"key":"S1461157013000296_r37","first-page":"139","article-title":"On the least prime in an arithmetic progression I. The basic theorem","volume":"15","author":"Linnik","year":"1944","journal-title":"Rec. Math. (Mat. Sbornik ) N.S."},{"key":"S1461157013000296_r23","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1999.1001"},{"key":"S1461157013000296_r1","first-page":"175","volume-title":"Proceedings of the 18th FOCS","author":"Adleman","year":"1977"},{"key":"S1461157013000296_r34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01362452"},{"key":"S1461157013000296_r10","first-page":"337","article-title":"Partially balanced incomplete block designs","volume":"4","author":"Bose","year":"1939","journal-title":"Sankhy\u0101"},{"key":"S1461157013000296_r49","doi-asserted-by":"crossref","unstructured":"49. J. Voight , \u2018Curves over finite fields with many points: an introduction\u2019, Computational aspects of algebraic curves, Lecture Notes Series on Computing 13 (ed. Shaska Tanush; World Scientific, Hackensack, NJ, 2005) 124\u2013144.","DOI":"10.1142\/9789812701640_0010"},{"key":"S1461157013000296_r44","doi-asserted-by":"publisher","DOI":"10.1007\/BF02124680"},{"key":"S1461157013000296_r52","volume-title":"Courbes Alg\u00e9briques et Vari\u00e9t\u00e9s Abelienne","author":"Weil","year":"1971"},{"key":"S1461157013000296_r16","unstructured":"16. P. Delsarte , \u2018An algebraic approach to the association schemes of coding theory\u2019, Technical Report, Philips Research Reports, Supplement No. 10, 1973."},{"key":"S1461157013000296_r11","first-page":"149","article-title":"A deterministic algorithm for factorizing polynomials of $\\mathbb{F}_q[x]$","volume":"17","author":"Camion","year":"1983","journal-title":"Ann. Discrete Math."},{"key":"S1461157013000296_r30","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02505-6"},{"key":"S1461157013000296_r19","doi-asserted-by":"crossref","DOI":"10.37236\/1509","article-title":"Separability number and Schurity number of coherent configurations","volume":"7","author":"Evdokimov","year":"2000","journal-title":"Electron. J. Combin."},{"key":"S1461157013000296_r8","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-72126-2"},{"key":"S1461157013000296_r33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01234936"},{"key":"S1461157013000296_r22","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2008.168.367"},{"key":"S1461157013000296_r42","unstructured":"42. B. Riemann , \u2018\u00dcber die Anzahl der Primzahlen unter einer gegebenen Gr\u00f6sse\u2019, Monatsberichte Berliner Akad., 1859."},{"key":"S1461157013000296_r55","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007237"},{"key":"S1461157013000296_r18","first-page":"209","volume-title":"Proc. 1st ANTS","author":"Evdokimov","year":"1994"},{"key":"S1461157013000296_r35","doi-asserted-by":"publisher","DOI":"10.1137\/08073408X"},{"key":"S1461157013000296_r7","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"S1461157013000296_r54","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1998.0244"},{"key":"S1461157013000296_r9","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706356"},{"key":"S1461157013000296_r2","doi-asserted-by":"publisher","DOI":"10.2307\/1969420"},{"key":"S1461157013000296_r3","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-96-00763-6"},{"key":"S1461157013000296_r29","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90014-P"},{"key":"S1461157013000296_r5","volume-title":"Algebraic combinatorics I: association schemes","author":"Bannai","year":"1984"},{"key":"S1461157013000296_r25","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-006-6923-7"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157013000296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,18]],"date-time":"2020-08-18T10:27:58Z","timestamp":1597746478000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157013000296\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014]]}},"alternative-id":["S1461157013000296"],"URL":"https:\/\/doi.org\/10.1112\/s1461157013000296","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}