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

Chessboard Game and Algorithm for Factorization of Polynomials over F_2

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

The factorization problem of a polynomial over finite field F2 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.