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则 为一个有 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(x) 为一个 GF(p) 上次数为 n 的不可约多项式，集合 GF(pn)=GF(p)x/g(x)=a0+a1x+a2x2+an1xn1|aiGF(p),0in1在 GF(pn) 上定义加法 和乘法 分别为模 g(x) 加法和模 g(x) 乘法，即任意的 a(x),b(x)GF(pn)， a(x)b(x)=a(x)+b(x),a(x)b(x)=(a(x)b(x)modg(x)则 为一个有 pn 个元素，特征为 p 的有限域，其中零元素为 GF(p) 中的 0，单位元为 GF(p) 中的 1.令 a(x) 为 GF(pn) 中的一个非零元素. 由于 gcd(a(x),g(x)=1，因此，存在 GF(p) 上的多项式 b(x),c(x)，使得 a(x)b(x)+g(x)c(x)=1. 由此得到 a(x) 的逆元为 a1(x)=b(x)modg(x).域 GF(pn) 称为 GF(p) 的（n 次）扩域(extension field)，而 GF(p) 称为 GF(pn) 的子域(subfield).例注2.1： 给定 GF(p) 上的多项式 a(x) 和 g(x)，例2中的等式 a(x)b(x)+g(x)c(x)=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(x) 是一个 r 次不可约多项式，并且 B()=,p,p2,pr1中的元素为 g(x) 在 GF(q) 上的所有不同的根，即 g(x)=(x)(xp)(xp2)(xpr1).注：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(x) 的次数为 n，并且 g(x)=(x)(xp)(xp2)(xpn1).更进一步，,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(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,dGF(2).显然，xGF(24). 由于 x5=1，即 x 的阶为 5，因此，x 不是 GF(24) 的本原元. 于是， p(x) 不是 GF(2) 上的本原多项式. 另外，可以验证 x+1 是 GF(24) 的本原元.2 Matlab 中的有限域计算函数Matlab 中自带的有限域的计算是在 GF(2m) 上进行的，即在二元域 GF(2) 的扩域中进行计算，其中 1m16. 由 “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)=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 用来定义一个有限域数组，函数申明如下：X_GF = GF(X,M,PRIM_POLY)函数创建有限域 GF(2M) 上的一个数组，使用的 GF(2) 上的 M 次本原多项式为 PRIM_POLY； M 是一个 1 至 16 之间的整数；数组 X 中的元素为 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 0 0 0 1 2 3 4 5 6 7 0 2 4 6 3 1 7 5 0 3 6 5 7 4 1 2 0 4 3 7 6 2 5 1 0 5 1 4 2 7 3 6 0 6 7 1 5 3 2 4 0 7 5 2 1 6 4 3 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 GF8*GF8Warning: Lookup tables not defined for this order 23 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 35 In gf.mtimes at 20ans = GF(23) array. Primitive polynomial = D3+D2+1 (13 decimal)Array elements = 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 0 2 4 6 5 7 1 3 0 3 6 5 1 2 7 4 0 4 5 1 7 3 2 6 0 5 7 2 3 6 4 1 0 6 1 7 2 4 3 5 0 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 23 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) = D3+D1+1D3+D2+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 = 0【精品文档】第 11 页