matlab有限域上的运算

-1 有限域根底知识1.1 有限域Galois域的构造令p为一个素数. 则对任意的一个正整数n，存在一个特征为p，元素个数为pn的有限域GF(pn).注：任意一个有限域，其元素的个数一定为pn，其中p为一个素数有限域的特征，n为一个正整数.例1有限域GF(p)令p为一个素数，集合GF(p)=Zp=0,1,2,p1.在GF(p)上定义加法和乘法分别为模p加法和模p乘法，即任意的a,bGF(p)，ab=(a+b)modp, ab=(ab)modp则<GF(p),>为一个有p个元素的有限域，其中零元素为0，单位元为1.令a为GF(p)中的一个非零元素. 由于gcd(a,p)=1，因此，存在整数b,c，使得ab+pc=1. 由此得到a的逆元为a1=bmodp.域GF(p)称为一个素域(prime field).例注1：给定a和p，例1中的等式ab+pc=1可以通过扩展的欧几里得除法得到，从而求得GF(p)中任意非零元素的逆元.例2有限域GF(pn)从GF(p)出发，对任意正整数n，n2，我们可以构造元素元素个数为pn的有限域GF(pn)如下：令g(*)为一个GF(p)上次数为n的不可约多项式，集合GF(pn)=GF(p)*/g(*)=a0+a1*+a2*2+an1*n1 | aiGF(p),0in1在GF(pn)上定义加法和乘法分别为模g(*)加法和模g(*)乘法，即任意的a(*),b(*)GF(pn)，a(*)b(*)=a(*)+b(*), a(*)b(*)=(a(*)b(*)modg(*)则<GF(pn),>为一个有pn个元素，特征为p的有限域，其中零元素为GF(p)中的0，单位元为GF(p)中的1.令a(*)为GF(pn)中的一个非零元素. 由于gcd(a(*),g(*)=1，因此，存在GF(p)上的多项式b(*),c(*)，使得a(*)b(*)+g(*)c(*)=1. 由此得到a(*)的逆元为a1(*)=b(*)modg(*).域GF(pn)称为GF(p)的n次扩域(e*tension field)，而GF(p)称为GF(pn)的子域(subfield).例注2.1：给定GF(p)上的多项式a(*)和g(*)，例2中的等式a(*)b(*)+g(*)c(*)=1可以通过扩展的欧几里得除法得到，从而求得GF(pn)中任意非零元素的逆元.例注2.2：设GF(q)是一个含有q个元素的有限域. 对任意正整数n, GF(q)上的n次不可约多项式一定存在. 更进一步，GF(q)上首项系数为1的n次不可约多项式的个数为Nq(n)=1nd|n(nd)qd=1nd|n(d)qn/d其中为Moebius函数，定义为(m)=1(1)k0如果m=1如果m=p1p2pk,其中p1,p2,pk为互不一样的素数其它1.2 有限域的性质令GF(q)是一个含有q个元素的有限域，Fq=GF(q)0为有限域GF(q)中所有非零元素构成的集合. 则在乘法之下Fq是一个有限循环群. 循环群Fq的一个生成元称为有限域GF(q)的一个本原元.假设GF(q)为一个本原元，则GF(q)=0,1,2,q2并且q1=1，即q=.定义：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个含有p个元素的子域p不一定为素数，GF(q). 则GF(p)上以为根，首项系数为1，并且次数最低的多项式称为在GF(p)上的极小多项式(minimal polynomial of over GF(p). 特别地，假设GF(q)为GF(q)的一个本原元，则在GF(p)上的极小多项式称为GF(p)上的一个本原多项式(primitive polynomial for GF(q) over GF(p).定义注1：对任意的GF(q)，在GF(p)上的极小多项式存在并且唯一，并且在GF(p)上的极小多项式为GF(p)上的一个不可约多项式.定义注2：设GF(q)，则和p在GF(p)上具有一样的极小多项式. 更进一步，集合B()=,p,p2,p3,pi,中的元素具有一样的极小多项式. 设q=pn，则pn=. 因此，集合B()中互不一样的元素的个数记为r不超过n. 可以证明，为GF(q)的一个本原元当且仅当r=n.定理：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个含有p个元素的子域. 设GF(q)，r为满足pr=的最小正整数. 则在GF(p)上的极小多项式g(*)是一个r次不可约多项式，并且B()=,p,p2,pr1中的元素为g(*)在GF(q)上的所有不同的根，即g(*)=(*)(*p)(*p2)(*pr1).注：r的计算方法如下：设在Fq中的阶为k. 集合Zk=m | 0mk1,gcd(m,k)=1在模k乘法运算下是一个含有(k)个元素的有限群其中为欧拉(Euler)函数. 则r等于pmodk在Zk中的阶.推论：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个含有p个元素的子域. 设|GF(q)|=pn，即q=pn. 设GF(q)为GF(q)的一个本原元，则在GF(p)上的极小多项式g(*)的次数为n，并且g(*)=(*)(*p)(*p2)(*pn1).更进一步，,p,p2,pn1均为GF(q)的本原元.注：设GF(p)是一个含有p个元素的有限域，n是任意一个正整数，则GF(p)上的n次本原多项式一定存在. 更进一步，GF(p)上的首项系数为1的n次本原多项式的个数为(pn1)n，其中为欧拉函数.例3考虑二元域GF(2)上的不可约多项式p()=3+1，构造有限域GF(23)=GF(2)/p()=0,1,+1,2,2+1,2+,2+1.容易验证，,2,3,4,5,6都是GF(23)的本原元. GF(2)上的首项系数为1的3次本原多项式有两个，分别为 (i) ,2,4在GF(2)上的极小多项式g(*)=(*+)(*+2)(*+4)=*3+*+1(ii) 3,5,6在GF(2)上的极小多项式g(*)=*3+*2+1有限域GF(p)上的本原多项式一定是GF(p)上的不可约多项式；但是，GF(p)上的不可约多项式不一定是GF(p)上的本原多项式. 定理：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个含有p个元素的子域，g(*)是GF(p)上的一个不可约多项式. 则g(*)为GF(p)上的本原多项式当且仅当g(*)在GF(q)上的根都是GF(q)的本原元.下面例子说明不可约多项式不一定是本原多项式.例4考虑二元域GF(2)上的不可约多项式p(*)=*4+*3+*2+*+1，构造有限域GF(24)=GF(2)*/p(*)=a+b*+c*2+d*3 | a,b,c,dGF(2).显然，*GF(24). 由于*5=1，即*的阶为5，因此，*不是GF(24)的本原元. 于是，p(*)不是GF(2)上的本原多项式. 另外，可以验证*+1是GF(24)的本原元.2 Matlab 中的有限域计算函数Matlab 中自带的有限域的计算是在GF(2m)上进展的，即在二元域GF(2)的扩域中进展计算，其中1m16. 由"1.1 有限域的构造的"例2可知，我们只需先找到一个GF(2)上的m次不可约多项式g(*)，得到集合GF(2)*/g(*)，然后定义其上的加法和乘法分别为模g(*)加法和模g(*)乘法，即得到有限域GF(2m).然而，这样得到的有限域GF(2m)中，元素*未必是本原元，这将给后面的乘法运算带来很多麻烦. 因此，在不可约多项式g(*)的挑选上，我们最好选择一个本原多项式. 这其实就是 Matlab 中的做法.Matlab 中GF(2m)的元素：在 Matlab 中GF(2m):=GF(2)D/p(D)，其中p(D)为一个GF(2)上的m次本原多项式. GF(2m)=am1Dm1+am2Dm2+a1D+a0, | aiGF(2),0im1因此，每个GF(2m)中的元素本质上是一个次数小于m的多项式，每个元素和多项式之间有"1-1对应关系. 例如，取m=3和本原多项式p(D)=D3+D+1，则我们得到有限域GF(23)，其中的元素和多项式之间的对应关系如下：GF(23)GF(2)D/p(D)二进制00000110012D0103D+10114D21005D2+11016D2+D1107D2+D+1111GF(2)上的多项式由系数组成的二进制所对应的十进制数字来表示. 例如，多项式p(D)=D3+D+1的系数组成的二进制为1011，因此，多项式p(D)表示为数字11.2.1 定义有限域数组在 Matlab 中，函数gf用来定义一个有限域数组，函数申明如下：*_GF = GF(*,M,PRIM_POLY)函数创立有限域GF(2M)上的一个数组，使用的GF(2)上的M次本原多项式为PRIM_POLY；M是一个1至16之间的整数；数组*中的元素为0至2M1之间的数. 例如，生成有限域GF(23)中的所有元素，并令本原多项式为p(D)=D3+D2+1.>> GF8 = gf(0:7,3,13)GF8 = GF(23) array. Primitive polynomial = D3+D2+1 (13 decimal)Array elements = 0 1 2 3 4 5 6 7如果不指定本原多项式，则 Matlab 将使用默认本原多项式. 例如>> gf(0:7,3)ans = GF(23) array. Primitive polynomial = D3+D+1 (11 decimal)Array elements = 0 1 2 3 4 5 6 7在这里例子中，Matlab 使用了3次本原多项式D3+D+1.如果不指定次数M和本原多项式PRIM_POLY，则生成二元域GF(2)中的元素.>> gf(0:1)ans = GF(2) array. Array elements = 0 1生成的有限域中的数组可以参与运算+、.、.、等). 注意：参与运算的操作数必须来自同一个有限域，用于生成有限域的本原多项式也必须一样！一个典型的例子是计算有限域的乘法表如下：>> GF8 = gf(0:7,3)GF8 = GF(23) array. Primitive polynomial = D3+D+1 (11 decimal)Array elements = 0 1 2 3 4 5 6 7>> GF8'*GF8ans = GF(23) array. Primitive polynomial = D3+D+1 (11 decimal)Array elements = 0 0 0 0 0 0