有限域 信安数学

巫玲[e-mail]有限域GaloisField7.1域的扩张域整环无零因子环含幺环可交换环环Abel群群半群AB表示满足A则满足B除环7.1域的扩张定义7-1非空集合F，若F中定义了加和乘两种运算，且满足：1)F关于加法构成阿贝尔群，加法恒等元记为02)F中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为13)加法和乘法之间满足分配律则F与这两种运算构成域每一个非零元都是可逆元的有单位元的交换环如实数域\复数域\有理数域7.1域的扩张当域元素个数有限时，称为有限域或伽罗瓦galois域,记为GF并把元素的个数称为F的阶，记为GF(n),否则称为无限域最常见:GF(2)两个元素个数相同的有限域一定同构7.1域的扩张如：1、全体整数2、全体偶数3、全体实数4、全体复数5、全体有理数设q为素数，则整数全体关于模q的剩余类1,,1,0q在模q的运算下(模q加和乘)构成q阶有限域GF(q)构成环，不构成域构成域构成域构成域构成环，不构成域无限域6、7.1域的扩张子域定义7-2记为F≤A7.1域的扩张定义7-3设F是域，X是F一个子集，那么F中包含X所有子域的交，称为X所生成的子域。所有子域的交:最小子域素域素域也称为极小域任何域都包含一个素域7.1域的扩张这两个例子实际上已刻划了所有的素域。7.1域的扩张有限扩张设F是K的扩域，视F是K上的向量空间，且维数为n，则称F是E上的有限扩张，记为[F:K]=n。例：视C为R上向量空间，基{1，i}，维数为2,称C为R的二维扩张。[F:K]=[F:E][E:K]无限扩张[F:K]=∞7.1域的扩张扩域的过程反过来，就得到素域的概念，即不会是任何域的扩域的域定义7-3域F上子域K，可以并入F子集X扩张，称为X在K上生成的子域，表示为K(X)扩域过程中最小的一步，是得到所谓单扩张，即并入一个元素而生成之扩域。例设F=R,K=Q,S={√2}，则K(S)=Q(√2)={a+b√2|a,b∈Q}复数域上的子域R，子集X={i},则R(X)=C7.2有限域的基本性质有限域的加法特性：特征有理数域、实数域和复数域中，任意多个1相加都不等于0而有限域中，因为元素个数有限，若干个1相加中不可能没有相同的元素设i*1=j*1,1≤ij,则(i-j)*1=0定义：设F为域，1为乘法单位元素，如果对任意正整数m，都有m*1≠0,则称F的特征是0，否则若适合条件的最小正整数p，则成F的特征为p，记为charF。7.2有限域的基本性质有限域F的特征=F的素域的阶分析：charF=p,则p*1=0,F的素域K中必包含{0,1}，因此必包含n*1，因此1≤素域K的加群，所以p≤|F|,因为F最小子域，|F|=pcharF=p,p一定素数7.2有限域的基本性质7.2有限域的基本性质有限域的加法特性：特征若F是一个域，则F的特征要么是0要么是素数p若F是特征为p的有限域，则对任意a,b∈F都有（a+b)p=ap+bp7.2有限域的基本性质7.2有限域的基本性质7.2有限域的基本性质有限域的乘法特性：乘法群都是循环群有限域GF中的费马定理：或者说都是方程的根或者说有限域GF(q)乘法群的生成元（即阶为q-1的元素）为GF(q)的本原元联系：原根乘法的阶；加法的阶被称为周期aanp0xxnpFapaxxxn)(7.5有限域的构造域上的多项式如同环上的多项式，只是系数来源于域最重要的的是GF(p)和GF(pn),p素如f(x)=x6+x4+x+1,g(x)=x4+x+1为GF(2)上的多项式,则，用g(x)去除f(x)商式为q(x)=x2+1,余式r(x)=x3+x2用域上n次多项式去除F(x)中的所有多项式，所得余数的次数一定小于n，如果域F含有q个元素，则余式共有qn个不同形式，这样就可以将F(x)中所有元素划为qn个剩余式如f(x)=x3+1为GF(2)上的多项式，用他去除GF(2)上所有多项式，得到余式可以将GF(2)上的多项式划分为8个剩余类{0}，{1},{x},{x+1},{x2},{x2+1},{x2+x},{x2+x+1}7.5有限域的构造7.5有限域的构造这些剩余形成的多项式代数结构是域吗？关键：逆元如f(x)=x3+1时，{x+1}有逆元吗？若要构成域，则模必须为既约多项式若f(x)不是即约，则f(x)=g(x)h(x)，g(x)和h(x)的次数小于f(x)，则g(x)和h(x)是剩余类的一个代表元，所以属于这个新的代数结构，但它们无逆元。7.5有限域的构造生成域：设p(x)为域F上一个n次既约多项式，记F[x]p(x)为模p(x)全体剩余式的集合，集合上的运算为多项式按模加和按模乘,则F[x]p(x)构成域，如果F包含q个元素，则F[x]p(x)是一个包含qn个元素的有限域GF(qn)，F是GF(qn)的子域GF(qn)是F的扩域，或称是由p(x)扩成的域选取p(x)的不同，取模运算效率不同，一般p(x)项数越少效率越高，所以一般p(x)为3项式或5项式，因为偶数项式都不是既约的。项数确定，除最高次数（已确定）其余次数从高向低尽量小7.5有限域的构造例：由GF(2)上的既约多项式p(x)=x4+x+1扩成GF(24)4位向量形式多项式形式生成元幂形式指数形式000000-∞00011a000010xa110100x2a221000x3a330011x+1a440110x2+xa551100x3+x2a667.5有限域的构造4位向量形式多项式形式生成元幂形式指数形式1011x3+x+1a770101x2+1a881010x3+xa990100x2a10100111x2+x+1a11111110x3+x2+xa12121111x3+x2+x+1a13131101x3+x2+1a14141001x3+1a15157.5有限域的构造7.5有限域的构造多项式的周期设f(x)是GF(p)上的多项式，且f(0)≠0,使f(x)除得尽xt-1的最小t称为f(x)的周期，记为P(f)=tf(0)≠0必要，否则，f(x)必包含x的因式，f(x)必不能整除xt-1f(x)互素的全体余式加上元素0构成有限域，记为[GF(p)f(x)]*注意，此时没有要求f(x)既约t其实就是元素x在域[GF(p)f(x)]*中的阶若既约多项式的周期等于pm-1，则为本原多项式7.6有限域应用代表性应用：编码理论开关理论纠错码AES：p(x)=x8+x4+x3+x+17.6有限域应用AES1997年美国政府向世界公开征集，2000年称为美国国家标准利用p(x)=x8+x4+x3+x+1扩成有限域GF(28)，8次不可约多项式一个字节就可视为一个多项式，成为GF(28)中的一个元素7.6有限域应用AESAES的主要环节字节代换：使用一个s盒S盒的构造：x行y列初始值xy，16进制下的，然后每个求出有限域中的逆，在进行矩阵变换行移位：一个简单的置换列混淆：相互加、乘后形成新值轮密钥加：按位xor多轮，每个阶段均可逆7.6有限域应用循环冗余码CRC检错码与纠错码CRC的工作过程可以简单的概括为四步。添0：在需要发送的数据后面添加0，0的个数比生成多项式的位数少1个做除法：①除法时并非减法，而是异或②我们关心的是最后的余数R而不是商Q，因此有时直接将余数称为CRC余数填充：将余数R填入待发数据中补充的0的位置，得到发送方的真正发送的数据S。接收方检查：接收方将收到的数据S，执行与发送方同样的除法，如果得到的余数为0，则验证通过，如果不为0则传输出错。7.6有限域应用7.6有限域应用CRC的数学原理有限域中，将一般将位串看作系数为0或1的多项式，所以CRC也叫做多项式编码如10011有6位，表示多项式为G(x)=x4+x+1，G(x)每项对应的系数分别为1、0、0、1、1在M后面添加r位0，就相当于xr·M(x)。有限域中，加法、减法是模2运算，因此，在上面第二步骤除法的减法运算为异或。7.6有限域应用CRC的数学原理若待发送数据为M(x)，生成元为G(x)，G(x)的最高次数为r，R(x)为余数，实际发送的数据为S(x)：（1）添零：计算xr·M(x)（2）做除法：xr·M(x)(modG(x))=R(x)（3）余数填充：S(x)=xr·M(x)+R(x)（4）接收方检查：S(x)(modG(x))=(xr·M(x)+R(x))(modG(x))=R(x)+R(x)=07.6有限域应用CRC的硬件实现无零因子环环域阿贝尔群群半群整环交换环含幺环