Guo, Zeyu
Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach
Abstract
Let f̃(X) ∈ ℤ[X] be a degreen 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 finitedimensional 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 mschemes 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:142:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12708},
URN = {urn:nbn:de:0030drops127082},
doi = {10.4230/LIPIcs.MFCS.2020.42},
annote = {Keywords: polynomial factoring, permutation group, finite field, algebraic combinatorics, additive combinatorics, derandomization}
}
18.08.2020
Keywords: 

polynomial factoring, permutation group, finite field, algebraic combinatorics, additive combinatorics, derandomization 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 