数学的预备知识.doc
10页
1数学的预备知识1.1群、环.域的基本知识，群的陪集分解整数环多项式环模q运算下的整数环模p(x)运算下的多项式环整数环上的有限域｛模p运算｝ Z/(p)多项式环上的有限域｛模p (x)运算｝ F (x) /p (x)1.2有限域生成和举例GF⑵域上的4阶本原多项式：x4+x+l 它是GF (2)域上的4阶不可约多项式， 它的周期是24-loGF(24)域上的本原元a,以及元素的两种表示 由a的方幕构成所有非零元素的乘法循环群 所有非零元素的多项式表示、即1, a, a?的线性组合 乘法循环群中元素的阶GF (24)域上的特征元素的最小多项式最小多项式的共辄类元素的阶、最小多项式的周期GF (2°)域的构造GF (2°)的子域和最小子域GF (24)域上元素的分裂域 多项式x"+x的因式分解例1验证x4+x+l是不可约多项式x不能整除x4+x+l,余式为1X+1不能整除x4+x+l,余式为1 商 X’/余 x'+x+l 商 X?/余 x2+x+l 商x/余1x2+x+l不能整除xJx+l 商 X?/余 x3+x2+x+l 商x/余1例2验证X4+X+1的周期是15x4+x+l的周期是x4+x+l整除x"+l, N取最小的整数。
验证最小整 数是否是15 = 2—1x4+x+l 除以 xN商NX4/余NX-3 +N-4X商xN7/余xNxN-6 + xN"7商NX'/余.广+ xw商NX"/余NX8 +xN-9 + xN-10商xN余xN9 +严 XNH1商NX"/余NX10 4-xZ + xi商NX审余NX11 4-xN-14商xN"/余xN15例3多项式X4+X+1的除法电路多项式除法电路多项式x4+x+l的除法电路多项式x4+x+l的除法电路的状态表时序第一级第二级第三级第四级输出a oa1a 2a 301000101002001030001411005011060011711018101090101101110110111121111131011141001151000例4 GF(24)的生成、元素的方幕表示和多项式表示.元素的阶 GF (2)域上的4阶本原多项式x°+x+l的根(X：a 4+ a +1=0 即 a ° = 1 + a由oc生成GF(2m) Ji的元素元素元素阶数001C(1aC(15a2oc215a3a35a41 + oc15a5a + a23a62 . 3oc + a5a71 + oc + a315a81 + a215a9a + a35a101 + a + a23a119 Qa + ot + a15a121 + a + a2 + a35a131+ a2+ a315a141+ a315a151例5 GF(24)上的元素的分类以及相应的最小多项式元素最小多项式元素的阶数和 最小多项式的周期2 4 8a, a , a , ax4+x+l153 6 12 9a , a , a , ax4+x3+x2+x+l5a5, a10x2+x+l3a7, a14, a13, a11x4+x3+l151x+110例6 GF(2“)上的元素最小多项式和它们的因式分解 x4+x+l = ( x- a ) ( x- a2) ( x- a4) ( x- a8) x°+x'+ x2+x+l= ( x- a3) ( x- a6) ( x- a12) ( x- a9) x4+x3+l= (x-a7) (x-a14) (x-a13) (x-a11) x2+x+l= (x-a5) (x-a10)x+l= ( x-1)例7 GF(24)域的构造、特征和子域GF(24)域元素的总数=2’GF(24)域的特征是2,即最小子域是2个元素：0、12整除2°GF(24)域的子域是GFQ'),有4个元素：0, 1, a5, a102?整除T例8 GF(2°)上的多项式x"+xX16 + X = (X1' + 1) X=(x°+x+l) ( x4+x3+ x'+x+l) ( x4+x3+l) ( x2+x+l) ( x+1) X=(x-a ) ( x- a2) ( x- a4) ( x- a8)(x-a3) ( x-a6) (x-a12) ( x- a9)(x-a7) (x-a14) (x-a13) (x-a11)(x-a5) (x-a10) ( x-1) x1.3有限域基本概念本原多项式本原元元素的阶有限域的特征元素的最小多项式最小多项式的共辄类分裂域基本性质GF (Q)域非零元素P的阶整除(Q-l), (X- p)整除xJ 有限域的所有非零元素构成一个乘法循环群 GF (Q)域中存在本原元有限域的特征有限域的特征是一个素数G + 0)p"=刖 + 0 严有限域元素的最小多项式元素的最小多项式整除以元素为根的多项式 多项式xQ-x的最小多项式分解GF (Q)域中元素的多项式表示以及方幕表示GF (Q)域共有p,n个GF (Q)域的结构存在一个GF (Q)域，Q=Pm其中p是素数，m是正整数存在一个GF (q)域上m阶的本原多项式 最小多项式和共辄类元素P卩是P的最小多项式的根最小多项式根的共辄类最小多项式的共辄类因式分解基本性质的证明：定理10・3:设陆陶…卩q・i是有限域GF(Q)上的非零元xQa-l= (“1)(肝2)・・・(十险1)。
非零元素P的阶整除(Q-l), (X- p )整除 xJ证明：GF(Q)上的非零元素生成一个乘法群，若D是非零的域元素，它的阶为h,由生成乘法群的子集有 h各元素，ph=l,由乘法群的陪集分解知，的阶h整除(Q-1),是x^-l的 根， (因此有卩Q" =(0〃) ： * =1, (x-卩)/xQ_1-l,故 XQ_1-1= (x-pi) (x-p2)…(x-pQ-i) o定理104 GF(Q)域中非零元素构成一个乘法循环群 证明：F*记作全部非零元素的集合，F*是乘法群，共Q-1个元素 设aWF*, a\ i=l> 2・・・至多有Q-1个不同的值即r使a1 = ai+r成立的最小正整数，则l
申的全部元素是一个乘法循环群定理10.5任意一个有限域GF(Q)必有一个本原元证明：GF(Q)的全部非零元素组成一个乘法循环群，如定理10.4所 述，其中Q・1阶元素a就是GF(Q)的本原元定理10.6每个GF(Q)包含有唯一的最小子域,它含有素数个元素， GF(Q)的特征是这个素数证明：构造集合G=｛0. 1、2. ...｝,显然G是有限的，设G中有p 个元素，G是加法的循环群，(它是模p的)对加法运算是一个交换群, G中元素的乘法运算，由GF(Q)乘法运算分配律确知，G上元 素乘法运算是mod p的，对乘法运算是封闭的，服从交换律, 结合律，有唯一的单位元素1,有唯一的逆元素故G=｛0、1 p-l｝是一个域GF(p), p是素数G中任意一个元素(3,则｛0(3、1 (3 9-1)13｝共有p个元素，彼此各不相同这其中必有一个元素与卩相乘为 P，该元素为乘法单位元素，必有一个元素与D相乘为1, 该元素为|3的乘法逆元素如果｛00、10、…、(p-l) (3 ｝中有两个元素相等,记做a 0 =b (3 , a p -b (3 =0o由乘法分配律可写作(a -b) 0=0而这与(a-b)、|3都是GF(Q)中的非零元素相矛盾，因此 {0 3、1 (3 (p-1) 共有p个元素，彼此各不相同。
定理10.7： GF(Q)上每个元素都只有唯一的GF(q)上最小多项式, 若f(x)是卩的最小多项式,而多项式g(x)以p为根,则f (x) |g(x)o 证明：设f(x)、fi(x)都是卩的最小多项式，首项系数均为1可以写作 fi(x)=f(x)+r(x), deg[r(x)]
定理10.9♦: GF(Q)是GF(q)的扩展域，它的本原元oc在GF(q)域 上的本原多项式是f (x), deg[f (x)]=m，则GF (Q)共有q"个元素, 且每个元素可以写作卩=+ am.2am'2 + …+ aia + a0 (*)3()> ax> —am.1eGF(q)o证明：由域的性质知，(*)给出的元素peGF(Q),且互不相等否则 a是低于m次多项式的根，a的最小多项式是低于m阶的 因为GF(Q)中的所有元素都可以用W形式来表示而卩的这种表示式至多给出『个元素，故GF(Q)中任何一个元素都可以写作W形式定理10.。
