Deterministic polynomial factoring over finite fields: A uniform approach via P-schemes. (January 2020) - Guo, Zeyu
Abstract: 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 p are given, such that f ( X ) : = f ˜ ( X ) mod p factorizes 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 G is a subgroup of Sym ( k ) for k up 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 conjecture inIvanyos 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.