文章基本信息

标题：Deterministic Polynomial Factoring and Association Schemes
本地全文：下载
作者：Manuel Arora ; Gábor Ivanyos ; Marek Karpinski 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The problem of finding a nontrivial factor of a polynomial f(x) over a finite field Fq has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the art by focusing on prime degree polynomials; let n be the degree. If (n−1) has a `large' r-smooth divisor s, then we find a nontrivial factor of f(x) in deterministic poly(nrlogq) time; assuming GRH and that s=(n2r . Thus, for r=O(1) our algorithm is polynomial time. Further, for r=(loglogn) there are infinitely many prime degrees n for which our algorithm is applicable and better than the best known; assuming GRH.
关键词：Algebra Decomposition, Association Scheme, Cyclotomic Scheme, finite field, GRH, Linnik, matching, Polynomial Factoring, representation theory, Smooth Number, tensor