Citation
Guo, Zeyu (2017) PSchemes and Deterministic Polynomial Factoring Over Finite Fields. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z94F1NSG. https://resolver.caltech.edu/CaltechTHESIS:06012017013622968
Abstract
We introduce a family of mathematical objects called Pschemes, where P is a poset of subgroups of a finite group G. A Pscheme is a collection of partitions of the right coset spaces H\G, indexed by H∈P, that satisfies a list of axioms. These objects generalize the classical notion of association schemes [BI84] as well as the notion of mschemes [IKS09].
Based on Pschemes, we develop a unifying framework for the problem of deterministic factoring of univariate polynomials over finite field under the generalized Riemann hypothesis (GRH). More specifically, our results include the following:
We show an equivalence between mscheme as introduced in [IKS09] and Pschemes in the special setting that G is an multiply transitive permutation group and P is a poset of pointwise stabilizers, and therefore realize the theory of mschemes as part of the richer theory of Pschemes.
We give a generic deterministic algorithm that computes the factorization of the input polynomial ƒ(X) ∈ F_{q}[X] given a "lifted polynomial" ƒ~(X) of ƒ(X) and a collection F of "effectively constructible" subfields of the splitting field of ƒ~(X) over a certain base field. It is routine to compute ƒ~(X) from ƒ(X) by lifting the coefficients of ƒ(X) to a number ring. The algorithm then successfully factorizes ƒ(X) under GRH in time polynomial in the size of ƒ~(X) and F, provided that a certain condition concerning Pschemes is satisfied, for P being the poset of subgroups of the Galois group G of ƒ~(X) defined by F via the Galois correspondence. By considering various choices of G, P and verifying the condition, we are able to derive the main results of known (GRHbased) deterministic factoring algorithms [Hua91a; Hua91b; Ron88; Ron92; Evd92; Evd94; IKS09] from our generic algorithm in a uniform way.
We investigate the schemes conjecture in [IKS09] and formulate analogous conjectures associated with various families of permutation groups, each of which has applications on deterministic polynomial factoring. Using a technique called induction of Pschemes, we establish reductions among these conjectures and show that they form a hierarchy of relaxations of the original schemes conjecture.
We connect the complexity of deterministic polynomial factoring with the complexity of the Galois group G of ƒ~(X). Specifically, using techniques from permutation group theory, we obtain a (GRHbased) deterministic factoring algorithm whose running time is bounded in terms of the noncyclic composition factors of G. In particular, this algorithm runs in polynomial time if G is in Γ_{k} for some k=2^{O(√(log n)}, where Γ_{k} denotes the family of finite groups whose noncyclic composition factors are all isomorphic of subgroups of the symmetric group of degree k. Previously, polynomialtime algorithms for Γ_{k} were known only for bounded k.
We discuss various aspects of the theory of Pschemes, including techniques of constructing new Pschemes from old ones, Pschemes for symmetric groups and linear groups, orbit Pschemes, etc. For the closely related theory of mschemes, we provide explicit constructions of strongly antisymmetric homogeneous mschemes for m≤3. We also show that all antisymmetric homogeneous orbit 3schemes have a matching for m≥3, improving a result in [IKS09] that confirms the same statement for m≥4.
In summary, our framework reduces the algorithmic problem of deterministic polynomial factoring over finite fields to a combinatorial problem concerning Pschemes, allowing us to not only recover most of the known results but also discover new ones. We believe progress in understanding Pschemes associated with various families of permutation groups will shed some light on the ultimate goal of solving deterministic polynomial factoring over finite fields in polynomial time.
Item Type:  Thesis (Dissertation (Ph.D.))  

Subject Keywords:  computer algebra; derandomization; polynomial factoring; algebraic combinatorics; algorithm  
Degree Grantor:  California Institute of Technology  
Division:  Engineering and Applied Science  
Major Option:  Computer Science  
Thesis Availability:  Public (worldwide access)  
Research Advisor(s): 
 
Thesis Committee: 
 
Defense Date:  22 May 2017  
Record Number:  CaltechTHESIS:06012017013622968  
Persistent URL:  https://resolver.caltech.edu/CaltechTHESIS:06012017013622968  
DOI:  10.7907/Z94F1NSG  
ORCID: 
 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  10241  
Collection:  CaltechTHESIS  
Deposited By:  Zeyu Guo  
Deposited On:  02 Jun 2017 20:02  
Last Modified:  10 Jan 2022 19:55 
Thesis Files

PDF
 Final Version
See Usage Policy. 1MB 
Repository Staff Only: item control page