Improving the Berlekamp Algorithm for Binomials x n - a
Improving the Berlekamp Algorithm for Binomials x n - a
复制标题
改进二项式的 Berlekamp 算法 x n - a
DOI：
10.1007/978-3-642-31662-3_16
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Aichi Kudo
中科院分区：
文献类型：
--
作者：
Ryuichi Harasawa;Yutaka Sueyoshi;Aichi Kudo
在本文中，我们描述了有限域上单变量多项式分解Berlekamp算法的一种改进，用于有限域上二项式的分解。更准确地说，我们给出了一种直接求解方程的确定性算法，而不需要对相应的系数矩阵进行清除。我们表明，如果我们在提出改进的第一步之后应用Berlekamp算法的概率版本，使用所提出的方法进行二项分解是在操作中执行的。我们的方法在q的某些区域比已知方法渐近快，而在其他区域与已知方法一样快。
In this paper, we describe an improvement of the Berlekamp algorithm, a method for factoring univariate polynomials over finite fields, for binomialsxn−aover finite fields. More precisely, we give a deterministic algorithm for solving the equationdirectly without applying the sweeping-out method to the corresponding coefficient matrix. We show that the factorization of binomials using the proposed method is performed inoperations inif we apply a probabilistic version of the Berlekamp algorithm after the first step in which we propose an improvement. Our method is asymptotically faster than known methods in certain areas ofq,nand as fast as them in other areas.