A Caltech Library Service

Deterministic polynomial factoring and association schemes

Arora, Manuel and Ivanyos, Gábor and Karpinski, Marek and Saxena, Nitin (2014) Deterministic polynomial factoring and association schemes. LMS Journal of Computation and Mathematics, 17 (1). pp. 123-140. ISSN 1461-1570. doi:10.1112/S1461157013000296.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


The problem of finding a nontrivial factor of a polynomial f(x) over a finite field F_q 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 be the degree. If (n−1) has a ‘large’ r-smooth divisor s, then we find a nontrivial factor of f(x) in deterministic poly(n^r, log q) time, assuming GRH and that s=Ω(√(n/2^r)). Thus, for r=O(1) our algorithm is polynomial time. Further, for r=Ω(loglog n) there are infinitely many prime degrees n for which our algorithm is applicable and better than the best known, assuming GRH. Our methods build on the algebraic-combinatorial framework of m-schemes initiated by Ivanyos, Karpinski and Saxena (ISSAC 2009). We show that the m-scheme on n 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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2014 The Author(s). Received 1 February 2013; revised 3 September 2013. This work was done while M.A. and N.S. were employed in the Hausdorff Center for Mathematics, Bonn (HCM). We would like to thank HCM and the Department of Computer Science, University of Bonn for its support. Especially, for hosting G.I. for a crucial part of the research, and for helping organize a related workshop on algebraic-combinatorial techniques. We thank Sergei Evdokimov, Akihide Hanaki, Mikhail Muzychuk, Ilya Ponomarenko, Igor Shparlinski and Paul-Hermann Zieschang for the many fruitful conversations. Especially, M.A. is grateful to Ilya for the numerous, still ongoing, discussions, explanations and pointers.
Issue or Number:1
Classification Code:2010 Mathematics Subject Classification 12Y05, 05E30 (primary), 05E10, 03D15, 68W30 (secondary)
Record Number:CaltechAUTHORS:20150317-102036984
Persistent URL:
Official Citation:Manuel Arora, Gábor Ivanyos, Marek Karpinski and Nitin Saxena (2014). Deterministic polynomial factoring and association schemes. LMS Journal of Computation and Mathematics, 17, pp 123-140. doi:10.1112/S1461157013000296.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55845
Deposited By: Jason Perez
Deposited On:17 Mar 2015 18:49
Last Modified:10 Nov 2021 20:51

Repository Staff Only: item control page