A Caltech Library Service

Deterministic polynomial factoring over finite fields: A uniform approach via P-schemes

Guo, Zeyu (2020) Deterministic polynomial factoring over finite fields: A uniform approach via P-schemes. Journal of Symbolic Computation, 96 . pp. 22-61. ISSN 0747-7171. doi:10.1016/j.jsc.2019.02.011.

[img] PDF - Submitted Version
Creative Commons Attribution Non-commercial No Derivatives.


Use this Persistent URL to link to this item:


We introduce a family of combinatorial objects called P-schemes, where P is a collection of subgroups of a finite group G. A P-scheme is a collection of partitions of right coset spaces H\G, indexed by H ∈ P, that satisfies a list of axioms. These objects generalize the classical notion of association schemes as well as m-schemes (Ivanyos et al., 2009). We apply the theory of P-schemes to deterministic polynomial factoring over finite fields: suppose f(X) ∈ Z[X] and a prime number pare given, such that f(X) :=f(X) modpfactorizes into n =deg(f)distinct linear factors over the finite field F_p. We show that, assuming the generalized Riemann hypothesis (GRH), f(X)can be completely factorized in deterministic polynomial time if the Galois group G of f(X)is an almost simple primitive permutation group on the set of roots of f(X), and the socle of Gis a subgroup of Sym(k)for kup to 2^O(√log n). This is the first deterministic polynomial-time factoring algorithm for primitive Galois groups of superpolynomial order. We prove our result by developing a generic factoring algorithm and analyzing it using P-schemes. We also show that the main results achieved by known GRH-based deterministic polynomial factoring algorithms can be derived from our generic algorithm in a uniform way. Finally, we investigate the schemes conjecturein Ivanyos et al. (2009), and formulate analogous conjectures associated with various families of permutation groups. We show that these conjectures form a hierarchy of relaxations of the original schemes conjecture, and their positive resolutions would imply deterministic polynomial-time factoring algorithms for various families of Galois groups under GRH.

Item Type:Article
Related URLs:
URLURL TypeDescription
Guo, Zeyu0000-0001-7893-4346
Additional Information:© 2019 Elsevier Ltd. Received 13 June 2018, Accepted 23 January 2019, Available online 25 February 2019. © 2019 This manuscript version is made available under the CC-BY-NC-ND 4.0 license. The author is grateful to Chris Umans, Nitin Saxena, Manuel Arora, and Anand Kumar Narayanan for helpful discussions.
Subject Keywords:polynomial factoring; permutation group; finite field; algebraic combinatorics
Classification Code:MSC: Pimary 68W30; 12Y05; 13P05
Record Number:CaltechAUTHORS:20190225-133843285
Persistent URL:
Official Citation:Zeyu Guo, Deterministic polynomial factoring over finite fields: A uniform approach via P-schemes, Journal of Symbolic Computation, Volume 96, 2020, Pages 22-61, ISSN 0747-7171, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93229
Deposited By: Tony Diaz
Deposited On:25 Feb 2019 22:04
Last Modified:16 Nov 2021 16:56

Repository Staff Only: item control page