国家重点实验室 多项式 。多项式 f(x)=fx+fx-1+...+fix+fo 其中f∈Fp=0,1,.,n,该多项式称为域F。上的多项 。多项式次数degf(x) >系数不为零的x的最高次数称为多项式x)的次数 。首一多项式 >最高次数的系数为1的多项式 。既约多项式 >设x)是次数大于零的多项式，若除常数和常数与本 身的乘积以外，再不能被域F。上的其他多项式整除， 则称f孔x)为域F。上的既约多项式 >x)是否既约与讨论的域有关：x)=x2+1在实数域上 既约，但在复数域上fx)=(x+x-)
多项式 多项式 f(x)=fnx n+ fn-1x n-1+…+ f1x+f0 其中 i=0,1,…,n，该多项式称为域Fp上的多项 式 多项式次数 degf(x) ➢系数不为零的x的最高次数称为多项式f(x)的次数 首一多项式 ➢最高次数的系数为1的多项式 既约多项式 ➢设f(x)是次数大于零的多项式，若除常数和常数与本 身的乘积以外，再不能被域Fp上的其他多项式整除， 则称f(x)为域Fp上的既约多项式 ➢f(x)是否既约与讨论的域有关：f(x)=x 2+1在实数域上 既约，但在复数域上f(x)=(x+i)(x-i) i Fp f
国家重点实验室 既约多项式 ·每一个首一多项式必可分解为首一既约多项式之积，并且 当不考虑因式的顺序时，该分解是唯一的 f(x)=p,(x)P2(x)…p,(x) 其中，px)为首一既约多项式，a为正整数 。d次多项式fx)不可能有多于d个的一次因式，至多有d个根 。a为之根的充要条件是(x-a川fx) 。若p(x)是fx)的k重既约因式，则p(x)必是fx)的k-1重既约 因式
既约多项式 每一个首一多项式必可分解为首一既约多项式之积，并且 当不考虑因式的顺序时，该分解是唯一的 其中，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&LCM GCD(x),gx)小：同时除尽x)和gx)的次数最高的首一 多项式 。LCM[fx),g(x小：同时被x)和gx)除尽的次数最低的首 一多项式 o f(x)g(x)=(f(x),g(x))[f(x),g(x)] o Euclidean:算法 (f(x),g(x))=A(x)f(x)+B(x)g(x) f()=x+x8+x2+x2+x+1=(x+x3+xx+x3+x+10十x2+1) 8x)=x+x2+x+1=x+Ix3+1) （f(x),g(x)月=x3+1=1f(x)+(x3+x3+xx4+x3+x+1) =A(x)f(x)+B(x)g(x)
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 = + + + + + = + + + + + + + = + + + = + + = + = + + + + + + = +
N 国家重点实验室 多项式的加法和乘法 设 fx=fnxn+fn-1Xn-1+.+fx+f。f∈Fp g(x)=gmxm+gm-1xm-1+...+gx+g8:EFp 。多项式相等 >若m=n,且对所有1，f=g则fx)=g(x) 。多项式加（若n>m) f(x)+g(x)=fr x"+...+fm+1xmt1(fm+gm)xm+...+(f+g)x+(fo+ go) 。多项式乘 f(x)g(x)=hntm xntm+hntm-1xntm-1+...+hxh ∑f8,i=0,1,m,n≥m i=0 h,= ∑fg-yi=m+l,…,m+n i=i-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 − = − = − = = = + +
国家重点实验室 多项式剩余类环 。结论 >按上述定义的加法和乘法运算，F[x]构成一个具有单 位元、无零因子的可换环 。多项式剩余类环 >以一个Fp上的多项式x)=fnxn+fn-1xn-1++fX+f为模 的剩余类全体构成一个多项式剩余类环 >F[灯上任一多项式x)的一切倍式集合x)组成一个理 想。以此理想把Fx]划分陪集，这些陪集全体就构成 了模x)的剩余类环 。剩余类之间的加法和乘法运算规则 alx)+b(x)=a(x)+b(x) ax)·bx)=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)