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

DOI10.4230/LIPICS.MFCS.2020.42arXiv2007.00512MaRDI QIDQ6344206FDOQ6344206

Zeyu Guo

Publication date: 1 July 2020

Abstract: Let $ildef(X)inmathbbZ[X]$ be a degree-$n$ polynomial such that $$ factorizes into $n$ distinct linear factors over $mathbb{F}_p$. We study the problem of deterministically factoring $f(X)$ over $mathbb{F}_p$ given $ildef(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 $ildef(X)$ is (permutation isomorphic to) a linear group $GleqmathrmGL(V)$ on the set $S$ of roots of $ildef(X)$, where $V$ is a finite-dimensional vector space over a finite field $mathbbF$ and $S$ is identified with a subset of $V$. In particular, when $|S|=|V{|}^{Omega(1)}$, the algorithm runs in time polynomial in $n^{logn/(loglogloglogn{)}^{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.

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6344206)