1、1p模运算p欧几里得算法p群、环、域p有限域G(p)p多项式运算p有限域G(2n)2模运算3模运算 以模8运算为例4模运算 模运算的规律5模运算交换律结合律分配律恒等式加法逆元 正整数c称为a和b 的最大公因子最大公因子，如果 c 是a和b的因子， a和b 的任何因子都是c 的因子。 记为c=gcd(a,b)；等价定义 gcd(a,b)= maxk: k|a k|b 定理：设a, b, r是三个不全为0 的整数，如果a =bq + r ，其中q为整数，则gcd(a, b) = gcd(b, r) Euclidean算法：计算gcd(a, b)6模运算7欧几里得算法gcd(a, b) = gcd
2、(b, r1)gcd(b, r1) = gcd(r1, r2)gcd(r1, r2) = gcd(r2, r3)gcd(rn-2, rn-1) = gcd(rn-1, rn)gcd(rn-1, rn) = gcd(rn, 0)=rn8求GCD(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 2
3、6 + 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 = 2 x 2 + 0 gcd(2, 0)欧几里得算法求GCD(5754,3014)9欧几里得算法计算计算GCD(a,b)的欧几里得算法的欧几里得算法: 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、 10扩展的欧几里得算法11扩展的欧几里得算法12扩展的欧几里得算法代数系统代数系统一个一个非空集合非空集合A连同连同若干个定义在该集若干个定义在该集合上的运算合上的运算f1,f2,fk所组成的系统就称为一个所组成的系统就称为一个代代数系统数系统，记作，记作。运算封闭运算封闭 设*是定义在集合A上的二元运算上的二元运算，如果 对于任意的x,yA,都有x*yA,则称二元运算*在A上是封闭的。13运算可交换运算可交换 设*是定义在集合A上的二元运算上的二元运算，如果对于任意的x,yA都有x*y=y*x,则称该二元运算*是可交换的，或运算满足交换律。运算可结合运算可结合 设*是定义在集合A上的二元运
5、算上的二元运算，如果对于任意的x,y,zA都有(x*y)*z=x*(y*z),则称该二元运算*是可结合的，或运算满足结合律。14运算可分配运算可分配 设*，是定义在集合A上的两个二元运算上的两个二元运算，如果对于任意的x,y,zA都有 x*(yz)=(x*y)(x*z) (yz)*x=(y*x)(z*x)则称运算*对于运算是可分配的。幺元幺元对于任一对于任一xA,有有e* *x=x* *e=x。零元零元对于任一对于任一xA,有有* *x=x* *=。逆元逆元对于对于xA,有有y* *x=x* *y=e，x,y互为逆元。互为逆元。15p群群 Group,定义了二元运算的集合，记为G, *，遵循:
6、 封闭性：a,b属于G，则a*b属于G 结合律: (a*b)*c = a*(b*c) 单位元 e:e*a = a*e = a 逆元 a-1:a*a-1 = ep 有限群、无限群p 群的性质：无零元（只有一个等幂元）、满足消去律、a*x=b解唯一p 如果满足交换律a*b = b*a 则构成阿贝尔群(abelian group)16p 定义求幂运算求幂运算为重复运用群中的运算p 如: a3 = a*a*ap 定义: e=a0p 称一个群为循环群循环群，如果：群中每个元素都是一个固定元素a的幂，即p b = ak（for some a and every b in group）p a 称为群的一个生
7、成元生成元（generator）17p 当考虑两种运算时：加法+ 和 乘法p加法的逆元加法的逆元又称为又称为负元负元，a关于加法的逆元（负元）关于加法的逆元（负元）记为记为- ab+(-a)(c+(-b)可可简化为：简化为：b-a(c-b)自然而然第引入了减法（条件：每个元素的自然而然第引入了减法（条件：每个元素的负元负元存在）存在）18p环环p Ring ，一个集合，一个集合 ,记为记为R,，X，定义，定义了两种运算了两种运算 (加法加法和乘法和乘法): 对加法，构成阿贝尔群对加法，构成阿贝尔群 对乘法满足对乘法满足: 封闭性 结合律: a(bc) = (ab)c 分配律: a(b+c) =
8、 ab + acp 如果乘法满足交换律，则称如果乘法满足交换律，则称交换环交换环commutative ring p 如果乘法如果乘法有有单位元单位元、满足交换律满足交换律且且无零因子无零因子，则称，则称整环整环integral domain 零因子：Z6中的2和319p 环的性质：（环的性质：（ 为加法幺元）为加法幺元） a = a = （加法幺元必为乘法零元）（加法幺元必为乘法零元） a(-b) =(-a) b = -(ab) (-a) (-b) = ab a(b-c) = ab - ac (b-c) a =ba -ca （减法分配率）（减法分配率） 无无零因子等价于乘法满足消去律零因子等
9、价于乘法满足消去律2021环举例环举例 整数集、有理数集、实数集和复数集关于普通的加法整数集、有理数集、实数集和复数集关于普通的加法和和乘法乘法构成环，分别称为构成环，分别称为整数环整数环Z，有理数环有理数环Q，实数环实数环R和和复数环复数环C. n(n2)阶实矩阵的集合阶实矩阵的集合Mn(R)关于矩阵的加法和乘法关于矩阵的加法和乘法构构 成环，称为成环，称为 n 阶实矩阵环阶实矩阵环. 集合的幂集集合的幂集P P (B)关于集合的对称差运算和交运算构成关于集合的对称差运算和交运算构成环环. 设设Zn0,1, . , n1， 和和 分别表示模分别表示模n的加法和的加法和乘乘 法，则法，则构成环
10、，称为构成环，称为模模 n的整数环的整数环. 系数属于实数的所有系数属于实数的所有x的多项式所组成的集合记作的多项式所组成的集合记作Rx，那么，那么，Rx关于多项式的加法和乘法关于多项式的加法和乘法构成构成多项式环多项式环。p域域p Field， 集合集合 ，记为，记为F,，Xp 两种运算两种运算: 对加法，构成阿贝尔群 对乘法，构成阿贝尔群（除0外） 环p 域比环增加的条件：域比环增加的条件： 乘法满足交换律 乘法幺元存在 除零元外，乘法逆元都存在p 作作加、减、乘和除法（除加、减、乘和除法（除0外）运算，结果仍在集合外）运算，结果仍在集合中中p 有限整环必是域有限整环必是域222324域域
11、的的特征特征p：最小的正整数p，使得p1=0,1为的逆元，0为的逆元；如果p不存在，特征为0。 Q、R、C特征为0； 域的特征只能为0或素数 特征暗示了加法的循环性定理定理：有限域的元素个数必是其特征的幂。 对于1F，考虑0， 1 ，1 ，21 ， (p-1)1 以上元素互不相同，可能F=0， 1 ，1 ，21 ， (p-1)1 若不是，考虑其他元素2F；考虑任意a1 1 +a2 2，系数为0至p-125262728扩展的欧几里得算法EXTENDED EUCLID(a, b)1.(A1, A2, A3)=(1, 0, a); (B1, B2, B3)=(0, 1, b)2. if B3 = 0
12、return A3 = gcd(a, b); no inverse3. if B3 = 1 return B3 = gcd(a, b); B2 = b1 mod a4. Q = A3 div B35. (T1, T2, T3)=(A1 QB1, A2 QB2, A3 QB3)6. (A1, A2, A3)=(B1, B2, B3)7. (B1, B2, B3)=(T1, T2, T3)8. goto 229利用扩展的欧几里得算法扩展的欧几里得算法求乘法逆元乘法逆元30利用扩展的欧几里得算法扩展的欧几里得算法求乘法逆元乘法逆元求GF(1759)中550的乘法逆元31利用扩展的欧几里得算法扩展的欧
13、几里得算法求乘法逆元乘法逆元n22 1 mod 31311229-122 9 即 3022 9 mod 312229422-2(3022) 4 即 322 4 mod 31 92413022-2(322) 1 即 2422 1 mod 31n28 1 mod 757522819-22819即 732819 mod 7528119928-1(7328)9即 328 9 mod 7519291(7328)-2(328)1 即6728 1 mod 75n269 1 mod 349349126980 -126980 即 -126926938029 269-3(-1269)29 即 4269 80229
14、22 (-1269)-2(4269)22 即 -9269 291227 (4269)-1(-9269)7 即 13269 22371 (-9269)-3(13269)1 即-48269 得 30132nn次多项式次多项式f(x) = anxn + an-1xn-1 + + a1x + a0 = aixinai组成的集合称为系数集n讨论三种多项式运算q使用代数基本规则的普通多项式运算q系数运算是模p运算的多项式运算，即系数在Zp中q系数在Zp中，且多项式被定义为模一个n次多项式m(x)的多项式运算33p普通多项式运算p对应系数相加减（，）p系数依次相乘（）p如p f(x) = x3 + x2 +
15、 2 ， g(x) = x2 x + 1pf(x) + g(x) = x3 + 2x2 x + 3pf(x) g(x) = x3 + x + 1pf(x) x g(x) = x5 + 3x2 2x + 2p注意：定义在整数集上的多项式不支持除法运算，整数集不是域34p系数在模Zp中的中的多项式运算p系数是域F的元素时，构成多项式环（不构成整环，因为有可能有零因子）p系数是Zp的元素的多项式p最感兴趣的是mod 2p所有系数是0 或 1p例如：f(x) = x3 + x2 和 g(x) = x2 + x + 1pf(x) + g(x) = x3 + x + 1pf(x) x g(x) = x5
16、+ x235p多项式的因式p对于任何多项式:pf(x) = q(x) g(x) + r(x)pr(x) 称为余式pr(x) = f(x) mod g(x)p若没有余式，则称g(x)整除f(x)p不可约（既约）多项式，也叫素多项式。p用一个不可约多项式作为模，则可构成一个域（可以定义除法了）36p多项式的最大公因式pc(x) = GCD(a(x), b(x) ，如果c(x) 是能够同时整除a(x), b(x) 的多项式中次数最高的一个p欧几里得算法:pEUCLIDa(x), b(x)p1. A(x) = a(x); B(x) = b(x)p2. if B(x) = 0 return A(x) =
17、 gcda(x), b(x)p3. R(x) = A(x) mod B(x)p4. A(x) B(x)p5. B(x) R(x)p6. goto 237p多项式模运算p在GF(2n) 中p系数是mod2的多项式p次数低于np可用n次素多项式去素多项式去模约以降次p构成一个有限域p非零元总有逆元p可用扩展的欧几里得算法计算38pExample GF(23)39p计算上的考虑p因为系数是0或1, 所以可以用一个比特串来表示任何多项式p加法：比特串的逐位XORp乘法：移位和XOR40pExample GF(23)p(x2+1) 表示为1012 ，(x2+x+1) 表示为1112p加法p(x2+1)
18、+ (x2+x+1) = x p101 XOR 111 = 0102p乘法p(x+1).(x2+1) = x.(x2+1) + 1.(x2+1) p= x3+x+x2+1 = x3+x2+x+1 p 011.101 = (101)1 XOR (101)0 = p1010 XOR 101 = 11112 p多项式模运算p (x3+x2+x+1 ) mod (x3+x+1) = 1.(x3+x+1) + (x2) = x2p 1111 mod 1011 = 1111 XOR 1011 = 0100241p生成元生成元p 有限域有限域的一种定义的一种定义p 生成元生成元gp在域F中有0, g0, g1, , gq-2p 用不可约多项式的用不可约多项式的根根可以产生生成元可以产生生成元p 生成元的指数相加，就可定义乘法运算生成元的指数相加，就可定义乘法运算42整除和模如果a =bq + r ，则gcd(a, b) = gcd(b, r)欧几里得算法代数结构群环域有限域Fp多项式运算一般运算Fp上的运算Fp上的运算，模不可约多项式F(2n)
