Schemes for deterministic polynomial factoring
Schemes for deterministic polynomial factoring
复制标题
确定性多项式因式分解方案
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Nitin Saxena
中科院分区：
文献类型：
--
作者：
G. Ivanyos;Marek Karpinski;Nitin Saxena
在这项工作中，我们将分解多项式（超过有限字段）的确定性复杂性与某些组合对象联系起来，我们称为M-Schemes，是置换基团的概括。我们设计了已知的条件确定性次指数时间多项式保理算法的新概括，以获得基础的M-Scheme。然后，我们证明了理解M-Shemes的进展与假设多项式的确定性复杂性的改善如何相关，假设是普遍的Riemann假设（GRH）。
特别是，我们给出了第一个确定性的多项式时间算法（假设GRH）找到质量n多项式的非平凡因子，其中（n-1）是恒定平滑的数字。我们使用有关质量数量的关联方案的结构定理，Hanaki和Uno（2006）通过表示理论方法证明了这一点。
In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects, we call m-schemes, that are generalizations of permutation groups. We design a new generalization of the known conditional deterministic subexponential time polynomial factoring algorithm to get an underlying m-scheme. We then demonstrate how progress in understanding m-schemes relate to improvements in the deterministic complexity of factoring polynomials, assuming the Generalized Riemann Hypothesis (GRH).
In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n-1) is a constant-smooth number. We use a structural theorem about association schemes on a prime number of points, which Hanaki and Uno (2006) proved by representation theory methods.