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

We introduce a family of combinatorial objects called P-schemes, where Pis 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 epsilon 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) over bar (X) epsilon Z[X] and a prime number pare given, such that f(X) := (f) over bar (X) modpfactorizes into n = deg((f) over bar) 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) over bar (X) is an almost simple primitive permutation group on the set of roots of (f) over bar (X), and the socle of Gis a subgroup of Sym(k) for kup to 2(O(root logn)). 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 withvarious 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. (C) 2019 Elsevier Ltd. All rights reserved.