matlab有限域上的运算

《matlab有限域上的运算》由会员分享，可在线阅读，更多相关《matlab有限域上的运算（12页珍藏版）》请在金锄头文库上搜索。

1、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) 中的

2、一个非零元素. 由于 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+a

3、n1xn1|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(

4、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)=1n

5、d|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

6、个元素的子域（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(

7、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(

8、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)(x

9、p)(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

10、) ,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) 的本原元.

11、下面例子说明不可约多项式不一定是本原多项式.例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. 由

12、 “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)

13、 上的 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+

14、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在这里例