数论相关基础知识课件.ppt

1、B数论相关基础知识B提纲 群环域 模运算 欧几里德算法 有限域GF(p) 多项式运算 有限域GF(2n)BAbstract AlgebraAlgebraic structure Semigroupclosure封闭性, associative 结合律 Groupclosure, associativity, identity单位元, inverse逆元 Ring+: associativity, commutativity交换律, identity, inverse 0*: associativity, distributivity分配律 Fielda ringmultiplicative i

2、nverse 乘法逆元 Lattice, BooleanB4.1 群环域 群 Group 集合，元素 二元运算 封闭性、结合律 单位元、逆元 有限群、无限群 交换群（Abel） 循环群 生成元B环 Ring 环R 二元运算: 加法+、乘法 (R, +)是交换群 乘法封闭性、乘法结合律 分配律 a(b+c) = ab+ac 交换环 乘法交换律 整环（交换环且） 乘法单位元1 无零因子: ab=0 a=0或b=0B域 Field 域F F是整环 存在乘法逆元(0除外) 除法定义: a/b = a(b-1) 有理数域、实数域、复数域 有限域BGroup Ring FieldB域相关概念及定理 域的特

3、征 - 任意元素a的n次累计和为0的最小的n；域的特征要么是素数，要么是0(没有)； 素域：没有非0真子域的域； 有限域的阶是pn（其中p是素数）； 有限域的乘法群是循环群；B可逆在加/解密中的重要性 加密的操作对象是比特分组，通常被看作整数加密是对整数的变换。这种变换必须能恢复(解密时)，即可逆。如果加密是乘法，则解密就是除法，而域上正好有除法-乘法逆元。 对于8bits字节，希望Z256是域，但它不是；于是转而寻求GF(28)，它是域。 AES的S盒是基于模2系数的模某8次不可约多项式的剩余类。B4.2 模运算 模运算即求余数（C语言中的运算符）x mod na其中0ab)gcd(a, b

4、) = gcd(b, a mod b) 求最大公因子辗转相除法（欧几里德算法）gcd(a, b) = gcd(b%a, a%b)BGCD(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

5、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)B函数gcd(a, b) int gcd(int a, int b) if (a=0) | (b=0)return a+b;elsereturn gcd(a%b, b%a); B4.4 有限域GF(p) 域，无限域 有限域，又叫Galoris域有限域的阶都有pn的形式阶为p的有限域记为GF(p) 唯一性 (Isomorphism) 在同构意义下，某阶有限域只有一个 GF(p)：(Zp, +, x)GF(pm)： 系数在

6、Zp上的模某不可约多项式的多项式域GF(2n)：p=2BGF(p)：(Zp, +, x) 逆元 由于p是素数，所以除了0外都有逆元 GF(p=2)：(Z2, +, x)GF(p=7)：(Z7, +, x)* GF(p=8)：(Z8, +, x)不是域B求逆元：扩展Euclid算法 扩展扩展Euclid算法算法做欧几里德算法的计算序列做欧几里德算法的计算序列r0q1r1r2 (令令r0n，r1a)r1q2r2r3r2q3r3r4rm-2qm-1rm-1rm (1)rm-1qmrm rm+1 (0)记记 t0 rm+1，t1rm，依依 tjtj-2 qi-1 tj-1 mod r0，得得 tm逆逆

7、 r1的逆的逆B扩展Euclid算法举例 22 1 mod 31311229-122 9 即 3022 9 mod 312229422-2(3022) 4 即 322 4 mod 31 92413022-2(322) 1即2422 1 mod 31 28 1 mod 757522819-22819 即 732819 mod 7528119928-1(7328)9 即 328 9 mod 7519291 (7328)-2(338)1 即6728 1 mod75 269 1 mod 349349126980 -126980 即 -126926938029 269-3(-1269)29 即 4269

8、 8022922 (-1269)-2(4269)22 即 -9269 291227 (4269)-1(-9269)7 即 13269 22371 (-9269)-3(13269)1即-48269 得301B函数reverse() int reverse(int a, int m) int b, b1=1, b2=0; / 逆元int r, r1=a, r2=m; /do r = r2 % r1; / y-kx = rb = (b2-(r2/r1)*b1)%m;r2 = r1;b2 = b1;r1 = r;b1 = b; while (r1);if (r=0) return 0;if (b0)

9、b += m;return b; B4.5 多项式运算 多项式 一元n次整数域 多项式运算 加，减 乘例子：f(x) = x3 + x2 + 2，g(x) = x2 - x + 1f(x) + g(x) = x3 + 2x2 - x + 3f(x) g(x) = x3 + x + 1f(x) x g(x) = x5 + 3x2 - 2x + 2B- 除法: f(x)/g(x)=q(x) r(x) 整除，若r(x)=0 模g(x)同余 f(x) = q(x) g(x) + r(x) f(x) r(x) mod g(x) 不可约多项式(素多项式,既约多项式) g(x)不能表示为另两个多项式的乘积

10、关于系数Zn的多项式B多项式环 系数是域F的多项式，构成环 系数是Zn的多项式环 系数是Zp的多项式环 在Z2上的多项式环，在计算机上操作时有优势 加法，即XOR 乘法，即AND 构造GF(pn) 从环到域B构造GF(pn) 系数在Zp上的n-1次多项式f(x)集合S 共有pn个 (S,)构成有限域GF(pn) 需要某n次不可约多项式m(x)使用模m(x)的多项式加法和乘法 从GF(pn)到GF(2n) 到GF(28) in AESBExample GF(23)B- B4.6 有限域GF(2n) 系数模2，即只可0或1若次数最高7次，共28=256个多项式(剩余类) 加法 XOR 乘法 移位，

11、加法/XOR 乘法逆元(除法) 扩展Euclid算法BGF(23)上的运算（in AES） m(x) = x8 + x4 + x3 + x + 1 运算表：8x8 AES BTerms abelian groupassociativecoefficient set commutativecommutative ringcyclic group divisorEuclidean algorithm field finite groupfinite ringfinite field generatorgreatest common divisor groupidentity element inf

12、inite groupinfinite ringinfinite field integral domaininverse elementirreducible polynomial modular arithmeticmodular polynomial arithmetic modulo operator modulusmonic polynomial orderpolynomialpolynomial arithmetic polynomial ringprime numberprime polynomial relatively primeresidueringB小结 域结构在密码学上有重要应用。另外，格结构也越来越表现出重要用途。BQ & A