本文主要是介绍网络空间安全数学基础·多项式环与有限域,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
5.1 多项式环(掌握)
5.2 多项式剩余类环(理解)
5.3 有限域(熟练)
5.1 多项式环
定义:设F是一个域,称是F上的一元多项式.
首项:如果an≠0,则称 anx^n 为f(x)的首项
次数:n是多项式f(x)的次数,记为deg(f(x)) = n
首一多项式:如果an = 1,则称f(x)为首一多项式
零次多项式:若f(x) = a0≠0,则约定deg(f(x)) = 0
F上的全体一元多项式的集合用F[x]表示
零多项式:当ai全为0时,f(x)=0,称为零多项式
多项式环运算
对于F[x]中的任意两个多项式
定义F[x]上的加法和乘法分别如下:
其中
例:域GF(2)上的两个多项式:
则
定理:若F是域,F[x]是具有单位元的整环.
多项式整除
定义:f(x),g(x)∈F[x],f(x)≠0.如果存在q(x)∈F[x],使 g(x) = q(x) f(x),则称f(x)整除g(x),记为 f(x)|g(x), f(x)称为g(x)的因式。如果 f^k(x)|g(x),但f^(k+1)(x)不能整除g(x),则称f(x)是g(x)的k重因式.
多项式整除的性质
多项式整除具有下列性质:其中c≠0∈F.
1) f(x)|0;
2) c|f(x) (因为f(x) = c(c^(-1)f(x)));
3) 如果 f(x)|g(x),则 cf(x)|g(x);
4) 如果 f(x)|g(x),g(x)|h(x),则 f(x)|h(x);
5) 如果 f(x)|g(x),f(x)|h(x),则对任意u(x),v(x)∈F[x],有 f(x)|u(x)g(x)+ v(x)h(x);
6) 如果 f(x)|g(x),g(x)|f(x),则f(x) = cg(x).
例:Z[x]中有
F[x]的带余除法:对f(x),g(x)∈F[x],f(x)≠0,存在q(x),r(x)∈F[x],使例:GF(2)[x]上多项式
则
最大公因式
定义:f(x), g(x)∈F[x]为不全为零多项式.设d(x)≠0∈F[x],如果 d(x)|f(x),d(x)|g(x),则称 d(x) 是 f(x),g(x) 的一个公因式。
若d(x)是首一多项式,而且 f(x), g(x) 的任何公因式都整除d(x),则称d(x)是 f(x), g(x)的最大公因式,记为(f(x),g(x))。
如果(f(x),g(x))=1,则称f(x),g(x)互素。
定理(欧几里德算法):对于多项式f(x),g(x),其中deg(f(x))≤deg(g(x))。反复进行欧几里德除法:
于是
例:求GF(2)[x]上多项式:
解:由欧几里德算法得:
故
定理5-3 对于多项式f(x),g(x),其中deg(f(x))≤deg(g(x)),而且h(x) = (f(x),g(x)).则存在a(x),b(x)使 a(x)f(x)+b(x)g(x)=h(x), 其中deg(a(x))≤deg(g(x)), deg(b(x))≤deg(g(x))
特别地,当f(x),g(x)互素时,存在a(x),b(x)使 a(x)f(x)+b(x)g(x)=1
多项式的分解
定义:设p(x)∈F[x]为首一多项式,且deg(p(x))≥1,如果p(x)在F[x]内的因式仅有零次多项式及cp(x) (c≠0∈F),则称p(x)是F[x]内的一个不可约多项式,否则称为可约多项式。
例:Z[x]上多项式不可约.GF(2)[x]上多项式可约:
GF(2)[x]五次以内的不可约多项式:
定理(分解唯一定理):F[x]上的多项式可分解为,是两两不同的首一不可约多项式.除的排列次序外,上述分解是唯一的。
定理:多项式f(x)∈F[x]含有因式 x∈a (a∈F),当且仅当f(a)=0.
例:分解GF(2)[x]上多项式:
由于f(1)=0,所以f(x)有因式x+1.
运用多项式除法得
通过试探得
故
实际上在GF(2)[x]上有
因此也可这样分解:
5.2 多项式剩余类环
定义:设f(x)∈F[x]是首一多项式.对于a(x),b(x)∈F[x],如果f(x)除a(x),b(x)得相同的余式,即
则称a(x)和b(x)关于模f(x)同余,记为
由定义可见,a(x)≡b(x) mod f(x)当且仅当 a(x)-b(x)=g(x)f(x),g(x)∈F[x],或 f(x)|a(x)-b(x).
令是F[x]中关于模f(x)与a(x)同余的全体多项式集合。
与整数情形相似,我们可以把F[x]划分成剩余类,这些剩余类的集合记为F[x] mod f(x)。
例:GF(2)[x]mod=
定义多项式剩余类的加法和乘法分别如下:
定理:设f(x)∈F[x]是一个首一多项式,且deg(f(x))>0,则F[x]mod f(x)构成具有单位元的交换环,称为多项式剩余类环。多项式剩余类环可能存在零因子,例如GF(2)[x]mod中就有零因子,因为。
GF(2)[x]mod 存在零因子,是因为是可约多项式.在不可约多项式情形,我们有下面的定理.
定理:如果f(x)是F上的首一不可约多项式,则F[x]mod f(x)构成域.
定理:域F上的多项式F[x]是主理想整环.
5.3 有限域
定义:有限个元素构成的域称为有限域或Galois(伽罗瓦)域.域中元素的个数称为有限域的阶.
我们曾指出,当p是素数时,模p剩余类集合构成p阶有限域GF(p) 并指出这也是最简单的一种有限域. q阶有限域的所有非零元构成q-1阶乘法交换群.
我们将域中非零元素关于乘法群的阶定义为域中非零元素的阶.
由关于群的讨论我们有,n阶有限群的任意元素a均满足a^n = 1.所 以a^(q-1)=1。
如果把零元也考虑进来,则q阶有限域的所有元素满足 aq=a,或 aq-a = 0
那么q阶有限域可以看成是方程 x^q-x=0的根的集合。
定义:q阶有限域中阶为q-1的元素称为本原域元素,简称本原元。
本原元的意义是很明显的。如果q阶有限域中存在本原元a,则所有非零元构成一个由a生成的q-1阶循环群.那么q阶有限域就可以表示为
定理:有限域中一定含有本原元。实际上,当q>2时,q阶有限域的本原元多于一个。如果a是一个本原元,对于1≤n≤q-1,只要 (n,q-1) = 1, 由群中的结论,则a^n的阶也是q-1,即a^n也是本原元。我们指出,q阶有限域中共有φ(q-1)个本原元(φ是欧拉函数)。
假设a是域中的一个非零元,使的最小正整数n是a的加法阶.如果不存在这样的n,则加法阶是无限大.
例:GF(7)非零元素的加法阶:
定理:在一个无零因子环R里所有非零元的加法阶都相同。当加法阶有限时,它是一个素数。
定义:域中非零元的加法阶称为域的特征,当加法阶为无限大时,称特征为0。
推论:域的特征或者是0,或者是一个素数.有限域的特征是素数。
例:GF(p)的特征为p,因为
GF(p)的特征等于| GF(p)|.
定理:有限域的阶必为其特征之幂。一般有限域记为GF(p^m),其中p是域的特征,m是正整数。由于特征总是素数,则有限域的阶总为素数的幂。
定理:如果f(x)是GF(p)上的m次首一不可约多项式,则GF(p)[x] mod f(x)构成pm阶有限域GF(p^m)。
例:GF(2)[x] mod构成有限域GF(2^3)。
GF(2^3)的8个元素:
为了表示简单,可以去掉上面的横线,但其剩余类的含义没有改变:
这篇关于网络空间安全数学基础·多项式环与有限域的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!