密码学数学基础

第4章数学基础一来自整数理论的一些概念1数的整除性初等数论研究的基本对象是整数集合},3,2,1,0{K±±±=Z和自然数集合(即正整数集合)},4,3,2,1{K=N定义：设Z为有全体整数而构成的集合，若0b≠且使得此时称b整除。记为,还称为的除数(因子)。如果不存在整数使得则称b不整除a。Zmba∈,,mba=aab|bammba=例如：24的正因子是：1、2、3、4、6、8、12和24。对于数的整除有以下规则成立：1.如果则。1|a1±=a2.如果且，则ba|ab|ba±=。3.任何能整除0。0≠b4.如果而且，则对任意整数和n有gb|hb|m)(|nhmgb+。为明白最后一个规则，证明如下：如果，则是b的倍数，可以表示成：gb|g1gbg×=，为某一整数。1g如果，则是b的倍数，可以表示成：hb|h1hbh×=，为某一整数。1h故有：)(1111nhmgbnbhmbgnhmg+×=+=+所以能整除。bnhmg+12素数(质数)的概念:定义：整数被称为素数是指1>pp的因子仅有pp−−,,1,1。例如：下面的表给出了在2000以内的所有素数。表2.12000以内的所有素数2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199211223227229233239241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499503509521523541547557563569571577587593599601607613617619631641643647653659661673677683691701709719727733739743751757761769773787797809811821823827829839853857859863877881883887907911919929937941947953967971977983991997100910131019102110311033103910491051106110631069108710911093109711031109111711231129115111531163117111811187119312011213121712231229123112371249125912771279128312891291129713011303130713191321132713611367137313811399140914231427142914331439144714511453145914711481148314871489149314991511152315311543154915531559156715711579158315971601160716091613161916211627163716571663166716691693169716991709172117231733174117471753175917771783178717891801181118231831184718611867187118731877187918891901190719131931193319491951197319791987199319971999算术基本 定理 三点共线定理勾股定理的证明证明勾股定理共线定理面面垂直的性质定理 。任意大于1的整数都能被因式分解为如下的唯一形式：attPPPaαααK2121=其中都是素数而且每一个tPPPK>>21()K,3,2,10=>iiα。例如：13791×=；13117110112××=2任一个给定的正整数可以通过简单列出后面 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 中非零分量来说明。例如：整数12可以表示为{}1,232==aa；整数18可以表示为{}；2,132==aa两个数的乘法等同于对应指数分量的加法：pppnmkmnK+=→=对所有的p例如：2161812=×=l；3122=+=k；3213=+=k；3332216×=对于，它们的素数因子的关系如何？如果任何以形式表示的整数仅能被对应素数分量小于或者等于它的另一整数整除，其中ba|kpjpkj≤，因此有：ppbaba≤→|对所有的p例如：；；12|36；；12=a36=b32122×=223236×=；222ba==3321ba=≤=3互为素数定义：符号表示和的最大公因子。正整数是和b的最大公因子，如果满足下列条件：),gcd(baabca1.是a和因子；cb2.任何和的因子也是的因子。abc此外，还有如下的等价定义：]||,max[),gcd(bkakkba且=因为通常要求最大公因子为正，而),gcd(),gcd(),gcd(),gcd(babababa−−=−=−=，一般)|||,|gcd(),gcd(baba=。此外，由于0均能被所有非零整数整除，因此有aa=)0,gcd(。如果将两个正整数分别表示为素数的乘积，很容易确定它们的最大公因子。),min(),gcd(pppbakbak=→=对所有的。p确定一个大数的素因子在计算上往往是不容易做到的。如果两个正整数之间没有共同的素数因子，则称整数和互素。即它们仅有一个公因子1。换句话说，如果ab1),gcd(=ba，则认为和b互素。a34带余除法及展转相除法（欧几里德算法）定理1：（带余除法）设0,,>∈bZba则存在唯一决定的整数q和r，使得：brrqba<≤+=0,证明：用作单位来度量b}{][aaa+=，为的以b为单位的整数部分，为a的小数部分。先证明满足条件的和][aa}{aqr是存在的。为此令⎥⎦⎤⎢⎣⎡=baq，，则和qbar−=qr都是整数，并且由于⎭⎬⎫⎩⎨⎧=−=baqbabr，而10<⎭⎬⎫⎩⎨⎧≤ba，从而10<≤br，即。br<≤0再证明和qr是唯一确定的。如果又有整数q′和r′使得，，则rbqa′+′′=br<′≤0brr<′−，并且)(qqbrr−′=′−。这表明rr′−是正整数b的倍数，并且rr′−的绝对值又小于b。只有可能rr′=，于是qq′=，证毕。事实上，从几何直观上来看，定理是很明显的：设想把所有正，负整数和零都描在实数轴上，那么的一切整倍数qb便形成实数轴上的一列等距分点。代表整数的那个点必落在某两个相邻分点的区间内（qb,(q+1)b）,或者与这样一个区间的左端重合。这就意味着我们有babrrqba<≤+=0,。下图说明了给定a和正整数b，总能找到和qr满足之前的关系。数轴上的点代表整数；必将为余数线上某一点（图中显示a为正数的情况，为负数也是类似的情况）。由0为起点，经过b，2b，直到qb，以致aaaqb≤并且由qb到a的距离是abq>+)1(r，这样就得到了唯一的值和qr，剩余值r通常称为余数。4利用定理1可以得到如下重要的结果：定理2对于集合{ZyxbyaxS}∈+=,|，有如下结论：1.若，则。Snm∈,Snm∈±2.若ZcSn∈∈,，则。Scn∈3.设d为集合中的最小正整数，则恰好是的所有倍数构成的集合。SSd4.。),gcd(bad=证明：（略），可作为习题。注1集合恰好是由的所有倍数构成的，于是可以得到最大公因子的一些有用的性质：S),gcd(ba注2我们有如下结论：1.设m为正整数，则),gcd(),gcd(bammbma×=。2.若，则dba=),gcd(da和db是互素的整数。3.和的每个公因子都是的因子。ab),gcd(ba4.若1),gcd(),gcd(==mbma，则1),gcd(=mab。5.若，是不全为0的整数，则对每个整数有abx),gcd(),gcd(axbaba+=。6.若，abc|1),gcd(=bc，则。ac|由这些结论，我们可以得到求出最大公因子的如下算法：展转相除法（欧几里德算法）：假定。限制算法仅仅考虑正整数是可以接受的，因为0>>fd),gcd(),gcd(baba=。5EUCLID(d,f)1.fYdX←←;2.),gcd(0fdXreturnYif==3.YXRmod=4.YX←5.RY←6.goto2例如：要找出)1006,1970gcd(904100611970+×=)904,1006gcd(16290411006+×=)162,904gcd(941625904+×=)94,162gcd(68941162+×=)68,94gcd(2668194+×=)26,68gcd(1626268+×=)16,26gcd(1016126+×=)10,16gcd(610116+×=)6,10gcd(46110+×=)4,6gcd(2226+×=)2,4gcd(0222+×=)0,2gcd(所以。2)1066,1970gcd(=5模运算我们现在知道，任意给定一个正整数和任意一个整数，如果用除以，naan6得到商q和余数r将满足如下关系：⎣naqnrr⎦a/;0=<≤+qn=这里表示小于或者等于的最大整数。⎣⎦xx如果，则称整数和b模同余，可以书写为。)mod()mod(nbna=annbamod≡例如：；23mod473≡10mod921−≡注意：如果则。namod0≡an|模运算符就有如下性质：1.如果则。)(|ban−nbamod≡2.等价于)mod()mod(nbna=nbamod≡。3.等价于。nbamod≡nabmod≡4.如果而且nbamod≡ncbmod≡，则有ncamod≡。模运算操作规则模运算规则如下：1.()()[]()nbannbnamodmodmodmod+=+。2.()()[]()nbannbnamodmodmodmod−=−。3.()()[]()nbannbnamodmodmodmod×=×。下面证明第一条规则的合理性：定义arna=)mod(，则可得为某一整数；brnb=)mod(jjnraa,+=kknrbb,+=为某一整数。有：nknrjnrnbabamod)(mod)(+++=+7nnjkrrbamod))((+++=nrrbamod)(+=nnbnamod)]mod()mod[(+=其它规则的合理性证明留为作业。要注意，指数运算可以看作是多次重复乘法。例如：为了计算可以按照如下方式进行：13mod11713mod4121112≡=13mod341124=≡13mod21323411117≡≡××=因此，通常加法、乘法、减法的规则都可以适用于模运算，注意：除法运算在某些情况下也适用，例如当模数为素数的时候。n如下表给出了模8的加法和乘法运算的结果：首先观察加法表，运算结果一目了然，并且在这个结果矩阵中呈现一种规律性。此外，类似普通的加法，在模运算中每个数存在加法逆元，或者称为相反数。在这种情况下，一个数的加法逆元xy是满足的数。为了找出左边一列数对应的加法逆元，可以扫描对应列中值为0的项目，0所在列对应的位于顶行位置的数就是要找的加法逆元；同样的，乘法表中的表项也是很容易得到的。在模8乘法运算中，一个数的乘法逆元8mod0≡+yxxy是满足的数。这里必须注意并不是所有模8的数都存在乘法逆元；这一点随后还会讨论。8mod1≡×yx模8运算×0123456700000000101234567202460246303614725404040404505274763606420642707654321+012345670012345671123456702234567013345670124456701235567012346670123457701234568模运算的性质定义集合为所有小于的非负整数集合：nZn)}1(,,1,0{−=nZnK该集合也被当作模的余数集合。如果在该集合上实行模运算，中的整数保持如下性质：nnZ1.交换律：nwxnxwnwxnxwmod)(mod)(mod)(mod)(×=×+=+2.结合律()[]()[]()[]()[]nyxwnyxwnyxwnyxwmodmodmodmod××=××++=++3.分配律()[]()()[]ywxwnyxw×+×=+×mod4.恒等nwnwnwnwmodmod)1(modmod)0(=×=+5.ncbncabamodmod)()(≡→+≡+6.互素与如果nancbncabamodmod)()(≡→×≡×例如：为了说明这一点，考虑一个附加条件不满足的例子：8mod738mod242768mod21836≠≡=×≡=×但是造成这个奇怪的结果的原因是模数为合数时，有乘法零因子存在。最后，还可以观察到如果p是一个素数，则集合中的所有数均与p互素。这样就能在之前所列的性质中再加上一条性质：乘法逆元()1−w对每一个，存在一个，使得pZw∈zpzwmod1≡×。因为和互素，如果用乘以中所有的数模，得到的余数将以不同pwwpZp9的次序涵盖中的所有数。那么。至少有一个余数的值为1。因此，在中的某个数与相乘模pZpZwp的余数为1。这个数就是w的乘法逆元，命名为。1−w最后一点：如果，则能在中找到，使得1),gcd(=nanZbpbamod1≡×。原因与前面是相同的。因为a与互素，如果用与中的所有数相乘模，得到的与数将以不同的次序涵盖中的所有数。因此在中存在某个数，使得。nanZnnZnZbpbamod1≡×例如：表2.3提供了说明本概念的一个例子。表2.3模7运算+012345600123456112345602234560133456012445601235560123466012345×012345600000000101234562024613530362514404152635053164260654321ww的加法逆元w的乘法逆元00—161254345432523616数论中一些有用的定理定理3（费马定理）：如果为素数，a是不能被整除的正整数，则有：pp10papmod11≡−证明：易见，若中所有数均与a相乘模，结果仅引起原中数的次序重排，并且，。因此，有pZppZpamod00≡×{}pappapamod)1(,,mod2,mod−K={})1(,,2,1−pK。可得：))1((32apaaa−××××L[]ppappapamod)mod)1(()mod2()mod(−×××≡Lppmod)!1(−≡然而，我们有1)!())1((32−−=−××××paapapaaaL所以ppappmod)!1()!1(1−≡−−两端消去，因为它与)!1(−pp互素。定理得证。费马定理的另一种等价形式：如果p是素数，a是任意正整数，则：paapmod≡。费马定理的一个具体应用：例如：求的最末两位数字。4003由于3和100互素，由费马定理知：。于是：100mod1340≡)100(mod11)3(3101040400≡≡=，所以的最末两位数字是01。4003欧拉 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 在引入欧拉定理之前，需要首先介绍数论中的一个重要的量，即欧拉函数（Euler’stoientfunction），记为)(nφ，)(nφ表示小于且与互素的正整数的个数。nn11如下表列出了30以内的整数的)(nφ值，)1(φ被定义为1，但没有实际意义。表—某些数和它们的欧拉函数：n123456789101112131415)(nφ11224264641041268n161718192021222324252627282930)(nφ8166188121022820121812288很显然，对于任意一个素数，有：p1)(−=ppφ现在假定有两个不同的素数和q，则对于ppqn=，有：)1()1()()()()(−×−===qpqppqnφφφφ为了完全证明这一命题，考虑模n的完全剩余类集合为=nZ{)1(,,2,1,0}−pqK，其中不与互素的余数含于两个集合n{}pqpp)1(,,2,−K，和0中。因此：{qpqq)1(,,2,−K}()()[]111)(+−+−−=pqpqnφ1)(++−=qppq)1()1(−×−=qp)()(qpφφ×=对于一般的整数n，它的欧拉函数)(nφ的求解 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 由以下定理给出：定理4：1)1(=φ，当的时候，设是的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 分解式（还记得算术基本定理吗？），则：2≥ngegeepppnL2121=n)11()()(111∏∏==−+×=−=giigieieipnppniiφ。请同学将这个定理作为习题作业，来证明。12欧拉定理定理5（欧拉费马定理）：对于任何互素的整数a和，有：nnanmod1)(≡φ证明：如果为素数，则该命题成立，因为此时n)1()(−=nnφ，适合费马定理条件。不妨设n为一般的正整数，小于的且与互素的正整数的集合，标记如下：nn{})(21,,,nxxxRφK=现在对该集合中的每个整数乘以模：an{})mod(,),mod(),mod()(21naxnaxnaxSnφL=集合是集合SR的一个置换（即元素相同，顺序不同），原因如下：1.因为和互素，和也互素，则一定和也互素。因此，中的所有数均小于n并且和互素。anixniaxnSn2.S中不存在重复的整数。如果naxnaxjimodmod=，则。jixx=因此有∏∏==≡)(1)(1)(modniiniinxaxφφ)n≡+φ∏∏==≡⎥⎦⎤⎢⎣⎡)(1)(1)()(modniiniinnxxaφφφ)(mod1)(nan≡φ证毕。欧拉定理的另一种等价形式也很有用：a(mod1)(na这种形式在说明RSA算法的时候是很有用的。定理6给定两个素数p和以及整数qpqn=和，其中，则下列关系成立：mnm<<0nmmmqpnmod1)1)(1(1)(≡=+−−+φ证明：如果，则根据欧拉定理显然成立。假定gcd(，因为，等式等价于逻辑表达式(m不是的倍数)AND(不是1),gcd(=nm1),≠nmqpqn=1),gcd(=nmpm13的倍数)。如果是mp的倍数，则和有公因子mnp，因而是不可能互素的。同样，如果m是的倍数也是一样的。所以q1),gcd(≠nm等价于是mp的倍数或者是q的倍数。m下面讨论一下是mp的倍数的情况，显然cpm=，是某个正整数。在这种情况下，必然有；否则也是q的倍数，但是c1),gcd(=qmmpqm<。自然有：[]qmpqmod1)()(≡φφ，也就是；qmnmod1)(≡φ因此，存在某个正整数使得：kkqmn+=1)(φ在等式两边同时乘，有：cpm=kcnmkcpqmmn+=+=+1)(φnmmnmod1)(≡+φ是的倍数的情况也可以采用类似的方法得出。于是，定理6成立。mq注记：由这个定理可以推出：[]nmknmod1)(=φnmnkmod1)(≡φnmmnkmod1)(≡+φ中国剩余定理（CRT）中国剩余定理，在研究许多复杂问题时，有着特别的意义。许多自以为通晓此定理的人，未必如此！例如：（孙子算经）今有物不知其数。三三数之余二，五五数之余三，七七数之余二。问物几何？14答曰：)105(mod15221370223×+×+×≡（口诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。）问题是：70，21，15是如何得到的？原问题为求解同余方程组：2(mod3)3(mod5)2(mod7)xxx≡⎧⎪≡⎨⎪≡⎩注意：若为上述同余方程组的解，则0x10501×+=kxx也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组：1(mod3)0(mod5)0(mod7)xxx≡⎧⎪≡⎨⎪≡⎩0(mod3)1(mod5)0(mod7)xxx≡⎧⎪≡⎨⎪≡⎩0(mod3)0(mod5)1(mod7)xxx≡⎧⎪≡⎨⎪≡⎩的特殊解：15100=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛21010=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛70001=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛定理7（中国剩余定理）：设自然数两两互素，并记，则同余方程组：rmmm,,,21LrmmmNL21=在模同余的意义下有唯一解。N证明：考虑方程组：15⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧≡≡≡≡≡+−)(mod0)(mod0)(mod0)(mod0)(mod0111riiimxmxmxmxmxLLL)1(ri≤≤由于各个两两互素，这个方程组做变量替换，令imymNxi×=)/(方程组等价于解同余方程组：)1()(mod1)/(rimymNii≤≤=。若要得到特解，只要令iiiymNx×=)/(则方程组的解为：)(mod22110Nxbxbxbxrr+++=L在模同余的意义下唯一。证毕。N二来自群论中的若干基本概念定义（群）设为非空集合，若在中定义一个运算“·”，使得（表示从中取出得任意元素）有GGGba∈∀,Gba,Gba∈⋅，并且满足如下公理：1.结合律成立：有Gcba∈∀,,)()(cbacba⋅⋅=⋅⋅；2.中存在单位元：，有GeGa∈∀aeaae=⋅=⋅；3.中存在相应的逆元：GGa∈∀，有，使得；Ga∈−1eaaaa=⋅=⋅−−11则称G对运算“·”形成一个群，具体表示为),(⋅G，一般记为G。注：1.|G|表示群G内的元素的个数；若+∞<G（G内的元素有限），则称G为有限群；若+∞=G，称G为无限群。2.若，有，称为交换群（或称为Abel群）。Gba∈∀,abba⋅=⋅GG163.为群，GH是G的一个非空子集。如果相对于G的那个运算来说，H也是一个群，则称H是G的一个子群，记为GH≤。我们可以发现全体整数的集合Z对整数的加法形成一个群+Z。取定一个正整数，则由的一切整倍数所形成的集合是nnnH+Z的一个子群。易见，对于同余式：)(modnba≡相当于说；于是，上述同余式可以写为：nHba∈−)(modnHba≡定义（左陪集）：设G是一个群，H是G的一个子群。设Ga∈，那么集合{Hhah∈|}被称为群G中相对于子群H的左陪集，表示为，即，为左陪集代表元。自然，也有右陪集的概念。aaH{}HhahaH∈=|a注：1.有关左陪集的重要性质：(1).HhabHaH∈⇔=−1(2).HaHaH∈⇔=(3).bHaHaHb=⇔∈2.,有或者Gba∈∀,bHaH=φ=∩bHaH3.可以按照子群GH的左陪集分解为一些两两不交的等价类。若，它们是在同一类中，是指，即；形式地记为：Ggg∈21,Hgg∈−211HgHg21=)(mod)(Hba左≡4.易见，UGggHG∈=5.为群，。GGH≤H在G中的左陪集的个数称为H在G中的指数，记为。[]HG:6.若G为有限群，，则有：GH≤[]HGHG:⋅=定义（正规子群）：G为群，H是G的子群，若Gg∈∀有则称HggH=H是17G的正规子群，记为HG。注：1.如果G是交换群，那么它里面的任何一个子群都是的正规子群。G2.设HG，则对自己的乘法构成群，这里HG/},|{/的正规子群是GHHaaHHG∈=。证明：，有：HGbHaH/,∈∀HGabHabHHHHbabHaH/)())((∈===由于群G满足结合律，自然关于陪集的运算也满足结合律；另一方面，可以验证HG/H为中的单位元，并且，说明中的每个元素都有逆元。所以是群。HG/HHaaHaaH==−−11))((HG/HG/定义（商群）：设是群，GHG，则关于子集的乘法构成的群称为G关于HG/H的商群。注：群G的商群HGG/=是类比于整数加群+Z模整数而得到的剩余类加群：n{}]1[,],2[],1[],0[/−>=<+nnZL定义（循环群）：若群G可以由一个元素的方幂生成，即},,,,1,,,,{320123LLgggggggG==−−−，此时，称G为循环群，其中g为的生成元，记为。G>=<gG例如：循环群的几个例子：1.全体整数的集合Z对于整数的加法形成一个循环群，记为+Z，它的生成元仅有1和-1。+Z为无限循环群。2.次复单位根对复数乘法形成一个阶循环群nnξξ,>=<nU为n次本原单位根。183.整数同余类环中的全部元素对同余类加法所形成的群，是一个阶为的循环群。若和互素，则由决定的模n同余类就是的生成元。事实上，，必有一个整数使得><nZ/+nZnana][a+nZ+∈∀nZb][k)(modnbka≡⋅。这样，我们有：][][][][][][bakaaaak=⋅=+++=L（有k个）][a4.整数同余类环的乘法可逆元的全体组成的集合对同余类乘法形成一个群，这个群是交换群，一般不是循环群，以为例，><nZ/*nZ*12Z]}11[],7[],5[],1{[*12=Z它不是循环群。仅当为素数的时候，为循环群。np*nZ三环和域的基本概念定义（环）：所谓一个（结合）环，指的是这样一个集合R，在它里面定义了加法“＋”和乘法“·”两种运算，并且满足下列条件：1.集合R相对于加法“＋”来说构成交换群；2.集合R相对于乘法“·”来说封闭，且满足结合律；3.分配律成立：，Rcba∈∀,,cabacba•+•=+•)(，并且有：acabacb•+•=•+)(；注：1.，注意，当乘法不满足交换律的时候，公式一般不成立。mnnmnmnmaaaaaRa==∈∀+)(,nnnbaab=)(2.若环R对“·”来说满足交换律，称它为交换环。3.环R被称为含有单位元的环，是指R内含有乘法单位元“1”，使得有。Ra∈∀aaa=•=•11例如：环的若干例子：191.整数环Z。易见全体整数的集合对数的加法形成一个群；对数的乘法也形成一个群，它满足分配律。Z为含有单位元“1”的交换环。它是最具体最容易被接受的数环。2.剩余类环。为整数模剩余类的集合nZnZn]}1[,],1[],0{[−=nZnL它对剩余类的加法和乘法构成一个含有单位元“[1]”的交换环。3.各式各样的数域都对通常的数的加法和乘法形成一个含有“1”的交换环。4.设表示上面几个例子给出的任意一个数环。定义F},|{][0111为正整数nFaaxaxaxaxFinnnn∈++++=−−L，它是数域上的一元多项式环。F5.取大于1的正整数n，则的一切整数倍形成的集合对数的加法和乘法形成了一个不含单位元“1”的交换环。nnZ整环定义（整环）：含有乘法单位元“1”而无零因子的交换环称为整环。注：1.无零因子是指，由可以推出0=⋅ba0=a或者0=b。反之，如果，则，。否则，称为左零因子，b为右零因子。0=⋅ba0≠a0≠ba2.整环是类比于我们熟知的整数环，提取了整数环中的主要特征，例如乘法的消去律。3.任何一个整环都至少含有2个元素。恰含有2个元素的整环是存在的，例如它对模2的加法乘法运算形成一个整环，事实上，它为二元域。}1,0{2=F定义（除环）：一个环被称为除环（或斜域），是指该环的非零元全体对“·”形成一个群。定义（域）：一个可交换的除环称为域。注：201.为整数模pFp的剩余类环，p为素数，可以验证它为域。因为中的元素有限，称它为有限域；又因为pFp为素数，又称之为素域。2.域首先必是整环；反之则不然。例如，整数环Z，域上的多项式环多时整环，但它们都不是域。然而，对有限整环来说：F][xF定理8：任意一个由有限个元素组成的整环R必定是有限域。定理9：在整环R的加法群+R中，或者每个非零元素都生成一个无限阶的循环群；或者存在一个素数p，+R中的每个元素都生成一个p阶循环子群。证明：R为整环，于是R∈1。+R作为R的加法群含有由1生成的循环子群}|1{1Zkk∈⋅=><1.如果为无限循环群：><1,0,≠∈∀aRa来证也为无限循环群。若否，设的阶为，于是：><aamamaaaaammm⋅⋅=⋅+++=+++=⋅=)1()111(04434421L4434421L由于整环无零因子，必有01=⋅m，说明><1为的因子，与为无限循环群矛盾。所以也为无限循环群。m><1><a2.如果为有限循环群：><1首先断定+R元素1的阶必为某个素数p。事实上，如果假设211ppm==><，其中mpmp<<<<211,1。我们有：01111)111()111()1)(1(2121=⋅=+++=++++++=⋅⋅mppmpp4342L4434421L4434421L由于整环无零因子，所以11⋅p和12⋅p这两者中必然有一个为0，这与m=><1矛盾。所以必为素数，设mpm=为一个素数。0,≠∈∀aRa，有0)1()111(=⋅=⋅+++=+++=⋅apaaaaappp4434421L4434421L说明+R中的每个非零元素都生成一个p阶的循环子群，证毕。21注：当R为整环时，上述定理中的两种情况必有而且仅有一种成立。前一种情况称整环R的特征为0（0=Rchar）；后一种情况称整环R的特征为（）。易见，有限域作为特殊的整环，它的特征必定为。ppRchar=p推论1：F为有限域，则中的元素的个数FF是其特征的方幂，即npF=。推论2：在一个特征为的整环pR中，对任意自然数m有：mmmpppbaba+=+)(，,mmmpppbaab=)(Rba∈∀,推论3：在一个特征为的整环pR中，由等式对某个自然数成立，可以断定。mmppba=ba=子环和环同构定义（子环）：设R是一个环，φ≠⊆11.RRR，如果对1RR的运算“＋”和“·”也形成一个环，称为1RR的一个子环。定义（环同构）：设R和R′是两个环。如果有一个保持加法和乘法运算的1-1映射到R′之上，且有：Rba∈∀,)()()(babaϕϕϕ+=+)()()(baabϕϕϕ⋅=此时，称R和R′同构。注：同构映射ϕ把R中的“0”元映射成为R′中的“0”元；把R中的“1”元映射成为R′中的“1”元；把R中的子环映射成为R′中的子环。定理10：任何一个特征为0的整环R（或者域）都包含了一个整子环（子域），它同构于整数环FZ（有理数域）；任何一个特征为的整环Q0>pR（或者域）都包含一个子整环同构于。FpF22注：由此定理知，整环或者域都包含有一个最小的整环（或者最小的域）做它们的出发点。下面讨论交换环R的商环。我们已经知道，对群G的一个正规子群H来说，可以给出商群HGG/=，这个商群以H的各个陪集作为元素，使得成为G的一个缩影。如何把这个现象类比到商环呢？先从最具体的整数环HG/Z入手，设R为整数环Z，它的子环：}|{1ZkknnR∈⋅>==<Zlm∈∀,，称模同余，即lm,1R)(mod1Rlm≡，相当于lmn−|，由数论的写法。)(modnlm≡R对的商环就是：1R]}1[,],1[],0{[/1−==nZRZnL我们已知在的乘法为，它的意义是：nZ][]][[abba=][],[21brbara∈+∀∈+∀，有：][))((]][[211221abrrbrarabrbraba=+++=++=，相当于：12112Rnrrbrar=>∈<++这就诱导出一般交换环R中的理想子环的想法。定义（理想）：交换环R的一个子环称为1RR中的一个理想子环（简称理想），如果有。1,RrRa∈∈∀1Rar∈注：1.设是整环nbbb,,21LR中的任意一组元素，则形如：Rabababarinn∈∀+++=,2211L的元素全体是R中的理想，它称为由这些元素生成的理想，记为：。1Rnbbb,,,21L><nbbb,,,21L特别，由单独一个元素所生成的理想b><b被称为R中的一个主理想，由R中的一切形如ab的元素组成，}|{Raabb∈>=<。2.整数环Z中，Z的任何一个子环都是一个理想；Z的任何一个理想都是主理23想。原因是，+Z是循环群，+Z的任何一个子群也必然是循环群。nH3.域上的多项式环中，不一定每一个子环都是理想子环，例如，有理数域上的一元多项式环中，带整系数的那些多项式组成一个子环，但不是理想。然而，可以证明多项式环中的每一个理想都是主理想。F][xF][xQ][xF定理11：设R是一个交换环，是1RR的一个理想。如果将两个模同余类的和与积分别定义为同余类1R][],[ba][],[abba+，即：][][][],[][][abbababa=⋅+=+则由全部模同余类所组成的集合1R1/RRR=对上述运算构成环，称为R对的商环。1R有限域定义（子域，扩域）：设E为一个域，为FE中的一个非空子集。如果相对于E中的加法和乘法来说是一个域，则称为FFE的一个子域（或者基域），E为的一个扩域（或扩张）。F注：1.任何一个特征为0的域E都包含一个子域，它同构于有理数域，任何一个特征为的域FQpE都包含了一个子域，它同构于素域。易见，扩域FpFE对E中的加法运算和中的元素与FE中的元素的乘法运算形成上的一个向量空间。如果FE作为上的向量空间是维的，则FnE被称为的一个次扩张，否则FnE称为的无限次扩张。前者记为FnFE=]:[，后者记为。∞=]:[FE2.特征为0的域E可以视为由有理数域Q扩张而来；特征为的域pE可视为由素域扩张而来。对于特征为的域pFpE来说，若设E的乘法单位元为，则e24e的全体整倍元的集合为pFopeepee≅=−}|)1(,,2,{L。这就说明E可视为由扩张而来。若设，则存在个元素pFnFEp=]:[n)1(niui≤≤使得E中任意元u可以唯一的表示成为：pinnFauauauau∈+++=L2211从而可知npE=定理12（域扩张）:设为任意域，而FFmmxmxmxxmidddd∈++++=−−,)(2211L为上的一个次不可约多项式，则同余类环Fd><=)(/xmFE可视为上的一个有限次扩域，并且有：FdFE=]:[。证明：首先证明为域。设><=)(/xmFE][)(xFxf∈，][)(xFxq∈∀有：)()()(xfxmxq+模的同余类设为，知它是)(xm)]([xfE中的一个元素，若，知=1，因此必有多项式]0[)(∉xf))(),((xmxf][)(xFxu∈，使得：1)()()()(=+xmxvxfxu于是有：，或者说。这说明]1[)]([)]([=⋅xfxu)]([)]([1xuxf=−><=)(/][xmxFE中的每个非零元素都有乘法逆元，所以它是一个域。下面证明。dFE=]:[E中由零次多项式，亦即中的元素所决定的那些模同余类组成F)(xmFkk∈],[E中的一个子域F；而映射][)(kk=σ是到FF之上的一个同构映射。这样，中的元素的同余类仍然为，把决定的模的同余类记为Fk][kkx)(xm][xα，这样一来中的任意多项式][xFnnxaxaaxf+++=L10)](对应于nnnnnnaaaxaxaaxaxaaxfαα+++=+++=+++=LLL101010]][[]][[][][)]([25)(αf=特别，我们有0)]([)(==xmmα,于是借助于上不可约多项式所造出得扩域F)(xmE种，元素α()是的一个零点。不仅如此，假如上的另一个多项式也以][x=)(xmF)(xlα为零点，那么由0)()]([==αlxl，可知有。事实上，有)(|)(xlxm][)(xFxf∈∀),()()()(xrxmxqxf+=其中：1110)(−−+++=ddxrxrrxrL于是1110)()]([−−+++==ddrrrfxfαααL也即E中任意元素都可以表示成为的线性组合。1,,,1−dααL另一方面，若有Faaad∈−110,,,L，使得，相当于说，仅当∑−==100diiiaα1110|)(−−+++ddxaxaaxmL0110====−daaaL。说明关于域是线性无关的，于是它们为1,,,1−dααLFE在的一个基，有FdFE=]:[。证毕。注：1.对于关系式0)]([)(==xmmα来说，意味着扩域E是基域上的不可约多项式的一个零点F)(xmα添加到上去而得到的，可把FE记为)(αF。特别的，如果是素域，而是上的一个次不可约多项式，则FpF)(xmpFd)(αpF是由个元素构成的域。事实上，任何一个有限域都可以从某个素域出发，通过添加上某个不可约多项式的一个零点得到。αppFpF2.当我们把)(αF中的元素表示成为这种形式的时候，表达式中的系数1110)(−−+++=ddrrrfαααL)10(−≤≤diri是唯一确定的，因此可以把)(αF中的元素表示为上的维向量d),,,(110−=dγγγγL。F26例如：是上的一个四次不可约多项式。易见，为上的一个四次扩域。如果把记为1)(34++=xxxm2F>++<1/][342xxxF2F][xα，那么这个域中的16个元素可以表示为：2332210,Faaaaai∈+++=αααγ这16个元素可以表示为：)0,0,0,0(0=γ，)0,0,0,1(1=γ，)0,0,1,0(2=γ，)0,0,1,1(3=γ，)0,1,0,0(4=γ，)0,1,0,1(5=γ，)0,1,1,0(6=γ，)0,1,1,1(7=γ，)1,0,0,0(8=γ，)1,0,0,1(9=γ，)1,0,1,0(10=γ，)1,0,1,1(11=γ，)1,1,0,0(12=γ，)1,1,0,1(13=γ，)1,1,1,0(14=γ，)1,1,1,1(15=γ请读者自行计算的表达式。1565,,,αααL我们可以用线性代数的知识证明下面的定理13（望远镜公式）：设域E是域的有限次扩张，域FK是域E的有限次扩张，则域K是域的有限次扩张，并且有：F]:][:[]:[FEEKFK=事实上，我们已经注意到作为有限域一身兼具了两个交换群。其一，F相对于“＋”来说，它是交换群，并且中的每个非0元都以某个素数F+Fp作为它的阶，即，0,0,=⋅=≠∈∀+gpggFgp有p称为域的一个特征。其二，相对于“×”而言也是交换群。若为的次扩张，此时，即为元有限域。此时F}0{\*FF=FpFnnqpqFF==,Fnp1*−=qF，于是，必然有：，也就是，进一步就是，于是可以断定有限域中全部个元素都满足方程*F∈∀α11=−qααα=q0=−ααqFq0=−xxq即中的个元素的多项式的个零点。易见，，在中有分解式FqxxxGq−=)(q][)(xFxGp∈)(xGF27∏∈−=FxxGαα)()(称为有限域的一揽子多项式。)(xGF我们有重要的结论定理14：有限域的乘法群是一个F*F1−q阶的循环群。为循环群意味着存在使，此时*F*F∈α><=α*Fα称为1−q次的本原单位根；同时α也称为有限域中的本原元。F设α为有限域中的本原元，则中任意非零元FFβ都可以表示成为：的形式，其中k称为kαβ=β对本原元α的指数，记为：βαindk=同时k也称为以α为底β的对数，也可以记为βαlog=k。注：1.对于α来说，β的对数仅在模1−q的条件下唯一确定，所以规定。10−≤≤qk2.βαindk=这个函数实际上是定义在之上而在整数同余类环中取值的一个对数函数，有如下性质：*F1−qZ(1))1(mod2121−+=qindindindββββααα(2))1(mod−⋅=qindkindkββαα3.设α为有限域的一个本原元，则的非零元素FFβ是本原元的充要条件是1)1,(=−qindβα。下面的问题是，如何在中找出一个本原元使其成为对数的底？在这里我们