文章基本信息

标题：Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach
本地全文：下载
作者：guo:LIPIcs: : , author {Zeyu Guo
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：42:1-42:14
DOI：10.4230/LIPIcs.MFCS.2020.42
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Let fÌf(X) â^^ â"¤[X] be a degree-n polynomial such that f(X): = fÌ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Ì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Ìf(X) is (permutation isomorphic to) a linear group G â¤ GL(V) on the set S of roots of fÌ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.
关键词：polynomial factoring; permutation group; finite field; algebraic combinatorics; additive combinatorics; derandomization