数据加密技术（代数系统有限域）课件.ppt

《数据加密技术（代数系统有限域）课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.1有限域概念定义27：只含有有限个元素的域称为有限域，称为伽罗华（Galois）域，含有q个元素的有限域常记为Fq或GF(q)。（学习代数系统的目的）如就是一个有限域，而且是最小的有限域。如整数模3剩余类环是含有3个元素的有限域，等等。有限域的元素个数称为有限域的阶，如F2的阶为2，Z3的阶为3.7有限域定理30：设F是有限域，其阶为q,则q=pm,p为某一素数，m为一正整数。关于有限域的存在性，有定理31：对每一个素数p，任一正整数m，必存在阶为pm的有限域，而且在同构意义下，这样的域是唯一的。通常把阶为q=pm的有限域记为Fpm或GF(p

2、m)。定理32：对任意的a∈GF(pm)，apm=a(非零元构成乘法群)定义28：有限域F所包含的最小子域称为F的素域，F的素域的阶称为F的特征。设p是素数，如果有限域F的阶为q=pm，则F的素域的阶为p，F是其素域的扩张。例令F={0,1,2,3},在F上定义加法和乘法如下：则F是含4个元素的域，其素域是F2，特征是2.+012301230123103223013210*012301230000012302310312定理32：设p是素数，有限域F的阶为q=pm，m为一正整数，则F的子域的阶一定是pn,其中n是m的一个正因子，而且对m的每一个正因子n，F必有一个阶为pn的子域

3、。定理33：设p是素数，m为一正整数,n是m的一个正因子，则有限域GF(pm)的一个元素a∈GF(pn)当且仅当apn=a。从而，对任意的自然数，当a∈GF(pn)，a=apn=(apn)pn=…=apkn定义29：有限域非零元a的阶定义为a在F的非零元构成的乘法群中的阶。若有限域的阶为q=pm，则其乘法群F*的阶为q-1=pm–1。因此有如下定理：定理34：有限域GF(q)的任意非零元a的阶一定是q-1的因子。定义30：设F是有限域，a∈F且为非零元，称使na=0的最小正整数n为元素a的周期。如在F2中，1的周期=？在F4中，1，2，3的周期=？注意：在有限域中，元素a的周期

4、是对“加法”，阶为对“乘法”定理35：有限域F的所有非零元都有相同的周期，而且等于F的特征。证明：设F的特征是p,令F1={i1,i∈N}，则i1（i个1相加，所以i1是F的元素）是F1是F的子集，从而F1是有限集。因此，由于自然数的无穷性，i1必有重复，故必有自然数m和n,使m1=n1。不妨假设m>n，于是有(m-n)1=0∈F1。设k=min{i∈N,i1=0},则F1={11,21,31,…,k1}容易验证F1是F的子域，其中m1的加法逆元是(k-m)1，(m11).(m21)=1当且仅当m1m2=1(modk)。明显地，F1是F的最小子域，即F1是F的素域。因此F1的阶

5、就是F的特征，即k=p。设a是F的任意非零元，其周期为n,则pa=pa.1=a.p1=0,说明a的周期n<=p(周期的定义)。令p=qn+r,0<=r

6、1环上的多项式定义30：R为交换环，x是变元,R[x]={f(x)=∑aixi

7、n∈Z,ai∈R}则称（R[x],+,*)为R上的多项式环。定义31：若f(x),g(x)∈R[x],g(x)≠0,存在q(x)∈R[x],q(x)≠0使得f(x)=g(x)*q(x)，则称f(x)可约，否则f(x)是R(x)的不可约多项式，也可叫既约多项式，素式。q[x]使用类似整数的带余除法来生成，最大公约、最小公倍、同余、互质、线性表达、唯一分解定理等思想一致所以两个多项式可形成相除后有商有余的关系素式地位如同素数如果f(x)可约，则可以分解成两个系数更小的多项式的乘积8多项式理论2x+5)3

8、x5+5x3+2x2+1+4x2x3+6x23x2+0x+5x33x4+4x3x3+2x2多项式长除法：f(x)=3x5+5x3+2x2+1∈Z7[x],g(x)=2x+5∈Z7[x]0x4+0x+(1)补齐缺失项5x43x5+4x43x4+5x3(2)模7除，消去本次最高次项+5x3x2+4x3x+1结论：商：5x4+5x3+4x2+5x余：3x+1x3+x2+1)x4+x2+x+1+1+1x3+x2+1f(x)=x4+x2+x+1∈Z2[x],g(x)=x3+x2+1∈Z2[x]0x3+