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

《棋盘游戏与有限域上多项式分解算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第44卷第6期数学的实践与认识Vo1．44．No．62014年3月MATHEMATICSINPRACTICEANDTHE0RYMar．．2014棋盘游戏与有限域上多项式分解算法陈玺，屈龙江，海昕，李超，z(1．国防科技大学理学院数学与系统科学系，湖南长沙410073)(2．信息保障科学与技术实验室，北京100072)摘要：将有限域F2上多项式分解问题转化为一种对应的棋盘游戏，利用后者的性质设计了一个F2上m+几一2次多项式f(x)分解为一个m一1次多项式与一个礼一1次多项式的判断、分解算法，并对算法的复杂度进行

2、了分析．算法的一个优势是，如果．厂()不能按要求分解，也可以找到一个与f(x)相近(这里指系数相异项较少)的多项式的分解．关键词：棋盘游戏；有限域；多项式分解；搜索算法有限域上的多项式理论是有限域理论的重要组成部分，在编码密码、有限几何、组合设计等应用中也有着非常重要的地位，这些年来受到了很多研究，详见I1-2】及其中的参考文献．多项式的分解是有限域上多项式理论的重要内容，应用也很广泛．现在已有一些有限域上的多项式分解算法，其中Berlekamp算法最为著名[1{3]．本文是对有限域上多项式分解的研究．与以往研

3、究不同的是，本文首先将有限域上多项式分解问题转化为一种对应的棋盘游戏，然后研究了该棋盘游戏的性质，并基于此设计了一个F2上m十礼一2次多项式f(x)分解为一个m一1次多项式与一个n一1次多项式的判断、分解算法．接着对算法的复杂度进行了分析，尽管该算法的复杂度较高，不太实用，但其有一个优势：如果f(x)不能按要求分解，也可以找到一个与f(x)相近(这里指系数相异项较少)的多项式的分解．这种分解也可能在某些应用中有用．全文结构如下：第2节介绍与有限域上多项式分解对应的棋盘游戏，第3节在分析棋盘游戏性质的基础上，给出

4、了一个多项式分解算法，然后分析了算法的复杂度，最后一节总结并提出下一步值得研究的问题．1一个有趣的棋盘游戏与有限域上多项式分解算法让我们从一个有趣的小游戏开始．如图1所示，在一个6×6的棋盘中放满棋子，现允许去掉其中任意若干行若干列棋子(去掉哪些行列可以任意选择，但必须去掉完整一行或列)．问是否存在一种去掉棋子的方法使得棋盘每一条斜向右上45度的对角线上(共11条对角线)都有奇数枚棋子．为了便于描述，下文中都将这种斜向上45度的对角线称为副对角线．收稿日期：2013．08—07资助项目：国家自然科学基金(612

5、72484)；信息保障科学技术实验室开放基金(KJ一12—02)212数学的实践与认识44卷那么f(x)可以分解成F2上两个五次多项式的乘积，但这与．厂()是上的不可约多项式的事实矛盾，因此任何一种去掉棋子的方法都不可能使得每一条副对角线上都有奇数枚棋子．证毕．这个证明依赖于f(x)的不可约性．进一步，如果去掉棋子的方法存在的话，去掉棋子的方法也依赖于f(x)的分解．事实上，一般地，这样的游戏与有限域上多项式的分解(考虑顺序)是一一对应的．在一个m×n的棋盘中放满棋子，现允许去掉其中任意若干行若干列棋子(去掉哪

6、些行列可以任意选择，但必须去掉完整一行或列)．问是否存在一种去掉棋子的方法使得棋盘每一条副对角线上(从左上到右下共m+n一1条对角线)的棋子个数模2的余数分别为a2，a3，·一，am+n，ai∈{0，1J，i∈{2，⋯，m+凡}．设f(x)=∑ai+2x为上的某个次数不超过m+n一2的多项式．则与前面分析类似，每一种满足条件的棋子排列方法对应了将f(x)分解成一个不超过m一1次多项式l厂()与一个不超过n一1次多项式，2()的乘积的方法，棋盘上每一行是否被去掉对应了fl(X)的相应系数；每一列是否被去掉对应了，

7、2(z)的相应系数．反过来，若f(z)可以写成一个次数不超过m一1的多项式^()与一个次数不超过佗一1的多项式_厂2()的乘积的形式，那么将fl(x)与，2()的系数分别对应棋盘的行与列，X前系数为1说明第i+1行(列)有棋子，系数为0说明第i+1行(列)无棋子，则由f(x)的一个分解我们得到了达到目的状态的一种去掉棋子的方法．因此，这种棋盘游戏中去掉棋子的方法确实与有限域多项式的分解是一一对应的．=1++++X+··’。．●●●I●◆●●●●●●0ll●●●●◆●●I●●●●●●●●●II●●●●●●●●●I

8、l●●●●●●●■●●■。●●●●．．●●●●●●●●◆●●I●●●●●●●◆●●I●●●●●●●图3棋盘游戏与多项式分解对应例图2有限域上多项式分解的一个算法上一节已经说明棋盘游戏与有限域上多项式的分解有着一一对应关系，但是怎么得到多项式的分解，或者等价地说，怎么找到去掉棋子的方法，还没有讨论．显然，任何一种多项式分解算法，都可以给出一种去掉棋子的方法．1反过来，去掉棋子的算法也对应