国家重点实验室 既约多项式 °每一个首一多项式必可分解为首一既约多项式之积,并且 当不考虑因式的顺序时,该分解是唯一的 f(x)=D1(x)n(x)2…p(x) 其中,p(x)为首一既约多项式,1为正整数 d次多项式f(x)不可能有多于a个的一次因式,至多有d个根 α为之根的充要条件是(x-)(x) 若p(x)是f(x)的k重既约因式,则p(x)必是f(x)的k1重既约 因式
既约多项式 每一个首一多项式必可分解为首一既约多项式之积，并且 当不考虑因式的顺序时，该分解是唯一的 其中，pi (x)为首一既约多项式， 为正整数 d次多项式f(x)不可能有多于d个的一次因式, 至多有d个根 α为之根的充要条件是 (x-α)| f(x) 若p(x)是f(x)的k重既约因式，则p(x)必是f’(x)的k-1重既约 因式 1 2 1 2 ( ) ( ) ( ) ( ) i i f x p x p x p x = i
国家重点实验室 GCD&CM oGcD((x),g(x):同时除尽x)和g(x)的次数最高的首 多项式 LcM[(x),g(x)]:同时被f(x)和g(x)除尽的次数最低的首 多项式 f(x)g(x)=(f(x),9(x)[(x),g(x) Euclidean算法 (f(x),9(x)=A(x)f(x)+B(x)g(x) f(x)=x+x3+x+x2+x+1=(x3+x2+x+x2+x+1)+(x2+1) g(x)=x2+x+x+1=(x+1)x2+1) (f(x.9(x)=x2+1=l/(x)+(x+x3+x)x+x3+x+1) A(xf(x)+b(glx
GCD&LCM GCD (f(x), g(x))：同时除尽f(x)和g(x)的次数最高的首一 多项式 LCM [f(x), g(x)]：同时被f(x)和g(x)除尽的次数最低的首 一多项式 f(x) g(x)= (f(x), g(x)) [f(x), g(x)] Euclidean算法 (f(x), g(x))=A(x) f(x)＋B(x) g(x) ( ) 9 8 7 2 5 3 4 3 3 4 3 3 3 5 3 4 3 ( ) 1 ( )( 1) ( 1) ( ) 1 ( 1)( 1) ( ), ( ) 1 1 ( ) ( )( 1) ( ) ( ) ( ) ( ) f x x x x x x x x x x x x x g x x x x x x f x g x x f x x x x x x x A x f x B x g x = + + + + + = + + + + + + + = + + + = + + = + = + + + + + + = +
国家重点实验室 多项式的加法和乘法 °设f(x)=fnx+fnxn1+,+1x+0f∈F g(x)gmm+ gm-1Xm-1+.+91X+gG; E Fp °多项式相等 >若m=n,且对所有千=g则fx)=g(x) 多项式加(若m>m) fx)+gx=fnXn+. tfm+Xm++(m +gmM+.+1+g)x+(fo+ 9o) °多项式乘 fx)gx)=hn+m Xntm+ hn+m1 Xntm-1+, h,+ho ∑1g1i=0. n≥m ∑fg,i=m+1…,m+n J=l-m
多项式的加法和乘法 设 f(x)=fnx n+ fn-1x n-1+…+ f1x+f0 g(x)=gmx m+ gm-1x m-1+…+ g1x+g0 多项式相等 ➢若m=n，且对所有i, fi=gi , 则f(x)=g(x) 多项式加（若n>m) f(x)+g(x)= fn x n+…+fm+1x m+1+ (fm + gm)x m+…+ (f1 + g1 )x+(f0+ g0 ) 多项式乘 f(x) g(x)=hn+m x n+m+ hn+m-1 x n+m-1+…+ h1x+h0 i Fp f gi Fp 0 0,1, , , 1, , i i i j j i i i i j j i m f g i m n m h f g i m m n − = − = − = = = + +
国家重点实验室 多项式剩余类环 结论 >按上述定义的加法和乘法运算,Fx]构成一个具有单 位元、无零因子的可换环 多项式剩余类环 >以一个F上的多项式x)=x+1x01+,…+千x+为模 的剩余类全体构成一个多项式剩余类环 >F]上任一多项式fx)的一切倍式集合x)组成一个理 想。以此理想把Fx]划分陪集,这些陪集全体就构成 了模fx)的剩余类环 剩余类之间的加法和乘法运算规则 a(x)+ alx t blx a().b()=ax).bx)
多项式剩余类环 结论 ➢按上述定义的加法和乘法运算，Fp [x]构成一个具有单 位元、无零因子的可换环 多项式剩余类环 ➢以一个Fp上的多项式f(x)=fnx n+ fn-1x n-1+…+ f1x+f0为模 的剩余类全体构成一个多项式剩余类环 ➢Fp [x]上任一多项式f(x)的一切倍式集合I f (x)组成一个理 想。以此理想把Fp [x]划分陪集，这些陪集全体就构成 了模f(x)的剩余类环 剩余类之间的加法和乘法运算规则 a(x) + b(x) = a(x) + b(x) a(x) • b(x) = a(x) • b(x)
国家重点实验室 Examples GF(2)上的多项式f(x)=x2+1的剩余类全体为: 0x2+1x(x2+1)(x+1)(x2+1) x +x+ 1x32+x2+x x: xx+x+1 x x3+x2+1 x+1:1+xx2+x x3+1 x +x 对所定义的加法和乘法运算,0.1,x.x+1构成剩余类 环 元素x+1没有乘法逆元 x+10=0:x+1=x+1:x+1x=x+x2=x+1 x+1x+1=1+x2=0
Examples GF(2)上的多项式 f(x)=x 2+1的剩余类全体为： 对所定义的加法和乘法运算， 构成剩余类 环 ➢元素 没有乘法逆元 0,1, x, x +1 2 2 2 2 3 3 2 2 3 3 2 2 3 0 : 0 1 ( 1) ( 1)( 1) 1 : 1 1 : 1 1 1:1+ + 1 x x x x x x x x x x x x x x x x x x x x x x x + + + + + + + + + + + + + + 3 2 x x + x +1 2 2 1 0 0; 1 1 1; 1 1 1 1 1 0 x x x x x x x x x x x + = + = + + = + = + + + = + =