论文标题
通过线性galois组在有限场上分解多项式：一种加法组合方法
Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach
论文作者
论文摘要
令$ \ tilde {f}（x）\ in \ mathbb {z} [x] $为gemal- $ n $ polythomial，以便$ f（x）：= \ tilde {f}（x）\ bmod p $ p $ p $ p $ p $ crominate to $ n $ n $ difints to $ n $线性因$ \ m m mathbbbb {f} _p $ {p $。我们研究了确定性分解$ f（x）$ a $ \ mathbb {f} _p $给定$ \ tilde {f}（x）$的问题。根据广义的Riemann假设（GRH），我们给出了改进的确定性算法，该算法计算$ f（x）$的完全分解，在$ \ tilde {f}（x）$的GALOIS组IS（X）$ IS（permain in permain Isomorphic to）的情况下，$ g \ leq g \ leq f \ leq \ leq \ natrm mathrm的$ n} $ $ \ tilde {f}（x）$，其中$ v $是有限的矢量空间$ \ mathbb {f} $和$ s $，并以$ 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.我们的结果也适用于Galois Group $ g $，与作者的最新算法相结合。 为了证明我们的主要结果，我们介绍了一个称为Linear $ m $ schemes的对象家族，并将$ f（x）$的问题减少到有关这些对象的组合问题上。然后，我们将从添加剂组合制剂中应用技术来获得改进的界限。我们的技术可能具有独立的利益。
Let $\tilde{f}(X)\in\mathbb{Z}[X]$ be a degree-$n$ polynomial such that $f(X):=\tilde{f}(X)\bmod p$ factorizes into $n$ distinct linear factors over $\mathbb{F}_p$. We study the problem of deterministically factoring $f(X)$ over $\mathbb{F}_p$ given $\tilde{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 $\tilde{f}(X)$ is (permutation isomorphic to) a linear group $G\leq \mathrm{GL}(V)$ on the set $S$ of roots of $\tilde{f}(X)$, where $V$ is a finite-dimensional vector space over a finite field $\mathbb{F}$ 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.
