Factoring univariate polynomials over the rationals
Factoring univariate polynomials over the rationals
复制标题
在有理数上分解单变量多项式
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. V. Hoeij
中科院分区：
文献类型：
--
作者：
A. Novocin;M. V. Hoeij
我们给出了一种将多项式f分解为一元有理系数的算法。我们的算法是van Hoeij[van Hoeij]分解算法的Belabas[Belabas]版本的变体。我们的算法不仅在Belabas的基础上有一个实用的加速，而且还允许我们证明一个新的分解多项式的复杂性结果。
Van Hoeij算法遵循Zassenhaus[Zass]的方法，分解f mod一个素数，Hensel提升局部因子。Van Hoeij算法的实际加速来自于使用LLL[LLL]算法来解决解码的指数重组问题，该问题是局部因素的组合形成真实因素。然而，在van Hoeij的方法中，LLL的成本很难确定(事实上，[van Hoeij]只证明了终止性，并没有试图找到复杂性)。
Belabas发现了van Hoeij算法的一个微调[Belabas]，它几乎优化了实际运行时间，但仍然没有提供一个很好的LLL成本界限。在[BHKS]中，这两个变体都被证明具有多项式的复杂性，但这些界限仍然大得令人不满意，并且几乎不能解释这些算法的行为。我们的算法在以下几个方面对Belabas的方法进行了改进：我们做了一个实用的改进，确保Hensel提升总是最小化的。我们包括一个决策过程，它允许我们将算法中的LLL开关总数限定为O(R3)，其中r是局部因素的数量。这与f的次数和系数大小无关。
在这张海报中，我们展示了新算法的概述，并简要介绍了我们证明的风格。有关开关界O(R3)的全部细节，请参见[Novocin]。使用浮点LL1[L2]和一些小的更改，我们可以显示LLL的开销是O(R7)。我们还在写下证明的细节，证明我们的算法的新的总复杂性是O(R7)。
We present an algorithm for factoring a polynomial, f , in one variable with rational coefficients. Our algorithm is a variant of the Belabas [Belabas] version of the van Hoeij [van Hoeij] factoring algorithm. Our algorithm not only contains a practical speed-up over Belabas' but it also allows us to prove a new complexity result for factoring polynomials.
The van Hoeij algorithm follows Zassenhaus' [Zass] approach by factoring f mod a prime number and Hensel Lifting the local factors. The practical speed-up in van Hoeij's algorithm comes from using the LLL [LLL] algorithm to solve the exponential recombination problem of decicing which combination of local factors form the true factors. However, the cost of LLL in van Hoeij's approach has been difficult to bound (in fact [van Hoeij] only proves termination and makes no attempt at finding a complexity).
Belabas found a fine-tuning [Belabas] of van Hoeij's algorithm which nearly optimizes the practical running times, but still does not provide a good bound for the LLL costs. In [BHKS] both variants were shown to have polynomial complexity, but these bounds are still unsatisfactorily large and do little to illuminate the behavior of these algorithms. Our algorithm improves Belabas' approach in the following ways: We make a practical improvement which ensures that Hensel Lifting is always minimized. We include a decision making process which allows us to bound the total number of LLL switches in the algorithm by O(r3), where r is the number of local factors. This is independent of both degree and coefficient size of f..
In this poster we present an overview of the new algorithm and give a brief look at the style of our proofs. For the full details of the switch bound O(r3) see [Novocin]. Using the Floating-Point LLL [L2] and some minor changes we can show the LLL costs are O(r7). We are still writing down the details of a proof that the new total complexity of our algorithm is O(r7).