资源描述：
《matlab有限域上的运算.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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−1}.在GF(p)上定义加法⊕和乘法⊙分别为模p加法和模p乘法，即任意的a,b∈GF(p)，a⊕b=(a+b)modp, a⊙b=(a⋅b)modp则为一个有p个元素的有限域
2、，其中零元素为0，单位元为1.令a为GF(p)中的一个非零元素.由于gcd(a,p)=1，因此，存在整数b,c，使得ab+pc=1.由此得到a的逆元为a−1=bmodp.域GF(p)称为一个素域(primefield)..专业专注.......例注1：给定a和p，例1中的等式ab+pc=1可以通过扩展的欧几里得除法得到，从而求得GF(p)中任意非零元素的逆元.例2（有限域GF(pn)）从GF(p)出发，对任意正整数n，n≥2，我们可以构造元素元素个数为pn的有限域GF(pn)如下：令g(x)为一个GF(p)上次数为n的不可约多
3、项式，集合GF(pn)=GF(p)[x]/⟨g(x)⟩={a0+a1x+a2x2+⋯+an−1xn−1
4、 ai∈GF(p),0≤i≤n−1}在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(
5、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).域GF(pn)称为GF(p)的（n次）扩域(extensionfield)，而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
6、(q)是一个含有q个元素的有限域.对任意正整数n,GF(q)上的n次不可约多项式一定存在.更进一步，GF(q)上首项系数为1的n次不可约多项式的个数为Nq(n)=1n∑d
7、nμ(nd)qd=1n∑d
8、nμ(d)qn/d其中μ为Moebius函数，定义为μ(m)=⎧⎩⎨1(−1)k0如果m=1如果m=p1p2⋯pk,其中p1,p2,…,pk为互不相同的素数其它1.2有限域的性质令GF(q)是一个含有q个元素的有限域，F∗q=GF(q)∖{0}为有限域GF(q)中所有非零元素构成的集合.则在乘法之下F∗q是一个有限循环群.循环群F
9、∗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)上的极小多项式(minimalpolynomialofαoverGF(p)).特别地，若α∈GF(q)为GF(q)的一个本原元，则α在GF(p)上
10、的极小多项式称为GF(p)上的一个本原多项式(primitivepolynomialforGF(q)overGF(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.可以证明，
11、α为GF(q)的一个本原元当且仅当r=n.定理：设GF(q)是一个含有q个元素的有限域，GF(p)是GF(q)的一个含有p个元素的子域.设α∈GF(q)，r为满足αpr=α的最小正整数.则α在GF(p)上的极小多项式g(x)是一个r次不可约多项式，并且.专业专注.......
