License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.42
URN: urn:nbn:de:0030-drops-127082
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12708/
Go to the corresponding LIPIcs Volume Portal

Guo, Zeyu

Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach

pdf-format:
LIPIcs-MFCS-2020-42.pdf (0.6 MB)

Abstract

Let f̃(X) ∈ ℤ[X] be a degree-n polynomial such that f(X): = f̃(X)od p factorizes into n distinct linear factors over ?_p. We study the problem of deterministically factoring f(X) over ?_p given f̃(X). Under the generalized Riemann hypothesis (GRH), we give an improved deterministic algorithm that computes the complete factorization of f(X) in the case that the Galois group of f̃(X) is (permutation isomorphic to) a linear group G ≤ GL(V) on the set S of roots of f̃(X), where V is a finite-dimensional vector space over a finite field ? and S is identified with a subset of V. In particular, when |S| = |V|^{Ω(1)}, the algorithm runs in time polynomial in n^{log n/(log log log log n)^{1/3}} and the size of the input, improving Evdokimov’s algorithm. Our result also applies to a general Galois group G when combined with a recent algorithm of the author.
To prove our main result, we introduce a family of objects called linear m-schemes and reduce the problem of factoring f(X) to a combinatorial problem about these objects. We then apply techniques from additive combinatorics to obtain an improved bound. Our techniques may be of independent interest.

BibTeX - Entry

@InProceedings{guo:LIPIcs:2020:12708,
  author =	{Zeyu Guo},
  title =	{{Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12708},
  URN =		{urn:nbn:de:0030-drops-127082},
  doi =		{10.4230/LIPIcs.MFCS.2020.42},
  annote =	{Keywords: polynomial factoring, permutation group, finite field, algebraic combinatorics, additive combinatorics, derandomization}
}

Keywords: polynomial factoring, permutation group, finite field, algebraic combinatorics, additive combinatorics, derandomization
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI