1、第四章（2） 数论和有限域4.1 概念：整数性和除法 整除性：设a、b、m都是整数，如果a=mb，则说非零整数b整除a，用b|a表示b整除a，b是a的因子。* 如果b|g，b|h,对于任何整数m和n，则满足 b|(mg+nh). 除法： a=qn+r0;/rn qan 4.2 Euclid 算法 历史上第一个称得上算法的好像就是这个欧几里德算法，又叫“辗转相除法” 。 简单的描述就是，记gcd(a,b)表示整数a,b的最大公因数，那么：gcd(a,b) =maxk,其中k|a,且k|b= gcd(b,a%b) ，最大公因子必须是正数。0ab4欧几里得算法欧几里得算法56Example GCD(
2、1970,1066)1970 = 1 x 1066 + 904 gcd(1066, 904)1066 = 1 x 904 + 162 gcd(904, 162)904 = 5 x 162 + 94 gcd(162, 94)162 = 1 x 94 + 68 gcd(94, 68)94 = 1 x 68 + 26 gcd(68, 26)68 = 2 x 26 + 16 gcd(26, 16)26 = 1 x 16 + 10 gcd(16, 10)16 = 1 x 10 + 6 gcd(10, 6)10 = 1 x 6 + 4 gcd(6, 4)6 = 1 x 4 + 2 gcd(4, 2)4 =
3、 2 x 2 + 0 gcd(2, 0)因此gcd(1970,1066)=2 Euclidean Algorithm to compute GCD(a,b) is: EUCLID(a,b)1. A = a; B = b 2. if B = 0 return A = gcd(a, b) 3. R = A mod B 4. A = B 5. B = R 6. goto 2 4.3 模运算给定任意整数a和q，以q除a，余数是r，则可以表示为a=sq+r,0rq，其中s=a/q,表示小于a/q的最大整数。定义r为为a mod q的剩余的剩余，记为ra mod q. 若整数a和b有(a mod q)=(
4、b mod q)，则称a与与b在在mod q下下同余同余。 eg. 100 = 34 mod 11 eg. -12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7 性质性质1：若ab（mod n）看作a与b的二元关系，则它是一个等价关系，即满足：自反性自反性 a a（mod n）；对等性对等性 如果a mod n=b mod n，则ab（mod n）；对称性对称性 若ab（mod n），则ba（mod n）；传递性传递性 若ab（mod n）， bc（mod n），则ac（mod n）。对于某个固定模m的同余式可以象普通的等式那样相加、相减和相乘，可结合：(1)a(m
5、od m)b(mod m)mod m=(ab)(mod m)(2)a(mod m)*b(mod m)mod m=a*b(mod m)(3)(a*b)mod m+(a*c)mod m=a*(b+c)mod m幂运算采用重复乘法实现例子.通过同余式演算证明：（1）5601是56的倍数（2）2231是47的倍数。解： 注意53=12513(mod56) 于是有561691(mod56) 对同余式的两边同时升到10次幂， 即有56 560-1。同理, 注意到26=6417(mod47),于是223=(26)325=(26 26)26 25 289*(17)*(32) mod47 7*17*32 (mo
6、d47) 25*32(mod47) 1(mod47) 于是有 47 223-1定理：(消去律)对于abac（mod m）来说，若gcd(a,m)1则bc(mod m) 例如1：附加条件不满足的情况 63=182 mod 8 a=6 n=8 67=422 mod 8 但37 mod 8 例如2：附加条件满足的情况53157 mod 8 a=5 n=8 511=557 mod 8 311 mod 8原因：模原因：模m的乘法运算返回的结果是的乘法运算返回的结果是0到到m-1之间的数，如果乘数之间的数，如果乘数a和模数和模数m有除有除1以外的共同因子时将不会产生完整的余数集合。以外的共同因子时将不会产
7、生完整的余数集合。Z801234567乘以乘以606121824303642模模8后后的 余的 余数数06420642Z801234567乘 以乘 以505101520253035模模8后 的后 的余数余数05274163 乘法逆元乘法逆元 若ax=1 mod f 则称a关于模f的乘法逆元为x。也可表示为ax1(mod f)。例如：4关于模7的乘法逆元为多少？ 4*X1(mod 7) 这个方程等价于求一个X和K，满足 4X=7K+1 其中X和K都是整数。 (x=2.k=1) 例如：a =35, n=3, 求a关于模n 的乘法 反元素 a-1 ？a-1=2修改的欧几里德算法gcd(a,b)=gc
8、d(b,a mod b)gcd(18,12)=gcd(12,6)=gcd(6,0)=6gcd(11,10)=gcd(10,1)=gcd(1,0)=1修改的欧几里德算法gcd(a,b)=gcd(b,a mod b) P79扩展欧几里德定理 对于与不完全为 0 的非负整数 a，b，gcd（a,b）表示 a,b 的最大公约数。那么存在整数 x，y 使得 gcd（a,b）=ax+by。例如：gcd(42,30)=6,下图是42x+30y的部分值Xy-3-2-10123-3-216-174-132-90-48-636-2-186-144-102-60-182466-1-156-114-72-301254
9、960-126-84-42042841261-96-54-1230721141562-66-2418601021441863-3664890132174216图是图是42x+30y的部分值，最小正整数是的部分值，最小正整数是gcd(42,30)=6,112 1213 232111.0nn nnnnnaqb rbq rrrq rrrq rrrq r111222333.nnnraxbyraxbyraxbyraxby21222111iiiiiiiiiirrrqraxbyraxby通过移项可得：221121212121()()()(),;iiiiiiiiiiiyiiiiiiiiraxbyaxbyqa
10、xq xb yq xthenxxq xyyq y25补充了解补充了解：抽象代数抽象代数 代数学发展的代数学发展的4 4个阶段个阶段: : 1 1 文字叙述阶段文字叙述阶段 2 2 简化文字阶段简化文字阶段 3 3 符号代数阶段符号代数阶段 4 4 结构代数阶段结构代数阶段261.1 1.1 方法与对象方法与对象 1 1 文字叙述阶段文字叙述阶段 主要特点主要特点: : 直观推理直观推理 古代中国古代中国: : 筹算法筹算法 古代希腊古代希腊: : 几何数论几何数论27古代中国古代中国: : 筹算法筹算法 算筹计数算筹计数 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 6 7 8
11、 9 10 28古代希腊古代希腊: : 几何数论几何数论 1+3+5+1+3+5+(2n-1)=n+(2n-1)=n2 2. .292 2 简化文字阶段简化文字阶段 丢番图（丢番图（Diophantus,公元公元250年）年） 算术算术使用简化文字符号使用简化文字符号 12345678910： 平方：平方： ， （dunamis） 立方：立方： ， （kubos） x3+8x-1： * x: ; x3+8x: ; 减减: ;常数常数: *303 3 符号代数阶段符号代数阶段 字母表示数字母表示数 M.Stiefel(1486-1567)1553M.Stiefel(1486-1567)1553综
12、合算术综合算术 使用使用+ +、- -、 F.Viete(1540-1603)F.Viete(1540-1603) : : cubus aequalia a cubus+a plano2in b+b cubus aequalia a cubus+a plano2in b+b cubuscubus2222)(babababa 313 3 符号代数符号代数阶段阶段 符号代数的意义符号代数的意义 字母表示数：代数学不再停留在具体的字母表示数：代数学不再停留在具体的数字计算，有了真正意义的数学公式、数字计算，有了真正意义的数学公式、运算法则，并由此进化为现代数学符号运算法则，并由此进化为现代数学符号系
13、统、现代数学公理系统系统、现代数学公理系统 项武义：近代代数学的分界不在于项武义：近代代数学的分界不在于“字字母表示数母表示数”而是而是“不定元引入不定元引入”324 4 结构代数结构代数阶段阶段 结构代数：从公理系统出发研究特定的结构代数：从公理系统出发研究特定的代数系统，群、环、域等代数系统，群、环、域等 抽象代数是现代数学的基础抽象代数是现代数学的基础4.4 概念：群、环、域 群 环 域 高等教育出版社群(Group)的定义 设G是一个非空集合，并在G内定义了一种代数运算 “ 。”，若满足：Gba,A1: 封闭性。对任意，恒有GbaGcba,A2: 结合律。对任意，恒有cbacbaA3:
14、 G中存在一恒等元e,对任意Ga，使aaeeaA4: 对任意Gaeaaaa11，存在a的逆元Ga1，使A1-A4:群若加法，恒等元（又称单位元）用0表示; 若为乘法，恒等元称为单位元群可以记作群可以记作G, 。；注意：；注意： “ 。”里面是实心是实心 (A5) 交换律：对于G中的任意元素a和b,有 A1-A5:可交换群 循环群循环群 若由群G的一个生成元素g的幂次构成G群，即G=e，g，g2 ， gn则称G为循环群。元素g称为G的生成元素。 e=g0 n阶循环群中，g生成了群G，或者说g是群G的生成元。记做G=。 a b b a环(Ring)的定义 环R记为R, +, ;非空集合R中，若定义
15、了两种代数运算加和乘，且满足： (M1) 乘法的封闭性:如果a和b属于R，则ab属于R (M2) 乘法的结合率：对于R中的任意元素a,b,c，有a(bc)=(ab)c (M3) 分配律：对于R中的任意元素a,b,c，有a(b+c)=ab+ac和(a+b)c=ac+bc A1-M3:环 (M4) 乘法交换律:对于R中的任意元素a和b，ab=ba A1-M4:可交换环 域(Field)的定义 (M5) 乘法单位元：对于F中的任意元素a，在F中存在一个元素i,使得ai=ia=a (M6) 无零因子：对于F中的元素a,b，若ab=0，则有a=0或b=0 A1-M6：整环 (M7) 乘法逆元：如果a属于
16、F,且a不为0，则F中存在一个元素 , 全得 A1-M7：域 域F记为F, +, ;11()1aaa a1a4.5 有线域GF(p) 元素个数为p（p为有线域的阶）必须是一个素数的幂 ，n是正整数 GF(2n)域 ：又称伽罗华域。np阶为p的有线域 给定一个素数p，元素个数为p的有限域GF(p)定义为整数0,1,p-1的集合 ，其运算为模p的代数运算pZGF(7) Multiplication Example 0 1 2 3 4 5 60 0 0 0 0 0 0 01 0 1 2 3 4 5 62 0 2 4 6 1 3 53 0 3 6 2 5 1 44 0 4 1 5 2 6 35 0 5
17、 3 1 6 4 26 0 6 5 4 3 2 1对于一个数：对于一个数：n，n和其加法逆元和其加法逆元(或称相反数相反数)之和是加法单位（即零）。 对于n加法逆元表示为-n。 例：7的加法逆元是-7。-0.3的加法逆元是0.3。4.6 多项式运算Polynomial Arithmetic 多项式多项式 f(x)=fnxn+ fn-1xn-1+ f1x+f0piFf 其中i=0,1,n，该多项式称为域Zp上的多项式 多项式次数多项式次数 degf(x) 系数不为零的x的最高次数称为多项式f(x)的次数 首一多项式首一多项式 最高次数的系数为1的多项式普通多项式 eglet f(x) = x3
18、+ x2 + 2 and g(x) = x2 x + 1f(x) + g(x) = x3 + 2x2 x + 3f(x) g(x) = x3 + x + 1f(x) * g(x) = x5 + 3x2 2x + 2系数在Zp 多项式 例如模2，则所有系数 0 or 1 GF（2）中加法等价于XOR,乘法等价于逻辑与运算 eg. let f(x) = x3 + x2 and g(x) = x2 + x + 1f(x) + g(x) = x3 + x + 1f(x) x g(x) = x5 + x2求最大公因式 1、求多项式的最大公因式： （1）c(x)能同时整除a(x)和b(x) （2）a(x)
19、和b(x)的任何因式都是c(x)的因式 即：gcda(x)，b(x)能同时整除a(x)和b(x)的多项式中次数最高的一个。 2、gcda(x),b(x)=gcdb(x),a(x) mod b(x) 3、算法假设a(x)的次数大于b(x)的次数。 can write any polynomial in the form: f(x) = q(x) g(x) + r(x) can interpret r(x) as being a remainder r(x) = f(x) mod g(x) if have no remainder say g(x) divides f(x) if g(x) has
20、 no divisors other than itself & 1 say it is irreducible (or prime) polynomial计算：r2(x)=0,q2(x)=x+1,gcda(x),b(x)=r1(x)=x*3+x*2+1EUCLIDa(x), b(x)1. A(x) = a(x); B(x) = b(x)2. if B(x) = 0 return A(x) = gcda(x), b(x)3. R(x) = A(x) mod B(x)4. A(x)B(x)5. B(x) R(x)6. goto 24.7 有线域GF( )的多项式模运算2nf(x)=an-1xn-
21、1+ an-2xn-2+ a1x+a0 ai 在集合在集合0,1,.p-1共有共有pn 不同的多项式不同的多项式 如p=3 n=2时，共3*2=9 多项式 0 x 2x 1 x+1 2x+1 2 x+2 2x+2 如p=2 n=3时，共2*3=8 多项式 0 x+1 x*2 +x 1 x*2 x*2+x+1 x x*2+110niiiax GF(23) 中 (x2+1) is 1012 & (x2+x+1) is 1112 加法 (x2+1) + (x2+x+1) = x 101 XOR 111 = 0102 乘法 (x+1).(x2+1) = x.(x2+1) + 1.(x2+1) = x3
22、+x+x2+1 = x3+x2+x+1 011.101 = (101)1 XOR (101)0 = 1010 XOR 101 = 11112 除法 (get q(x) & r(x) is (x3+x2+x+1 ) mod (x3+x+1) = 1.(x3+x+1) + (x2) = x2 1111 mod 1011 = 1111 XOR 1011 = 01002 如果乘法运算的结果是次数大于n-1的多项式，那么必须将其除以某个次数为次数为n的既约多项式的既约多项式m(x)并取余式。既约多项式即只有1和其本身两个约数，又称不可约多项式Example GF(23)生成元与乘法逆元 生成元 可证明：
23、在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次方幂的形式，g称为GF(p)的生成元 逆元 生成元的例子 有限域GF（23），5是GF（23）的生成元 5 50 01 15 51 15 55 52 22 25 53 310105 54 44 45 55 520205 56 68 85 57 717175 58 816165 59 911115 510109 95 5111122225 5121218185 5131321215 5141413135 5151519195 516163 35 5171715155 518186 65 519197 75 52020
24、12125 5212114145 522221 1 AES（高级加密标准）使用有线域（高级加密标准）使用有线域GF(28)的运算，既约多项式m(x)= 假定为m(x)= 0的根 即是这个不可约多项式m(x)定义的有线域的生成元 下图说明GF(28)中的任意一个元素都可以表示成的幂8432184321 0 84321 类似继续推导 可以表示出00000000-11111111 思考： 计算3*7，和129*5 在该域内的数值？乘法逆元思考 把下图中所有的变量都看成函数， r(x),a(x),b(x)，q(x),x(x),y(x).etc.计算(x7+x+1)mod(x8+x4+x3+x+1)的乘法逆元，结果是x7作业 11-26收 4.6 4.15(a) 4.19(a) 4.25(b) 4.26 4.27作业题是
