《代数学基础有限域.ppt》由会员分享，可在线阅读，更多相关《代数学基础有限域.ppt（23页珍藏版）》请在三一办公上搜索。
1、有限域的表示,有限域的表示,1.多项式表示2.N比特的字符表示3.向量空间中的基表示4.本原元表示,1.多项式表示,二元域F2；多项式f(x)=x8+x4+x3+x+1在F2上不可约；F2x/f(x)上模f(x)的所有多项式集合构成一个含有28个元素的域.,域中元素是F2上所有次数小于8的多项式，可以写成下面的形式：将每个元素都可以简写为一个长度为8的比特串：即一个字节。,在16进制编码中，用一个字符表示一个长度为4的比特串，那么一个字节可以表示成两个16进制的字符。也就是说，F28上的任一元素都可以看作区间00,FF上的一个字节。例如：字节01010111(57)对应的元素为：,2.N比特二
2、元域,对于已知的8次不可约多项式f，我们可以将域F2x/f(x)看作由8个比特排列所构成的28=256个元素构成的域。一般地，我们可以将域F2x/f(x)看作由deg(f)个比特排列所构成的含有2deg(f)个元素构成的域，将这个域称为N比特二元域。N比特二元域在编码学和密码学中都有很多应用，AES就是在8比特二元域上实现的。,在N比特二元域中，加法运算即为比特之间的模2加法，与定义多项式f无关，但是乘法运算与f有关.,域中不可约多项式的根,令F是一个有限域，f(x)是F上的一个n次不可约多项式；类似于数域的扩张，可以将域F扩张，使得f(x)在扩张后的域上有n个根.分别记为 f(x)在F上不可
3、约，这n个根都不在F中.,定理,3.向量空间中基表示,定义 多项式基,向量空间,由线性代数的知识，n个线性无关的元素可以张成一个n维向量空间.,定理,例 域F28,这两个域都含有28个元素，同构.类似地，后一种表示法也可以用一个字节来表示.,中的乘法f(x)=x8+x4+x3+x+1,5.本原元表示,有限域的乘法群是一个循环群.其生成元称为本原元(或者本原根).,有限域的乘法群,定理:有限域Fq的乘法群F*q是一个循环群.,引理1:F*q是至多只有一个d阶循环子群,其中d|(q-1).,引理2:d|n(d)=n.,我们需要如下两条引理:,证明:如果 F*q,那么#=d|(q-1).,引理1:F
4、*q是至多只有一个d阶循环子群,其中d|(q-1).,同时的所有元都是方程xd-1=0的根.,F*q的所有元都是是方程xq-1-1=0的根.,由于Fq x是唯一分解环,得证.,引理2:d|n(d)=n.,证明:,S=1,2,n,Sd=x|1x n,gcd(x,n)=d,Sd,d|n,构成S的一个完全划分,#Sd=#x|1x n,gcd(x,n)=d=#x/d|1x/d n/d,gcd(x/d,n/d)=1=#y|1y n/d,gcd(y,n/d)=1=(n/d),定理:F*q是一个循环群.,证明:假设g是F*q的d阶元,那么d|(q-1).,中的d阶元有(d)个.ord(gk)=d/(d,k),F*q中的d阶元有(d)个.d阶循环群存在即唯一,q-1d|(q-1)(d).必须取等号,定义:F*q的生成元称为Fq的本原元.,F*q中的(q-1)阶元有(q-1)个.,多项式的表示vs 本原元表示,多项式表示-加法容易,乘法复杂本原元表示-加法复杂,乘法容易,本原元表示,取F2的不可约多项式 f(x)=x4+x+1 是 f(x)的根,即 f()=0,f()=4+1=04=+1.是一个本原元,
