《matlab有限域上的运算》由会员分享，可在线阅读，更多相关《matlab有限域上的运算（15页珍藏版）》请在金锄头文库上搜索。
1、1有限域基础知识有限域(Galois域)的构造令P为一个素数.则对任意的一个正整数n,存在一个特征为P,元素个数为 pn 的有限域 GF(pn).注：任意一个有限域，其元素的个数一定为pn，其中p为一个素数(有限域 的特征)，n为一个正整数.例1(有限域GF(P)令P为一个素数，集合GF(p)二Zp二0,1,2,，p- 1.在GF(p)上定义加法 和乘法分别为模p加法和模p乘法，即任意 的 a, beGF(p)，a b=(a+b)modp, ab=(a b)modp则GF(p),，为一个有p个元素的有限域，其中零元素为0，单位元 为1.令a为GF(p)中的一个非零元素.由于gcd(a, p)=
2、1,因此，存在整数 b,c，使得ab+pc二1.由此得到a的逆元为a- i=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/Dg(x) =a0+a1x+a2x2+- +an-1xn-1| aiwGF(p),OW i Wn- 1在GF(pn)上定
3、义加法和乘法分别为模g(x)加法和模g(x)乘 法，即任意的 a(x)b (x) e GF (pn),a(x)b (x)=a (x)+b (x), a(x) b (x) = (a (x) - b(x)modg(x)则GF(pn),，为一个有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) 的逆元为 a-1(x)=b(x)modg(x).域
4、GF(pn)称为 GF(p)的(n 次)扩域(extension field),而 GF(p)称 为 GF(pn)的子域(subfield).例注：给定GF(P)上的多项式a(x)和g(x),例2中的等式a(x)b(x)+g(x)c(x)=1 可以通过扩展的欧几里得除法得到，从而求得 GF(pn) 中任意非零元素的逆元.例注：设 GF(q) 是一个含有 q 个元素的有限域. 对任意正整数 n, GF(q) 上的n次不可约多项式一定存在.更进一步，GF(q)上首项系数为1的n 次不可约多项式的个数为Nq(n)=1nd|nU (nd)qd=1nd|nU (d)qn/d其中U为Moebius函数，定
5、义为U (m)二( 1)ko 如果m=1 如果m二P1P2Pk，其中 Pi，P2,，Pk为互不相同的素数其它有限域的性质令GF(q)是一个含有q个元素的有限域，F* q二GF(q) 0为有限域 GF(q)中所有非零元素构成的集合.则在乘法之下F* q是一个有限循环群. 循环群 F* q 的一个生成元称为有限域 GF(q) 的一个本原元 .若d GF(q)为一个本原元，则GF(q)二0,1,a,a2,，aq-2并且 aq- 1 = 1,即 aq=a.定义：设GF(q)是一个含有q个元素的有限域，GF(P)是GF(q)的一个 含有P个元素的子域(P不一定为素数),a eGF(q).则GF(P)上以
6、a 为根，首项系数为1,并且次数最低的多项式称为a在GF(P)上的极小多 项式(minimal polynomial of a over GF(p).特别地，若a eGF(q)为GF(q)的一个本原元，则a在GF(p)上的 极小多项式称为GF(p)上的一个本原多项式(p rimitive polynomial for GF(q) overGF(p).定义注1：对任意的a eGF(q)， a在GF(p)上的极小多项式存在并且 唯一，并且a在GF(p)上的极小多项式为GF(p)上的一个不可约多项式.定义注2：设awGF(q)，则a和 在GF(p)上具有相同的极小多 项式. 更进一步，集合B(a)
7、= a, ap, ap2, a,，0卩中的元素具有相同的极小多项式设q二pn，贝I apn=a.因此，集合B(a) 中互不相同的元素的个数(记为r)不超过n.可以证明，a为GF(q)的 一个本原元当且仅当r=n.定理：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个 含有p个元素的子域设a eGF(q)，r为满足apr=a的最小正整数. 则a在GF(p)上的极小多项式g(x)是一个r次不可约多项式，并且B(a)二a, ap, ap2,，apr 1中的元素为 g(x) 在 GF(q) 上的所有不同的根，即g(x) = (x- a)(x- ap)(x- ap2)(x- ap注：
8、r的计算方法如下：设a在F* q中的阶为k.集合Z* k=m | OWmWk- 1,gcd(m,k)=1在模k乘法运算下是一个含有e(k)个元素的有限群(其中e为欧拉(Euler)函数).则r等于pmodk在Z* k中的阶.推论：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个 含有p个元素的子域设|GF(q)|二Pn，即q=Pn设a wGF(q)为 GF(q)的个本原元，则a在GF(p)上的极小多项式g(x)的次数为 n,并且g(x) = (x- a)(x- ap)(x- ap2)(x- api).更进一步，a, ap，ap2,，apn-1均为GF(q)的本原元.注:设G
9、F(p)是一个含有p个元素的有限域，n是任意一个正整数，则GF(p) 上的n次本原多项式一定存在.更进一步，GF(p)上的首项系数为1的n 次本原多项式的个数为e (pn- i)n，其中e为欧拉函数.例3考虑二元域GF 上的不可约多项式p(a) = a3+a+1，构造有限域GF(23)=GF(2)a/Dp(a) 二0,1, a, a+1, a2, a2+1, a2+a,a2+a+1.容易验证，a，a 2，a 3，a 4，a 5，a 6都是GF(23)的本原元.GF(2)上的首项系数为 1 的 3 次本原多项式有两个，分别为(i) a,a2,a4 在 GF(2) 上的极小多项式g(x)=(x+a
10、)(x+a2)(x+a4)=x3+x+1(ii) a3,a5,a6 在 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 上的
11、不可约多项式p (x)=x4+x3+x2+x+1 ,构造有限 域GF(24)=GF(2)x/Dp(x) 二a+bx+cx2+dx3| a,b,c,dwGF(2).显然，XWGF（24）.由于x5=1，即X的阶为5,因此，X不是GF（24）的 本原元.于是，P（x）不是GF（2）上的本原多项式.另外，可以验证X+1是 GF（24）的本原元.2 Matlab中的有限域计算函数Mat lab中自带的有限域的计算是在GF （2m）上进行的，即在二元域GF（2） 的扩域中进行计算，其中WmW16由“有限域的构造”的“例2”可知，我们只需先找到一个GF（2）上的 m次不可约多项式g（x）,得到集合GF（2
12、）x/Dg（X）D，然后定义其上 的加法和乘法分别为模g（X）加法和模g（X）乘法，即得到有限域GF（2m）.然而，这样得到的有限域GF（2m）中，元素x未必是本原元，这将给后面的 （乘法）运算带来很多麻烦.因此，在不可约多项式g（X）的挑选上，我们最 好选择一个本原多项式.这其实就是Matlab中的做法.Matlab 中 GF，（2m）的元素：在 Matlab 中GF（2m）:=GF（2）D/Dp（D） ，其中 P（D）为一个 GF（2）上的 m 次本 原多项式.GF（2m） = am- 1Dm- 1+am- 2Dm- 2+ +aiD+a0，1 aiGF （2）,0W i Wm 1因此，每个
13、GF(2m)中的元素本质上是一个次数小于m的多项式，每个元素和多项式之间有“1-1”对应关系. 例如，取 m=3 和本原多项式P(D)二D3+D+1，则我们得到有限域GF(23)，其中的元素和多项式之间的对应关系如下：GF(23)GFD/p(D) 二进制00000110012D0103D+10114D21005D2+11016D2+D1107D2+D+1111GF(2) 上的多项式由系数组成的二进制所对应的(十进制)数字来表示. 例如， 多项式 p(D)=D3+D+1 的系数组成的二进制为 1011，因此，多项式 p(D) 表 示为数字 11.定义有限域数组在 Matlab 中，函数 gf 用
14、来定义一个有限域数组，函数申明如下：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 poly nomial = D八3+D八2+1 (13 decimal)Array elements =01234567如果不指定本原多
15、项式，则 Matlab 将使用默认本原多项式. 例如 gf(0:7,3)ans = GF(2八3) array. Primitive polynomial = D八3+D+1 (11 decimal)Array elements =01234567在这里例子中，Matlab使用了 3次本原多项式D3+D+1.如果不指定次数M和本原多项式PRIM_POLY,则生成二元域GF(2)中的元 素. gf(0:1)ans = GF(2) arrayArray elements =0 1生成的有限域中的数组可以参与运算（+、.： 等）注意：参与运算的操作数必须来自同一个有限域，用于生成有限域的本原多项式也必须相同！一个典型的例子是计算有限域的乘法表如下： GF8 = gf(0:7,3)GF8 = GF(2八3) array. PrimitiveArray elements =0123456
