Deterministic polynomial factoring over finite fields: A uniform approach via P-schemes. (January 2020)

• Record Type: Journal Article
• Authors: Guo, Zeyu
• Is Part Of: Journal of symbolic computation. Volume 96(2020)
• Page Start: 22
• Page End: 61
• Publication Date: 2020-01
• Subjects: primary 68W30 -- 12Y05 -- 13P05; Polynomial factoring -- Permutation group -- Finite field -- Algebraic combinatorics; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2019.02.011
• Languages: English
• ISSNs: 0747-7171

Abstract

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.