第四章 多项式环与有限域.

Presentation on theme: "第四章 多项式环与有限域."— Presentation transcript:

1 第四章 多项式环与有限域

2 一、子环与理想 子环：若环中的子集S，关于R中的代数运算也构成环，则称S是R的子环，R是S的扩环
理想：S是交换环R的一个子环，若S中的元素由某几个元素及其所有可能的倍元构成，则S是一个理想 主理想：若理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为主理想。 剩余类环：设R是可换环，I为R的一个理想，则R模I构成一个可换环，称它为环R以理想I为模的剩余类环M。

3 二、多项式（一） 多项式 f(x)=fnxn+ fn-1xn-1+…+ f1x+f0
多项式次数 degf(x)：系数不为零的x的最高次数称为多项式f(x)的次数 首一多项式:最高次数的系数为1的多项式 既约多项式:设f(x)是次数大于零的多项式，若除常数和常数与本身的乘积以外，再不能被域Fp上的其他多项式整除，则称f(x)为域Fp上的既约多项式 多项式的因式分解问题、根的问题 最大公因式与最小公倍式 其中 i=0,1,…n，该多项式称为域Fp上的多项式

4 二、多项式（二） f(x)=fnxn+ fn-1xn-1+…+ f1x+f0 g(x)=gnxn+ gn-1xn-1+…+ g1x+g0
若对所有i, fi=gi, 则f(x)=g(x) 多项式加法 f(x)+g(x)=(fn + gn)xn+ (fn-1 + gn-1)xn-1+…+ (f1 + g1)x+(f0 + g0) 多项式乘法 f(x)g(x)=hn+mxn+m+hn+m-1xn+m-1+…+h1x+h0 结论：按上述定义的加法和乘法运算，Fp[x]构成一个具有单位 元、无零因子的可换环

5 三、多项式剩余类环 定义：以一个Fp上的多项式f(x)=fnxn+ fn-1xn-1+…+ f1x+f0为模的剩余类全体构成一个多项式剩余类环 Fp上的所有次数小于n-1的多项式构成n次多项式的剩余类全体 剩余类之间的加法和乘法运算规则

6 Examples 1、GF(2)上的多项式 f(x)=x2+1的剩余类全体为： 2、GF(2)上的多项式 f(x)=x2+x+1的剩余类全体为： 对所定义的加法和乘法运算，前者构成剩余类环，后者构成域 结论：若n次首一多项式f(x)在域Fp上既约，则f(x)的剩余类环构成 一个有pn个元素的有限域

7 两个结论 多项式环Fp[x]的一切理想均是主理想 多项式剩余类环Fp[x]/f(x)中的每一个理想都是主理想。

8 四、循环群 循环群的定义 循环群的构造及性质 循环群中元素级的性质

9 循环群的定义 定义：由一个单独元素的所有幂次所构成的群称为循环群，该元素为循环群的生成元 注：
1、幂次的含义与在群上所定义的运算有关。若定义加法运算，幂运算为连加运算；若定义乘法运算，则幂运算为连乘。 2、循环群的生成元不止一个。 3、凡是循环群必是可换群。

10 Examples: 模4剩余类全体关于加法运算构成循环群，生成元为1和3。 模5全体非零剩余类关于乘法构成循环群，生成元为2和3

11 循环群的构造及性质 有限循环群和无限循环群 若元素a的所有幂次均不相同(无限循环群) 循环群元素的级
存在整数 h和k，使得ak=ah，则有a生成的循环群中元素个数有限(有限循环群) 循环群元素的级 若ak=ah，则有ah-k=e，定义使an=e的最小正整数为有限循环群元素a的级。

12 有限循环群的几个特点 1、若元素a的级为n，则a0=e,a,a2,…an-1均互不相同 2、若a为n级元素，则a的一切幂次生成的元素都在群G(a)中 3、凡是循环群必是可换群 4、可换群G中的每一个元素a都能生成一个循环群。若a为有限级，则生成有限循环群， a的级即为循环群中元素的个数(循环群的阶)

13 有限循环群元素级的性质 性质 1、若a是n级元素，则am=e的充要条件是
2、若a是n级元素， b是m级元素，且(n,m)=1,则 (ab)的级为nm 3、若a是n级元素， 则ak的级为n/(k,n) 4、若a是dk级元素， 则ak为d级元素 5、n阶循环群中，每个元素的级是群阶数n的因子 个单位原根 6、n阶循环群中有

14 两个定义 单位原根：n阶循环群中，每一个n级元素称为n次原根 欧拉函数：0,1,2,…,n-1中与n互素的元素个数称为欧拉函数。

15 五、有限域的乘法结构 基本概念 分圆多项式，用于分解xn-1多项式

16 基本概念 域中非0元素所构成的乘法群之阶—该元素的级
若a为域GF(q)中的n级元素，a为n次单位原根；在GF(q)中，元素a的级为q-1，a为本原域元素。 在GF(q)中，每一个非0元素均满足xq-1=1，即都是方程xq-1-1=0的根；反之，xq-1-1=0的根必在GF(q)中。 由GF(q)中n级元素a生成的循环群G(a)，一定是方程xn-1=0的根。 GF(q)中必有本原域元素存在。 若a是GF(q)中的本原域元素，则

17 分圆多项式 在含有n次单位原根的任意域上，有因式分解：
以GF(q)中彼此不同的d级元素为全部根的首一多项式，称为d级分圆多项式，记为Q(d)(x)。 d级分圆多项式Q(d)(x)的次数为f(d)

18 六、有限域的加法结构 基本概念 最小多项式与本原多项式 互反多项式 多项式的周期

19 基本概念与性质 与乘法比较：a,a2,a3,…,am=1, m----级 域的特征：满足ne=0的最小正整数n；
元素a的周期：满足na=0的最小正整数n; 与乘法比较：a,a2,a3,…,am=1, m----级 域中一切非0元素的周期相同，=特征；且或为素数，或为无穷 以p为特征的域是GF(pm)，m=1,2,…,称GF(p)是GF(pm)的基域，GF(pm)为GF(p)的扩域 在特征为p的域中，恒有(x-a)p=xp-ap, a是域中任意元素 在p特征域中，任意元素a,b,恒有(a+b)p=ap+bp;(a-b)p=ap-bp 若k是p特征域的域整数，则对自然数n,满足 费尔马定理：对GF(pm)的任何元素x，恒有 p特征域中，元素为域整数的充要条件是：它是xp-x=0的根

20 最小多项式与本原多项式 共轭根系 方次数 最小多项式 本原多项式

21 共轭根系 若 ，则 必是GF(pm)中互不相同的元素，它们都是f(x)的m个 不同的根，这m个值称作方程f(x)的共轭根系
GF(p)上多项式f(x)的共轭根系： 中每一个互不相同。 定义：能满足pm=1(mod n)的最小正整数m, 称作p对 模n的方次数

22 最小多项式 系数取自GF(p)上，且以w为根的所有首一多项式中，必有一个次数最低的，称为w的最小多项式，记为m(x)
m(x)在域GF(p)上既约 若f(x)也是GF(p)域上的多项式，且f(w)=0，则m(x)|f(x)。 设w是p特征有限域GF(pm)中的n级元素，而m是p关于模n的方次数，则w的最小多项式m(x)是m次多项式，且

23 最小多项式 定义元素w的最小多项式的次数m为w元素的次数，称w为m次域元素 共轭根系内的每个元素的最小多项式相同
系数取自GF(p)上的以GF(pm)中本原域元素为根的最小多项式，称为本原多项式。 若w是p特征有限域F上的m次域元素，则GF(p)上的次数小于m的、w的多项式全体Fw，构成域F上的pm阶子域

24 互反多项式 多项式的周期 f(x)|(xl-1)的最小整数l

25 有限域GF(pm)的构造 寻找一个GF(p)上的m次本原多项式，设a是该多项式的根，则集合 构成有限域GF(pm)(幂表示) 多项式表示
向量表示

26 由p(x)=1+x+x4生成的GF(24)有限域
幂表示 多项式表示 4维向量表示 0000 1 1000 a 0100 a2 0010 a3 0001 a4 1 + a 1100 a5 a + a2 0110 a6 a2 + a3 0011 a7 1 + a a3 1101 a8 a2 1010 a9 a a3 0101 a10 1 + a + a2 1110 a11 a + a2 + a3 0111 a12 1 + a + a2 + a3 1111 a13 a2 + a3 1011 a14 a3 1001