matlab有限域上地运算

1、1 有限域基础知识1.1 有限域( Galois 域)的构造令p为一个素数.则对任意的一个正整数n,存在一个特征为p,元素个数为pn 的有限域 GF(pn).注：任意一个有限域，其元素的个数一定为 pn,其中p为一个素数(有限域 的特征), n 为一个正整数 .例 1(有限域 GF(p) 令 p 为一个素数,集合GF(p)=Zp=0,1,2,p,.在GF(p)上定义加法 和乘法 O分别为模p加法和模p乘法，即任意的 a,b GF(p),a b=(a+b)modp, aO b=(a?D)modp则GF(p),，O为一个有p个元素的有限域，其中零元素为 0,单位元为 1.令a为GF(p)中的一个非

2、零元素.由于gcd(a,p)=1,因此，存在整数b,c, 使得 ab+pc=1. 由此得到 a 的逆元为 a-1=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)?=ao+aix+a2X2+? +an-ixn-i |

3、 ai GF(p),0 简-1在GF(pn)上定义加法 和乘法 O分别为模g(x)加法和模g(x)乘法，即任意的 a(x),b(x) GF(pn)，a(x) b(x)=a(x)+b(x), a(x)O b(x)=(a(x)?)(x)modg(x)则GF(pn),O 为一个有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-

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

5、n)=1nEd|n d)qd=1 nd|n 如)qn/d其中 为Moebius函数，定义为Km)=? 1(-1) kO 如果 m=1 如果 m=p1p2? pk,其中 p1,p2,pk为互不相同的素数其它1.2 有限域的性质令 GF(q) 是一个含有 q 个元素的有限域， F?q=GF(q)?O 为有限域GF(q) 中所有非零元素构成的集合 . 则在乘法之下 F?q 是一个有限 循环群. 循环群 F?q 的一个生成元称为有限域 GF(q) 的一个本原元 .若a GF(q)为一个本原元，则GF(q)=0,1, a, a,a-2并且 a-1=1，即 a= a 定义： 设 GF(q) 是一个含有 q

6、 个元素的有限域， GF(p) 是 GF(q) 的一个含有p个元素的子域(P不一定为素数)，a GF(q).则GF(p)上以a为 根，首项系数为 1并且次数最低的多项式称为a在GF(p)上的极小多项 式(mi ni mal polyno mial of a over GF(p).特别地，若a GF(q)为GF(q)的一个本原元，则a在GF(p)上的极小 多项式称为 GF(p) 上的一个 本原多项式 (primitive polynomial for GF(q) over GF(p).定义注1对任意的a GF(q)， a在GF(p)上的极小多项式存在并且唯一， 并且a在GF(p)上的极小多项式为

7、 GF(p)上的一个不可约多项式.定义注2：设a GF(q)，则a和a在GF(p)上具有相同的极小多项式.更进一步，集合B(a)= a, a, a2, a3,a,中的元素具有相同的极小多项式.设q=pn，贝u an= a因此，集合B( a中 互不相同的元素的个数(记为 r)不超过n.可以证明，a为GF(q)的一个 本原元当且仅当 r=n.定理： 设 GF(q) 是一个含有 q 个元素的有限域， GF(p) 是 GF(q) 的一个 含有p个元素的子域.设a GF(q) ,r为满足 ar= a的最小正整数.则a 在 GF(p) 上的极小多项式 g(x) 是一个 r 次不可约多项式，并且B(a)=

8、a, a, 0p2, ，0pr- 1中的元素为 g(x) 在 GF(q) 上的所有不同的根，即g(x)=(x- 0(x- a)(x- a2)? (x- opr-1).注：r的计算方法如下：设 a在F?q中的阶为k.集合Z?k=m | 0 奇之-1,gcd(m,k)=1在模k乘法运算下是一个含有 k)个元素的有限群(其中为欧拉(Euler) 函数). 则 r 等于 pmodk 在 Z?k 中的阶.推论： 设 GF(q) 是一个含有 q 个元素的有限域， GF(p) 是 GF(q) 的一个含有p个元素的子域.设|GF(q)|=pn,即q=pn.设a GF(q)为GF(q)的一个本原元，则 a在GF

9、(p)上的极小多项式g(x)的次数为n,并且g(x)=(x- a(x- a)(x- a2)? (x- O(pn- 1).更进一步，a a, a?,an-1均为 GF(q)的本原元.注：设 GF(p) 是一个含有 p 个元素的有限域， n 是任意一个正整数， 则 GF(p) 上的 n 次本原多项式一定存在 . 更进一步， GF(p) 上的首项系数为 1 的 n 次本原多项式的个数为Kpn-1)n,其中为欧拉函数.例3考虑二元域GF(2)上的不可约多项式p( 0= a+ a+1，构造有限域GF(23)=GF(2) q/?p( a?=0,1, a a+1, a, a+1, a+ a, a+ a+1.

10、容易验证， a a, a, a, a, a 都是 GF(23)的本原元.GF(2)上的首项系数为 1 的 3 次本原多项式有两个，分别为(i) a, a2, a4 在 GF(2) 上的极小多项式g(x)=(x+a)(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 个元素的子域

11、， 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/?o(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)

12、 的本原元 .2 Matlab 中的有限域计算函数Matlab 中自带的有限域的计算是在 GF(2m) 上进行的，即在二元域 GF(2)的扩域中进行计算，其中iwmw 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) 的挑选上， 我们最好 选择一个

13、本原多项式 . 这其实就是 Matlab 中的做法 .Matlab 中 GF(2m) 的元素： 在 Matlab 中 GF(2m):=GF(2)D/?p(D)?， 其中 p(D) 为一个 GF(2) 上的 m 次本原多项式 .GF(2m)= am-1 Dm- i+am- 2Dm-2+? +ai D+ao, | ai GF,0 im- 1因此，每个 GF(2m) 中的元素本质上是一个次数小于 m 的多项式，每个元素 和多项式之间有“1-1”对应关系 . 例如，取 m=3 和本原多项式p(D)=D3+D+1，贝賊们得到有限域 GF(23)，其中的元素和多项式之间的对应关系如下：GF(23)GF(2

14、)D/?p(D)?二进制00000110012 D0103 D+10114 D21005 D2+11016 D2+D1107 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_POL；Y M 是一

15、个 1 至 16 之间的整数；数组 X 中的元素为 0 至2M- 1 之间的数 .例如，生成有限域 GF(23) 中的所有元素，并令本原多项式为 p(D)=D3+D2+1. GF8 = gf(0:7,3,13)GF8 = GF(2A3) array. Primitive pol yn omial = DA3+DA2+1 (13 decimal)Array elements =0 1 2 3 4 5 6 7如果不指定本原多项式，则 Matlab 将使用默认本原多项式 . 例如 gf(0:7,3)ans = GF(2A3) array. Primitive polynomial = DA3+D+1

16、 (11 decimal)Array elements =0 1 2 3 4 5 6 7在这里例子中， Matlab 使用了 3 次本原多项式 D3+D+1. 如果不指定次数M和本原多项式PRIM_POL，则生成二元域GF(2)中的元 素. gf(0:1)ans = GF(2) array.Array elements =0 1生成的有限域中的数组可以参与运算(+、人、等).注意：参与运算的操 作数必须来自同一个有限域，用于生成有限域的本原多项式也必须相同！一个典型的例子是计算有限域的乘法表如下： GF8 = gf(0:7,3)GF8 = GF(2A3) array. Primitive po

17、l yn omial = DA3+D+1 (11 decimal)Array elements = GF8*GF8 ans = GF(2A3) array. Primitive polynomial = DA3+D+1 (11 decimal)Array elements =0 1 2 3 4 5 6 70 2 4 6 3 1 7 50 3 6 5 7 4 1 20 4 3 70 5 1 40 6 7 10 7 5 26 2 5 12 7 3 65 3 2 41 6 4 3 GF8 = gf(0:7,3,13)GF8 = GF(2A3) array. Primitive pol yn omia

18、l = DA3+DA2+1 (13 decimal)Array elements = GF8*GF8Warning: Lookup tables not defined for this order 2A3 and primitive polynomial 13. Arithmetic still works correctly but multiplication, exponentiation, and inversion of elements is faster with lookup tables. Use gftable to create and save the lookup

19、tables. In gf.gettables at 35In gf.mtimes at 20 ans = GF(2A3) array. Primitive pol yn omial = DA3+DA2+1 (13 decimal)Array elements =0 00000000 12345670 2465713在这里我们用两个不同的本原多项式构造有限域GF(23)，得到两不同的乘法表.注 1：当我们计算 GF(2)D/?D3+D2+1? 的乘法表时， Matlab 给产生一个警告 “Warning: Lookup tables not defined for this order 2A3 and primitive polynomial 13. ” 从警告中我们可以看出， Matlab 中有限域的乘法是通过查表 来完成的，这样可以显著地提高计算的速度 . 我们可以通过命令 gftable 来创 建并保存查找表格 .注 2：用本原多项式 D3+D+1 和 D3+D2+1 生成两个不同的元素个数为 8 的有限域，然而这两