A Caltech Library Service

P-schemes and Deterministic Polynomial Factoring Over Finite Fields


Guo, Zeyu (2017) P-schemes and Deterministic Polynomial Factoring Over Finite Fields. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z94F1NSG.


We introduce a family of mathematical objects called P-schemes, where P is a poset of subgroups of a finite group G. A P-scheme 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 m-schemes [IKS09].

Based on P-schemes, 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 m-scheme as introduced in [IKS09] and P-schemes 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 m-schemes as part of the richer theory of P-schemes.

We give a generic deterministic algorithm that computes the factorization of the input polynomial ƒ(X) ∈ Fq[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 P-schemes 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 (GRH-based) 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 P-schemes, 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 (GRH-based) 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=2O(√(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, polynomial-time algorithms for Γk were known only for bounded k.

We discuss various aspects of the theory of P-schemes, including techniques of constructing new P-schemes from old ones, P-schemes for symmetric groups and linear groups, orbit P-schemes, etc. For the closely related theory of m-schemes, we provide explicit constructions of strongly antisymmetric homogeneous m-schemes for m≤3. We also show that all antisymmetric homogeneous orbit 3-schemes 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 P-schemes, allowing us to not only recover most of the known results but also discover new ones. We believe progress in understanding P-schemes 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):
  • Umans, Christopher M.
Thesis Committee:
  • Umans, Christopher M. (chair)
  • Schulman, Leonard J.
  • Vidick, Thomas Georges
  • Huang, Ming-Deh
Defense Date:22 May 2017
Record Number:CaltechTHESIS:06012017-013622968
Persistent URL:
Guo, Zeyu0000-0001-7893-4346
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10241
Deposited By: Zeyu Guo
Deposited On:02 Jun 2017 20:02
Last Modified:09 Jun 2017 21:23

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page