棋盘游戏与有限域上多项式分解算法

将有限域F_2上多项式分解问题转化为一种对应的棋盘游戏,利用后者的性质设计了一个F_2上m+n-2次多项式f(x)分解为一个m-1次多项式与一个n-1次多项式的判断、分解算法,并对算法的复杂度进行了分析.算法的一个优势是,如果f(x)不能按要求分解,也可以找到一个与f(x)相近(这里指系数相异项较少)的多项式的分解.

Chessboard Game and Algorithm for Factorization of Polynomials over F_2

The factorization problem of a polynomial over finite field F_2 is transformed to a chessboard game and then an algorithm is designed to judge and decompose a given polynomial f(x) as the product of two polynomial with given degrees.The complexity of the algorithm is then analysised.One advantage of this algorithm is that we can find a factorization of a polynomial which is close to f(x)(here refers to have less different coefficients with f(x)) when such factorization for f(x) is not feasible.