密码学数学基础

第 4 章 数学基础 一 来自整数理论的一些概念 1 数的整除性 初等数论研究的基本对象是整数集合 },3,2,1,0{ K±±±=Z 和自然数集合(即正整数集合) },4,3,2,1{ K=N 定义：设 Z 为有全体整数而构成的集合，若 0b ≠ 且 使得 此时称 b整除 。记为 ,还称 为 的除数(因子)。如果不存在整数 使得 则称b不整除a。 Zmba ∈,, mba = a ab | b a m mba = 例如：24 的正因子是：1、2、3、4、6、8、12 和 24。 对于数的整除有以下规则成立： 1. 如果 则 。 1|a 1±=a 2. 如果 且 ，则ba | ab | ba ±= 。 3. 任何 能整除 0。 0≠b 4. 如果 而且 ，则对任意整数 和n有gb | hb | m )(| nhmgb + 。 为明白最后一个规则，证明如下： 如果 ，则 是b的倍数，可以 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示成：gb | g 1gbg ×= ， 为某一整数。 1g 如果 ，则 是b的倍数，可以表示成：hb | h 1hbh ×= ， 为某一整数。 1h 故有： )( 1111 nhmgbnbhmbgnhmg +×=+=+ 所以 能整除 。 b nhmg + 1 2 素数(质数)的概念: 定义：整数 被称为素数是指1>p p的因子仅有 pp −− ,,1,1 。 例如：下面的表给出了在 2000 以内的所有素数。 表 2.1 2000 以内的所有素数 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999 算术基本定理。任意大于 1 的整数 都能被因式分解为如下的唯一形式： a t tPPPa ααα K21 21= 其中 都是素数而且每一个tPPP K>> 21 ( )K,3,2,10 => iiα 。 例如： 13791 ×= ； 1311711011 2 ××= 2 任一个给定的正整数可以通过简单列出后面公式中非零分量来说明。 例如：整数 12 可以表示为{ }1,2 32 == aa ；整数 18 可以表示为{ }； 2,1 32 == aa 两个数的乘法等同于对应指数分量的加法： ppp nmkmnK +=→= 对所有的 p 例如： 2161812 =×=l ； 3122 =+=k ； 3213 =+=k ； 33 32216 ×= 对于 ，它们的素数因子的关系如何？如果任何以 形式表示的整数仅能 被对应素数分量小于或者等于它的另一整数 整除，其中 ba | kp jp kj ≤ ，因此有： pp baba ≤→| 对所有的 p 例如： ； ；12 | 36； ； 12=a 36=b 3212 2 ×= 22 3236 ×= ；22 2 ba == 33 21 ba =≤= 3 互为素数 定义：符号 表示 和 的最大公因子。正整数 是 和b的最大公因 子，如果满足下列条件： ),gcd( ba a b c a 1. 是a和 因子； c b 2. 任何 和 的因子也是 的因子。 a b c 此外，还有如下的等价定义： ]||,max[),gcd( bkakkba 且= 因为通常要求最大公因子为正，而 ),gcd(),gcd(),gcd(),gcd( babababa −−=−=−= ，一般 )|||,|gcd(),gcd( baba = 。 此外，由于 0 均能被所有非零整数整除，因此有 aa =)0,gcd( 。 如果将两个正整数分别表示为素数的乘积，很容易确定它们的最大公因子。 ),min(),gcd( ppp bakbak =→= 对所有的 。 p 确定一个大数的素因子在计算上往往是不容易做到的。 如果两个正整数之间没有共同的素数因子，则称整数 和 互素。即它们仅 有一个公因子 1。换句话说，如果 a b 1),gcd( =ba ，则认为 和b互素。 a 3 4 带余除法及展转相除法（欧几里德算法） 定理 1：（带余除法）设 0,, >∈ bZba 则存在唯一决定的整数 q和 r，使得： brrqba <≤+= 0, 证明：用 作单位来度量b }{][ aaa += ， 为 的以 b 为单位的整数部分， 为a的小数部分。先证明满足条件的 和 ][a a }{a q r是存在的。为此令 ⎥⎦ ⎤⎢⎣ ⎡= b aq ， ， 则 和 qbar −= q r都是整数，并且由于 ⎭⎬ ⎫ ⎩⎨ ⎧=−= b aq b a b r ，而 10 <⎭⎬ ⎫ ⎩⎨ ⎧≤ b a ，从而 10 <≤ b r ， 即 。 br <≤0 再证明 和q r 是唯一确定的。如果又有整数 q′和 r ′使得 ， ，则 rbqa ′+′′= br <′≤0 brr <′− ，并且 )( qqbrr −′=′− 。这表明 rr ′− 是正整数b的倍数， 并且 rr ′− 的绝对值又小于b。只有可能 rr ′= ，于是 qq ′= ，证毕。 事实上，从几何直观上来看，定理是很明显的：设想把所有正，负整数和 零都描在实数轴上，那么 的 一切整倍数 qb便形成实数轴上的一列等距分 点。代表整数 的那个点必落在某两个相邻分点的区间内 （qb ,(q+1)b ） , 或者与这样一个区间的左端重合。这就意味着我们有 b a brrqba <≤+= 0, 。 下图说明了给定a和正整数 b，总能找到 和q r满足之前的关系。数轴上的 点代表整数； 必将为余数线上某一点（图中显示 a为正数的情况， 为负数也 是类似的情况）。由 0 为起点，经过 b，2b，直到 qb，以致 a a aqb ≤ 并且 由 qb 到a的距离是 abq >+ )1( r，这样就得到了唯一的值 和q r，剩余值 r通常称为余数。 4 利用定理 1 可以得到如下重要的结果： 定理 2 对于集合 { ZyxbyaxS }∈+= ,| ，有如下结论： 1. 若 ，则 。 Snm ∈, Snm ∈± 2. 若 ZcSn ∈∈ , ，则 。 Scn∈ 3. 设 d 为集合 中的最小正整数，则 恰好是 的所有倍数构成的集合。 S S d 4. 。 ),gcd( bad = 证明：（略），可作为习 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。 注 1 集合 恰好是由 的所有倍数构成的，于是可以得到最大公因子 的一些有用的性质： S ),gcd( ba 注 2 我们有如下结论： 1. 设m为正整数，则 ),gcd(),gcd( bammbma ×= 。 2. 若 ，则dba =),gcd( d a 和 d b 是互素的整数。 3. 和 的每个公因子都是 的因子。 a b ),gcd( ba 4. 若 1),gcd(),gcd( == mbma ，则 1),gcd( =mab 。 5. 若 ， 是 不 全 为 0 的 整 数 ， 则 对 每 个 整 数 有a b x ),gcd(),gcd( axbaba += 。 6. 若 ，abc | 1),gcd( =bc ，则 。 ac | 由这些结论，我们可以得到求出最大公因子的如下算法： 展转相除法（欧几里德算法）：假定 。限制算法仅仅考虑正整数是 可以接受的，因为 0>> fd ),gcd(),gcd( baba = 。 5 EUCLID(d,f) 1. fYdX ←← ; 2. ),gcd(0 fdXreturnYif == 3. YXR mod= 4. YX ← 5. RY ← 6. goto 2 例如：要找出 )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 模运算 我们现在知道，任意给定一个正整数 和任意一个整数 ，如果用 除以 ，n a a n 6 得到商 q和余数 r将满足如下关系： ⎣ naqnrr ⎦a /;0 =<≤+qn= 这里 表示小于或者等于 的最大整数。 ⎣ ⎦x x 如果 ，则称整数 和b模 同余，可以 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 写为 。 )mod()mod( nbna = a n nba mod≡ 例如： ； 23mod473 ≡ 10mod921 −≡ 注意：如果 则 。 na mod0≡ an | 模运算符就有如下性质： 1. 如果 则 。 )(| ban − nba mod≡ 2. 等价于)mod()mod( nbna = nba mod≡ 。 3. 等价于 。 nba mod≡ nab mod≡ 4. 如果 而且nba mod≡ ncb mod≡ ，则有 nca mod≡ 。 模运算操作规则 模运算规则如下： 1. ( ) ( )[ ] ( ) nbannbna modmodmodmod +=+ 。 2. ( ) ( )[ ] ( ) nbannbna modmodmodmod −=− 。 3. ( ) ( )[ ] ( ) nbannbna modmodmodmod ×=× 。 下面证明第一条规则的合理性：定义 arna =)mod( ， 则可得 为某一整数； brnb =)mod( jjnra a ,+= kknrb b ,+= 为某一整数。有： nknrjnrnba ba mod)(mod)( +++=+ 7 nnjkrr ba mod))(( +++= nrr ba mod)( += nnbna mod)]mod()mod[( += 其它规则的合理性证明留为作业。 要注意，指数运算可以看作是多次重复乘法。 例如：为了计算 可以按照如下方式进行： 13mod117 13mod4121112 ≡= 13mod3411 24 =≡ 13mod21323411117 ≡≡××= 因此，通常加法、乘法、减法的规则都可以适用于模运算，注意：除法运算 在某些情况下也适用，例如当模数 为素数的时候。 n 如下表给出了模 8 的加法和乘法运算的结果：首先观察加法表，运算结果一 目了然，并且在这个结果矩阵中呈现一种规律性。此外，类似普通的加法，在模 运算中每个数存在加法逆元，或者称为相反数。在这种情况下，一个数 的加法 逆元 x y 是满足 的数。为了找出左边一列数对应的加法逆元，可以 扫描对应列中值为 0 的项目，0 所在列对应的位于顶行位置的数就是要找的加法 逆元；同样的，乘法表中的表项也是很容易得到的。在模 8 乘法运算中，一个数 的乘法逆元 8mod0≡+ yx x y 是满足 的数。这里必须注意并不是所有模 8 的数都 存在乘法逆元；这一点随后还会讨论。 8mod1≡× yx 模 8 运算 × 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 6 0 2 4 6 3 0 3 6 1 4 7 2 5 4 0 4 0 4 0 4 0 4 5 0 5 2 7 4 7 6 3 6 0 6 4 2 0 6 4 2 7 0 7 6 5 4 3 2 1 + 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 0 2 2 3 4 5 6 7 0 1 3 3 4 5 6 7 0 1 2 4 4 5 6 7 0 1 2 3 5 5 6 7 0 1 2 3 4 6 6 7 0 1 2 3 4 5 7 7 0 1 2 3 4 5 6 8 模运算的性质 定义集合 为所有小于 的非负整数集合： nZ n )}1(,,1,0{ −= nZn K 该集合也被当作模 的余数集合。如果在该集合上实行模运算， 中的整数 保持如下性质： n nZ 1. 交换律： nwxnxwnwxnxw mod)(mod)(mod)(mod)( ×=×+=+ 2. 结合律 ( )[ ] ( )[ ] ( )[ ] ( )[ ] nyxwnyxwnyxwnyxw modmodmodmod ××=××++=++ 3. 分配律 ( )[ ] ( ) ( )[ ]ywxwnyxw ×+×=+× mod 4. 恒等 nwnwnwnw modmod)1(modmod)0( =×=+ 5. ncbncaba modmod)()( ≡→+≡+ 6. 互素与如果 nancbncaba modmod)()( ≡→×≡× 例如：为了说明这一点，考虑一个附加条件不满足的例子： 8mod738mod242768mod21836 ≠≡=×≡=× 但是 造成这个奇怪的结果的原因是模数为合数时，有乘法零因子存在。 最后，还可以观察到如果 p是一个素数，则集合中的所有数均与 p互素。这 样就能在之前所列的性质中再加上一条性质： 乘法逆元 ( )1−w 对每一个 ，存在一个 ，使得pZw∈ z pzw mod1≡× 。 因为 和 互素，如果用 乘以 中所有的数模 ，得到的余数将以不同p w w pZ p 9 的次序涵盖 中的所有数。那么。至少有一个余数的值为 1。因此，在 中的 某个数与 相乘模 pZ pZ w p的余数为 1。这个数就是w的乘法逆元，命名为 。 1−w 最后一点：如果 ，则能在 中找到 ，使得1),gcd( =na nZ b pba mod1≡× 。原 因与前面是相同的。因为a与 互素，如果用 与 中的所有数相乘模 ，得到 的与数将以不同的次序涵盖 中的所有数。因此在 中存在某个数 ，使得 。 n a nZ n nZ nZ b pba mod1≡× 例如：表 2.3 提供了说明本概念的一个例子。 表 2.3 模 7 运算 + 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 × 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 w w的加法逆元 w的乘法逆元 0 0 — 1 6 1 2 5 4 3 4 5 4 3 2 5 2 3 6 1 6 数论中一些有用的定理 定理 3（费马定理）：如果 为素数，a是不能被 整除的正整数，则有： p p 10 pa p mod11 ≡− 证明：易见，若 中所有数均与a相乘模 ，结果仅引起原 中数的次序 重排，并且， 。因此，有 pZ p pZ pa mod00 ≡× { }pappapa mod)1(,,mod2,mod −K ={ })1(,,2,1 −pK 。可得： ))1((32 apaaa −×××× L [ ] ppappapa mod)mod)1(()mod2()mod( −×××≡ L pp mod)!1( −≡ 然而，我们有 1)!())1((32 −−=−×××× paapapaaa L 所以 ppap p mod)!1()!1( 1 −≡− − 两端消去 ，因为它与)!1( −p p互素。定理得证。 费马定理的另一种等价形式：如果 p是素数，a是任意正整数，则： paa p mod≡ 。 费马定理的一个具体应用： 例如：求 的最末两位数字。 4003 由于 3 和 100 互素，由费马定理知： 。于是： 100mod1340 ≡ )100(mod11)3(3 101040400 ≡≡= ，所以 的最末两位数字是 01。 4003 欧拉函数 在引入欧拉定理之前，需要首先介绍数论中的一个重要的量，即欧拉函数 （Euler’s toient function），记为 )(nφ ， )(nφ 表示小于 且与 互素的正整数的个 数。 n n 11 如下表列出了 30 以内的整数的 )(nφ 值， )1(φ 被定义为 1，但没有实际意义。 表— 某些数和它们的欧拉函数： n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 )( nφ 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 n 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 )( nφ 8 16 6 18 8 12 10 22 8 20 12 18 12 28 8 很显然，对于任意一个素数 ，有： p 1)( −= ppφ 现在假定有两个不同的素数 和 q，则对于p pqn = ，有： )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φ 的求解方法由以下定理给出： 定理 4： 1)1( =φ ，当 的时候，设 是 的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 分解式（还 记得算术基本定理吗？），则： 2≥n gegee pppn L21 21= n )11()()( 11 1 ∏∏ == − +×=−= g i i g i e i e i pnppn iiφ 。 请同学将这个定理作为习题作业，来证明。 12 欧拉定理 定理 5（欧拉费马定理）：对于任何互素的整数a和 ，有： n na n mod1)( ≡φ 证明：如果 为素数，则该命题成立，因为此时n )1()( −= nnφ ，适合费马定 理条件。不妨设 n 为一般的正整数，小于 的且与 互素的正整数的集合，标记 如下： n n { })(21 ,,, nxxxR φK= 现在对该集合中的每个整数乘以 模 ： a n { })mod(,),mod(),mod( )(21 naxnaxnaxS nφL= 集合 是集合S R的一个置换（即元素相同，顺序不同），原因如下： 1. 因为 和 互素， 和 也互素，则 一定和 也互素。因此， 中的所 有数均小于n并且和 互素。 a n ix n iax n S n 2. S 中不存在重复的整数。如果 naxnax ji modmod = ，则 。 ji xx = 因此有 ∏∏ == ≡ )( 1 )( 1 )(mod n i i n i i nxax φφ )n ≡+φ ∏∏ == ≡⎥⎦ ⎤⎢⎣ ⎡ )( 1 )( 1 )( )(mod n i i n i i n nxxa φφ φ )(mod1)( na n ≡φ 证毕。 欧拉定理的另一种等价形式也很有用： a (mod1)( na 这种形式在说明 RSA 算法的时候是很有用的。 定理 6 给定两个素数 p和 以及整数q pqn = 和 ，其中 ， 则下列关系成立： m nm <<0 nmmm qpn mod1)1)(1(1)( ≡= +−−+φ 证明：如果 ，则根据欧拉定理显然成立。假定gcd( ，因 为 ，等式 等价于逻辑表达式 (m不是 的倍数)AND( 不是 1),gcd( =nm 1), ≠nm qpqn = 1),gcd( =nm p m 13 的倍数)。如果 是m p的倍数，则 和 有公因子m n p，因而是不可能互素的。同 样，如果m是 的倍数也是一样的。所以q 1),gcd( ≠nm 等价于 是m p的倍数或者 是 q的倍数。 m 下面讨论一下 是m p的倍数的情况，显然 cpm = ， 是某个正整数。在这种 情况下，必然有 ；否则 也是 q的倍数，但是 c 1),gcd( =qm m pqm < 。 自然有： [ ] qm pq mod1)()( ≡φφ ，也就是 ； qm n mod1)( ≡φ 因此，存在某个正整数 使得： k kqm n += 1)(φ 在等式两边同时乘 ，有： cpm = kcnmkcpqmm n +=+=+1)(φ nmm n mod1)( ≡+φ 是 的倍数的情况也可以采用类似的方法得出。于是，定理 6 成 立。 m q 注记：由这个定理可以推出： [ ] nm kn mod1)( =φ nm nk mod1)( ≡φ nmm nk mod1)( ≡+φ 中国剩余定理（CRT） 中国剩余定理，在研究许多复杂问题时，有着特别的意义。许多 自以为通晓此定理的人，未必如此！ 例如：（孙子算经）今有物不知其数。三三数之余二，五五数之余 三，七七数之余二。问物几何？ 14 答曰： )105(mod15221370223 ×+×+×≡ （ 口诀 小学生乘法口诀表下载关于乘法口诀表的题目党史口诀下载一建市政口诀下载健身气功八段锦功法口诀下载 ：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百 零五便得知。） 问题是：70，21，15 是如何得到的？ 原问题为求解同余方程组： 2(mod 3) 3(mod 5) 2(mod 7) x x x ≡⎧⎪ ≡⎨⎪ ≡⎩ 注意：若 为上述同余方程组的解，则0x 10501 ×+= kxx 也为上述同余方程组 的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组： 1(mod 3) 0(mod 5) 0(mod 7) x x x ≡⎧⎪ ≡⎨⎪ ≡⎩ 0(mod 3) 1(mod 5) 0(mod 7) x x x ≡⎧⎪ ≡⎨⎪ ≡⎩ 0(mod 3) 0(mod 5) 1(mod 7) x x x ≡⎧⎪ ≡⎨⎪ ≡⎩ 的特殊解： 15 1 0 0 = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ 21 0 1 0 = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ 70 0 0 1 = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ 定理 7 （中国剩余定理）：设自然数 两两互素，并记 ，则同余方程组： rmmm ,,, 21 L rmmmN L21= 在模 同余的意义下有唯一解。 N 证明：考虑方程组： 15 ⎪⎪ ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪⎪ ⎪ ⎨ ⎧ ≡ ≡ ≡ ≡ ≡ + − )(mod0 )(mod0 )(mod0 )(mod0 )(mod0 1 1 1 r i i i mx mx mx mx mx L L L )1( ri ≤≤ 由于各个 两两互素，这个方程组做变量替换，令im ymNx i ×= )/( 方程组等价于 解同余方程组： )1()(mod1)/( rimymN ii ≤≤= 。 若要得到特解，只要令 iii ymNx ×= )/( 则方程组的解为： )(mod22110 Nxbxbxbx rr+++= L 在模 同余的意义下唯一。证毕。 N 二 来自群论中的若干基本概念 定义（群）设 为非空集合，若在 中定义一个运算“·”，使得 （表示 从 中取出得任意元素 ）有 G G Gba ∈∀ , G ba, Gba ∈⋅ ，并且满足如下公理： 1. 结合律成立： 有Gcba ∈∀ ,, )()( cbacba ⋅⋅=⋅⋅ ； 2. 中存在单位元 ： ，有G e Ga∈∀ aeaae =⋅=⋅ ； 3. 中存在相应的逆元：G Ga∈∀ ，有 ，使得 ； Ga ∈−1 eaaaa =⋅=⋅ −− 11 则称G对运算“·”形成一个群，具体表示为 ),( ⋅G ，一般记为G。 注： 1. |G |表示群G内的元素的个数；若 +∞=<+ nnZ L 定义（循环群）：若群G可以由一个元素的方幂生成，即 },,,,1,,,,{ 320123 LL gggggggG == −−− ，此时，称G为循环群，其中 g为 的生 成元，记为 。 G >=< gG 例如：循环群的几个例子： 1. 全体整数的集合 Z 对于整数的加法形成一个循环群，记为 +Z ，它的生成 元仅有 1 和-1。 +Z 为无限循环群。 2. 次复单位根对复数乘法形成一个 阶循环群n n ξξ ,>=< nZ / +nZ n a n a ][a +nZ +∈∀ nZb][ k )(mod nbka ≡⋅ 。这样， 我们有： ][][][][][][ bakaaaak =⋅=+++= L （有 k个 ） ][a 4. 整数同余类环 的乘法可逆元的全体组成的集合对同余类乘法形 成一个群 ，这个群是交换群，一般不是循环群，以 为例， >< nZ / * nZ * 12Z ]}11[],7[],5[],1{[*12 =Z 它不是循环群。仅当 为素数 的时候， 为循环群。 n p *nZ 三 环和域的基本概念 定义（环）：所谓一个（结合）环，指的是这样一个集合 R，在它里面定义 了加法“＋”和乘法“·”两种运算，并且满足下列条件： 1. 集合R相对于加法“＋”来说构成交换群； 2. 集合R相对于乘法“·”来说封闭，且满足结合律； 3. 分配律成立： ，Rcba ∈∀ ,, cabacba •+•=+• )( ，并且有： acabacb •+•=•+ )( ； 注： 1. ，注意，当乘法不满足交换律的时候， 公式 一般不成立。 mnnmnmnm aaaaaRa ==∈∀ + )(, nnn baab =)( 2. 若环R对“·”来说满足交换律，称它为交换环。 3. 环R被称为含有单位元的环，是指R内含有乘法单位元“1”，使得 有 。 Ra∈∀ aaa =•=• 11 例如：环的若干例子： 19 1. 整数环 Z 。易见全体整数的集合对数的加法形成一个群；对数的乘法也形成 一个群，它满足分配律。Z 为含有单位元“1”的交换环。它是最具体最容易 被接受的数环。 2. 剩余类环 。 为整数模 剩余类的集合 nZ nZ n ]}1[,],1[],0{[ −= nZn L 它对剩余类的加法和乘法构成一个含有单位元“[1]”的交换环。 3. 各式各样的数域都对通常的数的加法和乘法形成一个含有“1”的交换环。 4. 设 表示上面几个例子给出的任意一个数环。定义 F },|{][ 01 1 1 为正整数nFaaxaxaxaxF innnn ∈++++= −− L ，它是数域 上的一 元多项式环。 F 5. 取大于 1 的正整数n，则 的一切整数倍形成的集合 对数的加法和乘法形 成了一个不含单位元“1”的交换环。 n nZ 整环 定义（整环）：含有乘法单位元“1”而无零因子的交换环称为整环。 注： 1. 无零因子是指，由 可以推出0=⋅ba 0=a 或者 0=b 。反之，如果 ，则 ， 。否则，称 为左零因子，b为右零因子。 0=⋅ba 0≠a 0≠b a 2. 整环是类比于我们熟知的整数环，提取了整数环中的主要特征，例如乘法的 消去律。 3. 任何一个整环都至少含有 2 个元素。恰含有 2 个元素的整环是存在的，例如 它对模 2 的加法乘法运算形成一个整环，事实上，它为二元域。 }1,0{2 =F 定义（除环）：一个环被称为除环（或斜域），是指该环的非零元全体对“·” 形成一个群。 定义（域）：一个可交换的除环称为域。 注： 20 1. 为整数模pF p的剩余类环， p为素数，可以验证它为域。因为 中的元素 有限，称它为有限域；又因为 pF p为素数，又称之为素域。 2. 域首先必是整环；反之则不然。例如，整数环 Z ，域 上的多项式环 多 时整环，但它们都不是域。然而，对有限整环来说： F ][xF 定理 8：任意一个由有限个元素组成的整环R必定是有限域。 定理 9：在整环 R的加法群 +R 中，或者每个非零元素都生成一个无限阶的循 环群；或者存在一个素数 p， +R 中的每个元素都生成一个 p阶循环子群。 证明： R为整环，于是 R∈1 。 +R 作为 R的加法群含有由 1 生成的循环子群 }|1{1 Zkk ∈⋅=>< 1. 如果 为无限循环群： ><1 ,0, ≠∈∀ aRa 来证 也为无限循环群。若否，设 的阶为 ，于是： >< a a m amaaaaam mm ⋅⋅=⋅+++=+++=⋅= )1()111(0 4434421 L4434421 L 由于整环无零因子，必有 01=⋅m ，说明 ><1 为 的因子，与 为无限循 环群矛盾。所以 也为无限循环群。 m ><1 >< a 2. 如果 为有限循环群： ><1 首先断定 +R 元素 1 的阶必为某个素数 p 。事实上，如果假设 211 ppm ==>< ，其中 mpmp <<<< 21 1,1 。我们有： 01111)111()111()1)(1( 21 21 =⋅=+++=++++++=⋅⋅ mpp mpp 43421 L4434421 L4434421 L 由于整环无零因子，所以 11 ⋅p 和 12 ⋅p 这两者中必然有一个为 0，这与 m=><1 矛盾。所以 必为素数，设m pm = 为一个素数。 0, ≠∈∀ aRa ，有 0)1()111( =⋅=⋅+++=+++=⋅ apaaaaap pp 4434421 L4434421 L 说明 +R 中的每个非零元素都生成一个 p阶的循环子群，证毕。 21 注：当R为整环时，上述定理中的两种情况必有而且仅有一种成立。前一种 情况称整环 R 的特征为 0（ 0=Rchar ）；后一种情况称整环 R 的特征为 （ ）。易见，有限域作为特殊的整环，它的特征必定为 。 p pRchar = p 推论 1：F 为有限域，则 中的元素的个数F F 是其特征的方幂，即 npF = 。 推论 2：在一个特征为 的整环p R中，对任意自然数m有： mmm ppp baba +=+ )( ， ,mmm ppp baab =)( Rba ∈∀ , 推论 3：在一个特征为 的整环p R中，由等式 对某个自然数成立， 可以断定 。 mm pp ba = ba = 子环和环同构 定义（子环）：设 R是一个环， φ≠⊆ 11 .RRR ，如果 对1R R的运算“＋”和 “·”也形成一个环，称 为1R R的一个子环。 定义（环同构）：设 R和 R′是两个环。如果有一个保持加法和乘法运算的 1-1 映射到 R′之上，且 有： Rba ∈∀ , )()()( baba ϕϕϕ +=+ )()()( baab ϕϕϕ ⋅= 此时，称 R和 R′同构。 注：同构映射ϕ 把 R中的“0”元映射成为 R′中的“0”元；把 R中的“1” 元映射成为 R′中的“1”元；把 R中的子环映射成为 R′中的子环。 定理 10：任何一个特征为 0 的整环 R（或者域 ）都包含了一个整子环（子 域），它同构于整数环 F Z （有理数域 ）；任何一个特征为 的整环Q 0>p R（或者 域 ）都包含一个子整环同构于 。 F pF 22 注：由此定理知，整环或者域都包含有一个最小的整环（或者最小的域）做 它们的出发点。 下面讨论交换环R的商环。我们已经知道，对群G的一个正规子群H 来说， 可以给出商群 HGG /= ，这个商群以H 的各个陪集作为元素，使得 成为G 的一个缩影。如何把这个现象类比到商环呢？先从最具体的整数环 HG / Z 入手，设R 为整数环 Z ，它的子环： }|{1 ZkknnR ∈⋅>==< Zlm ∈∀ , ，称 模 同余，即lm, 1R )(mod 1Rlm ≡ ，相当于 lmn −| ，由数论的写法 。)(mod nlm ≡ R对 的商环就是： 1R ]}1[,],1[],0{[/ 1 −== nZRZ n L 我们已知在 的乘法为 ，它的意义是：nZ ][]][[ abba = ][],[ 21 brbara ∈+∀∈+∀ ，有： ][))((]][[ 211221 abrrbrarabrbraba =+++=++= ，相当于： 12112 Rnrrbrar =>∈<++ 这就诱导出一般交换环R中的理想子环的想法。 定义（理想）：交换环 R的一个子环 称为1R R中的一个理想子环（简称理想）， 如果 有 。 1, RrRa ∈∈∀ 1Rar∈ 注： 1. 设 是整环nbbb ,, 21 L R中的任意一组元素，则形如： Rabababar inn ∈∀+++= ,2211 L 的元素全体是 R中的理想 ，它称为由 这些元素生成的理想，记 为： 。 1R nbbb ,, ,21 L >< nbbb ,, ,21 L 特别，由单独一个元素 所生成的理想b >< b 被称为R中的一个主理想，由R 中的一切形如ab的元素组成， }|{ Raabb ∈>=< 。 2. 整数环 Z 中， Z 的任何一个子环都是一个理想；Z 的任何一个理想都是主理 23 想。原因是， +Z 是循环群， +Z 的任何一个子群也必然是循环群 。 nH 3. 域 上的多项式环 中，不一定每一个子环都是理想子环，例如，有理数 域上的一元多项式环 中，带整系数的那些多项式组成一个子环，但不是 理想。然而，可以证明多项式环 中的每一个理想都是主理想。 F ][xF ][xQ ][xF 定理 11：设 R是一个交换环， 是1R R的一个理想。如果将两个模 同余类 的和与积分别定义为同余类 1R ][],[ ba ][],[ abba + ，即： ][][][],[][][ abbababa =⋅+=+ 则由全部模 同余类所组成的集合1R 1/ RRR = 对上述运算构成环，称为 R对 的 商环。 1R 有限域 定义（子域，扩域）：设 E为一个域， 为F E中的一个非空子集。如果相对 于 E中的加法和乘法来说 是一个域，则称 为F F E的一个子域（或者基域），E 为 的一个扩域（或扩张）。 F 注： 1. 任何一个特征为 0 的域 E都包含一个子域 ，它同构于有理数域 ，任何一 个特征为 的域 F Q p E都包含了一个子域 ，它同构于素域 。易见，扩域F pF E对 E中的加法运算和 中的元素与F E中的元素的乘法运算形成 上的一个向 量空间。如果 F E作为 上的向量空间是 维的，则F n E被称为 的一个 次扩 张，否则 F n E称为 的无限次扩张。前者记为F nFE =]:[ ，后者记为 。 ∞=]:[ FE 2. 特征为 0 的域E可以视为由有理数域Q扩张而来；特征为 的域p E可视为由 素域 扩张而来。对于特征为 的域pF p E来说，若设E的乘法单位元为 ，则e 24 e的全体整倍元的集合为 pFopeepee ≅=− }|)1(,,2,{ L 。这就说明 E可视为由 扩张而来。若设 ，则存在 个元素pF nFE p =]:[ n )1( niui ≤≤ 使得E中任意元u 可以唯一的表示成为： pinn Fauauauau ∈+++= L2211 从而可知 npE = 定理 12（域扩张）:设 为任意域，而 F Fmmxmxmxxm id ddd ∈++++= −− ,)( 2211 L 为 上的一个 次不可约多项式，则同余类环F d ><= )(/ xmFE 可视为 上的一个 有限次扩域，并且有： F dFE =]:[ 。 证明：首先证明 为域。设><= )(/ xmFE ][)( xFxf ∈ ， ][)( xFxq ∈∀ 有： )()()( xfxmxq + 模 的同余类设为 ，知它是)(xm )]([ xf E 中的一个元素，若 ，知 =1，因此必有多项式]0[)( ∉xf ))(),(( xmxf ][)( xFxu ∈ ，使得： 1)()()()( =+ xmxvxfxu 于是有： ，或者说 。这说明 ]1[)]([)]([ =⋅ xfxu )]([)]([ 1 xuxf =− ><= )(/][ xmxFE 中的每个非零元素都有乘法逆元，所以它是一个域。下面证明 。 dFE =]:[ E中由零次多项式，亦即 中的元素所决定的那些模 同余类 组 成 F )(xm Fkk ∈],[ E中的一个子域F ；而映射 ][)( kk =σ 是 到F F 之上的一个同构映射。这样， 中的元素 的同余类 仍然为 ，把 决定的模 的同余类 记为F k ][k k x )(xm ][x α ，这 样一来 中的任意多项式 ][xF n nxaxaaxf +++= L10)]( 对应于 n n n n n n aaaxaxaaxaxaaxf αα +++=+++=+++= LLL 101010 ]][[]][[][][)]([ 25 )(αf= 特别，我们有 0)]([)( == xmm α ,于是借助于 上不可约多项式 所造出得扩域F )(xm E种，元素α ( )是 的一个零点。不仅如此，假如 上的另一个多项式 也以 ][x= )(xm F )(xl α 为零点，那么由 0)()]([ == αlxl ，可知有 。事实上， 有 )(|)( xlxm ][)( xFxf ∈∀ ),()()()( xrxmxqxf += 其中： 1 110)( − −+++= dd xrxrrxr