m a t l a b有限域上的运算1 有限域基础知识1.1 有限域（Galois域）的构造令p为一个素数. 则对任意的一个正整数n，存在一个特征为p，元素个数为p n的有限域GF(p n).注：任意一个有限域，其元素的个数一定为p n，其中p为一个素数（有限域的特征），n为一个正整数.例1（有限域GF(p)）令p为一个素数，集合GF(p)=Z p={0,1,2,…,p−1}.在GF(p)上定义加法⊕和乘法⊙分别为模p加法和模p乘法，即任意的a,b∈GF(p)，a⊕b=(a+b)mod p, a⊙b=(a⋅b)mod p则<GF(p),⊕,⊙>为一个有p个元素的有限域，其中零元素为0，单位元为1.令a为GF(p)中的一个非零元素. 由于gcd(a,p)=1，因此，存在整数b,c，使得ab+pc=1. 由此得到a的逆元为a−1=b mod p.域GF(p)称为一个素域(prime field).例注1：给定a和p，例1中的等式ab+pc=1可以通过扩展的欧几里得除法得到，从而求得GF(p)中任意非零元素的逆元.例2（有限域GF(p n)）从GF(p)出发，对任意正整数n，n≥2，我们可以构造元素元素个数为p n的有限域GF(p n)如下：令g(x)为一个GF(p)上次数为n的不可约多项式，集合GF(p n)=GF(p)[x]/⟨g(x)⟩={a0+a1x+a2x2+⋯+a n−1x n−1 | a i∈GF(p),0≤i≤n−1}在GF(p n)上定义加法⊕和乘法⊙分别为模g(x)加法和模g(x)乘法，即任意的a(x),b(x)∈GF(p n)，a(x)⊕b(x)=a(x)+b(x), a(x)⊙b(x)=(a(x)⋅b(x))mod g(x)则<GF(p n),⊕,⊙>为一个有p n个元素，特征为p的有限域，其中零元素为GF(p)中的0，单位元为GF(p)中的1.令a(x)为GF(p n)中的一个非零元素. 由于gcd(a(x),g(x))=1，因此，存在GF(p)上的多项式b(x),c(x)，使得a(x)b(x)+g(x)c(x)=1. 由此得到a(x)的逆元为a−1(x)=b(x)mod g(x).域GF(p n)称为GF(p)的（n次）扩域(extension field)，而GF(p)称为GF(p n)的子域(subfield).例注2.1：给定GF(p)上的多项式a(x)和g(x)，例2中的等式a(x)b(x)+g(x)c(x)=1可以通过扩展的欧几里得除法得到，从而求得GF(p n)中任意非零元素的逆元.例注2.2：设GF(q)是一个含有q个元素的有限域. 对任意正整数n,GF(q)上的n次不可约多项式一定存在. 更进一步，GF(q)上首项系数为1的n次不可约多项式的个数为N q(n)=1n∑d|nμ(nd)q d=1n∑d|nμ(d)q n/d其中μ为Moebius函数，定义为μ(m)=⎧⎩⎨1(−1)k0如果m=1如果m=p1p2⋯p k,其中p1,p2,…,p k为互不相同的素数其它1.2 有限域的性质令GF(q)是一个含有q个元素的有限域，F∗q=GF(q)∖{0}为有限域GF(q)中所有非零元素构成的集合. 则在乘法之下F∗q是一个有限循环群. 循环群F∗q的一个生成元称为有限域GF(q)的一个本原元.若α∈GF(q)为一个本原元，则GF(q)={0,1,α,α2,…,αq−2}并且αq−1=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,…,αp i,…}中的元素具有相同的极小多项式. 设q=p n，则αp n=α. 因此，集合B(α)中互不相同的元素的个数（记为r）不超过n. 可以证明，α为GF(q)的一个本原元当且仅当r=n.定理：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个含有p个元素的子域. 设α∈GF(q)，r为满足αp r=α的最小正整数. 则α在GF(p)上的极小多项式g(x)是一个r次不可约多项式，并且B(α)={α,αp,αp2,…,αp r−1}中的元素为g(x)在GF(q)上的所有不同的根，即g(x)=(x−α)(x−αp)(x−αp2)⋯(x−αp r−1).注：r的计算方法如下：设α在F∗q中的阶为k. 集合Z∗k={m | 0≤m≤k−1,gcd(m,k)=1}在模k乘法运算下是一个含有φ(k)个元素的有限群（其中φ为欧拉(Euler)函数）. 则r等于p mod k在Z∗k中的阶.推论：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个含有p个元素的子域. 设|GF(q)|=p n，即q=p n. 设α∈GF(q)为GF(q)的一个本原元，则α在GF(p)上的极小多项式g(x)的次数为n，并且g(x)=(x−α)(x−αp)(x−αp2)⋯(x−αp n−1).更进一步，α,αp,αp2,…,αp n−1均为GF(q)的本原元.注：设GF(p)是一个含有p个元素的有限域，n是任意一个正整数，则GF(p)上的n次本原多项式一定存在. 更进一步，GF(p)上的首项系数为1的n次本原多项式的个数为φ(p n−1)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(x)=(x+α)(x+α2)(x+α4)=x3+x+1(ii) α3,α5,α6在GF(2)上的极小多项式g(x)=x3+x2+1有限域GF(p)上的本原多项式一定是GF(p)上的不可约多项式；但是，GF(p)上的不可约多项式不一定是GF(p)上的本原多项式.定理：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个含有p个元素的子域，g(x)是GF(p)上的一个不可约多项式. 则g(x)为GF(p)上的本原多项式当且仅当g(x)在GF(q)上的根都是GF(q)的本原元.下面例子说明不可约多项式不一定是本原多项式.例4考虑二元域GF(2)上的不可约多项式p(x)=x4+x3+x2+x+1，构造有限域GF(24)=GF(2)[x]/⟨p(x)⟩={a+bx+cx2+dx3 | a,b,c,d∈GF(2)}.显然，x∈GF(24). 由于x5=1，即x的阶为5，因此，x不是GF(24)的本原元. 于是，p(x)不是GF(2)上的本原多项式. 另外，可以验证x+1是GF(24)的本原元.2 Matlab 中的有限域计算函数Matlab 中自带的有限域的计算是在GF(2m)上进行的，即在二元域GF(2)的扩域中进行计算，其中1≤m≤16.由“1.1 有限域的构造” 的“例2” 可知，我们只需先找到一个GF(2)上的m次不可约多项式g(x)，得到集合GF(2)[x]/⟨g(x)⟩，然后定义其上的加法和乘法分别为模g(x)加法和模g(x)乘法，即得到有限域GF(2m). 然而，这样得到的有限域GF(2m)中，元素x未必是本原元，这将给后面的（乘法）运算带来很多麻烦. 因此，在不可约多项式g(x)的挑选上，我们最好选择一个本原多项式. 这其实就是 Matlab 中的做法.Matlab 中GF(2m)的元素：在 Matlab 中GF(2m):=GF(2)[D]/⟨p(D)⟩，其中p(D)为一个GF(2)上的m次本原多项式.GF(2m)={a m−1D m−1+a m−2D m−2+⋯+a1D+a0, | a i∈GF(2),0≤i≤m−1}因此，每个GF(2m)中的元素本质上是一个次数小于m的多项式，每个元素和多项式之间有“1-1”对应关系. 例如，取m=3和本原多项式p(D)=D3+D+1，则我们得到有限域GF(23)，其中的元素和多项式之间的对应关系如下：GF(23)GF(2)[D]/⟨p(D)⟩二进制0 00001 10012 D0103 D+10114 D21005 D2+11016 D2+D110GF(23)GF(2)[D]/⟨p(D)⟩二进制7 D2+D+1111GF(2)上的多项式由系数组成的二进制所对应的（十进制）数字来表示. 例如，多项式p(D)=D3+D+1的系数组成的二进制为1011，因此，多项式p(D)表示为数字11.2.1 定义有限域数组在 Matlab 中，函数gf用来定义一个有限域数组，函数申明如下：X_GF = GF(X,M,PRIM_POLY)函数创建有限域GF(2M)上的一个数组，使用的GF(2)上的M次本原多项式为PRIM_POLY；M是一个1至16之间的整数；数组X中的元素为0至2M−1之间的数.例如，生成有限域GF(23)中的所有元素，并令本原多项式为p(D)=D3+D2+1.>> GF8 = gf(0:7,3,13)GF8 = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal) Array elements =0 1 2 3 4 5 6 7如果不指定本原多项式，则 Matlab 将使用默认本原多项式. 例如>> gf(0:7,3)ans = GF(2^3) array. Primitive polynomial = D^3+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(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements =0 1 2 3 4 5 6 7>> GF8'*GF8ans = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements =0 0 0 0 0 0 0 00 1 2 3 4 5 6 70 2 4 6 3 1 7 50 3 6 5 7 4 1 20 4 3 7 6 2 5 10 5 1 4 2 7 3 60 6 7 1 5 3 2 40 7 5 2 1 6 4 3>> GF8 = gf(0:7,3,13)GF8 = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal) Array elements =0 1 2 3 4 5 6 7>> GF8'*GF8Warning: Lookup tables not defined for this order 2^3 andprimitive polynomial 13. Arithmetic still workscorrectly but multiplication, exponentiation, andinversion of elements is faster with lookup tables.Use gftable to create and save the lookup tables.> In gf.gettables at 35In gf.mtimes at 20ans = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal) Array elements =0 0 0 0 0 0 0 00 1 2 3 4 5 6 70 2 4 6 5 7 1 30 3 6 5 1 2 7 40 4 5 1 7 3 2 60 5 7 2 3 6 4 10 6 1 7 2 4 3 50 7 3 4 6 1 5 2在这里我们用两个不同的本原多项式构造有限域GF(23)，得到两张不同的乘法表.注1：当我们计算GF(2)[D]/⟨D3+D2+1⟩的乘法表时，Matlab 给产生一个警告“Warning: Lookup tables not defined for this order 2^3 and primitive polynomial 13.” 从警告中我们可以看出，Matlab 中有限域的乘法是通过查表来完成的，这样可以显著地提高计算的速度. 我们可以通过命令gftable来创建并保存查找表格.注2：用本原多项式D3+D+1和D3+D2+1生成两个不同的元素个数为8的有限域，然而这两个有限域是同构的. 一般地，我们有如下有限域同构定理：定理：任意两个元素个数相同的有限域一定同构.与本原元多项式相关的函数primpoly函数primpoly用于计算GF(2)上的本原多项式，函数申明如下：PR = PRIMPOLY(M, OPT, 'nodisplay')其中M为本原多项式的次数，其取值为2至16之间的整数；选项OPT的定义如下：OPT = 'min' 给出一个权值最小的本原多项式OPT = 'max' 给出一个权值最大的本原多项式OPT = 'all' 给出所有的本原多项式OPT = L 给出所有权值为L的本原多项式字符串‘nodisplay’用于关闭默认的本原多项式显示方式.例如，输出GF(2)上所有次数为3的本原多项式.>> primpoly(3,'all')Primitive polynomial(s) =D^3+D^1+1D^3+D^2+1ans =1113>> primpoly(3,'all','nodisplay')ans =1113isprimitive函数isprimitive用来检查GF(2)上的多项式是否为本原多项式，函数申明如下：CK = ISPRIMITIVE(A)其中A为一个表示多项式的数字，并且表示的多项式的次数不能超过16. 如果A为本原多项式，则返回1；否则返回0.例如，检查多项式D3+D2+1和D3+D2+D+1是否为本原多项式如下：>> isprimitive(13)ans =1>> isprimitive(15)ans =。