《信息保障与安全》05-数论入门

1、. 数论入门数论入门 .2022-1-1华中农业大学信息学院2n整数：整数：q整数集整数集 , -3, -2, -1, 0, 1, 2, 3, 记为记为Z。n整除：整除：q设设a, b为整数。若存在某个整数为整数。若存在某个整数c, 使得使得b=ac, 则则称称a整除整除b（等价地，称（等价地，称a是是b的一个因子，或者的一个因子，或者说说a为为b的一个因子）。若的一个因子）。若a整数整数b，则记为，则记为 a | b 。n例如：例如：.2022-1-1华中农业大学信息学院3n整除的基本性质：整除的基本性质：q对所有的整数对所有的整数a，b，c，有以下正确结论：，有以下正确结论：q a | a

2、q若若 a | b 且且 b | c ，则，则 a | c 。q若若 a | b 且且 a | c，则对于所有的整数，则对于所有的整数x，y，有有a |（bx+cy）。）。q若若 a | b 且且 b | a，则，则 a = + b 或或 a = -b 。n例如例如 .2022-1-1华中农业大学信息学院4n整数的整除算法整数的整除算法q若若a，b均为整数，且均为整数，且b=1, 则按照则按照a除以除以b的普的普通长除法可以找到整数通长除法可以找到整数q（商）和（商）和r余数，使余数，使得：得：a=qb+r，其中，其中0=r Ring Field.域相关概念及定理n域的特征 - 任意元素a的n

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

4、a mod b)n求最大公因子辗转相除法（欧几里德算法）gcd(a, b) = gcd(b%a, a%b).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 26 + 16 gcd(26, 16)26 = 1 x 16 + 10 gcd(16, 10)16 = 1 x 10 + 6 gc

5、d(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(a, b)nint gcd(int a, int b)nnif (a=0) | (b=0)nreturn a+b;nelsenreturn gcd(a%b, b%a);n.4.4 有限域GF(p)n域，无限域n有限域，又叫Galoris域有限域的阶都有pn的形式阶为p的有限域记为GF(p)n唯一性 (Isomorphism)q在同构意义下，某阶有限域只有一个nGF(p)：(Zp, +, x)GF(pm)：q系数在Zp上的模某不

6、可约多项式的多项式域GF(2n)：p=2.GF(p)：(Zp, +, x)n逆元q由于p是素数，所以除了0外都有逆元nGF(p=2)：(Z2, +, x)GF(p=7)：(Z7, +, x)* GF(p=8)：(Z8, +, x)不是域.求逆元：扩展Euclid算法n扩展扩展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逆逆 r1的逆的逆

7、.扩展Euclid算法举例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(338)1 即6728 1 mod75n269 1 mod 349349126980 -126980 即 -126926938029 269-3(-1269)29 即 4269 802292

8、2 (-1269)-2(4269)22 即 -9269 291227 (4269)-1(-9269)7 即 13269 22371 (-9269)-3(13269)1即-48269 得301.函数reverse()nint reverse(int a, int m)nint b, b1=1, b2=0; / 逆元nint r, r1=a, r2=m; /ndo r = r2 % r1; / y-kx = rnb = (b2-(r2/r1)*b1)%m;nr2 = r1;b2 = b1;nr1 = r;b1 = b;n while (r1);nif (r=0) return 0;nif (b 1

9、是素数，当且仅当它只有因子是素数，当且仅当它只有因子1和和 p。q素数不能写作其它数的乘积素数不能写作其它数的乘积 q1是素数，但一般对它没兴趣是素数，但一般对它没兴趣 n例如：例如：2, 3, 5, 7是素数，是素数，4, 6, 8, 9, 10 不是素数不是素数n200以内的素数以内的素数: 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

10、199 2022-1-1.442022-1-1.4520004000600080001000020040060080010001200素数的个数2022-1-1.46素因子分解素因子分解n算数基本定理：算数基本定理：任意整数任意整数 a 1 都可以唯一地因子分解为都可以唯一地因子分解为a = p1a1p2a2ptat ，其中，其中，pi 均是素数，且均是素数，且p1p20q如如. 91 = 7 x 13 ; 3600 = 24 x 32 x 52 2022-1-1.47互素和最大公因子互素和最大公因子n两个数两个数 a, b 互素，如果它们没有除互素，如果它们没有除1以外的公因子以外的公因子

11、q如如 ( 8, 15 ) = 1 n最大公因子最大公因子q如如: 300 = 22 x 31 x 52 18 = 21 x 32 因此因此 GCD( 18, 300 ) = 21 x 31 x 50 = 62022-1-1.482 Fermat定理和定理和Euler定理定理nap-1 1 ( mod p)qp是素数，是素数，gcd( a, p ) = 1nFermat小定理小定理qap a (mod p)qp是素数，是素数，a是任意整数是任意整数2022-1-1.49n小于小于n且与且与n互素的正整数的个数互素的正整数的个数 如如 n = 10, 0, 1, 2, 3, 4, 5, 6, 7

12、, 8, 9 ，1, 3, 7, 9 (10) = 4n素数素数 p (p) = p-1 n素数素数p, q，有，有 (pq) = (p-1) x (q-1) n如：如：(37) = 36(21) = (31) x (71) = 2 x 6 = 12n约定：约定： (1) = 12022-1-1.50n定定 理：理：设设 n = p1e1 p2e2 prer，pi pj, pi为素数，为素数，ei1,则则(n) = n (1-p1-1) (1-p2-1)(1-pr-1)例如：例如：12 = 2 * 3 2022-1-1.512022-1-1.52na(n) 1 (mod n)对任意对任意 a,

13、 n，gcd(a, n) = 1n另一种表示：另一种表示：a(n)+1 a (mod n)对任意对任意 a, nn如：如：a = 3; n = 10; (10) = 4; 则则 34 = 81 1 mod 10a = 2; n = 11; (11) = 10;则则 210 = 1024 1 mod 11nFermat定理是定理是Euler定理的推论，或者说，定理的推论，或者说， Euler定理是定理是Fermat定理的更一般化形式。定理的更一般化形式。2022-1-1.53n与与RSA有关的结果有关的结果q两个素数两个素数 p 和和 q，整数，整数m 和和 n，n = pq, 0 m 0, q

14、 是奇数，使得是奇数，使得 (n1) = 2kq 2. 随机选择整数随机选择整数 a, 1 a n1 3. if aq mod n = 1 then 返回返回 (“不确定不确定); 4. for j = 0 to k 1 do 5. if (a2jq mod n = n-1) then 返回返回(“ 不确定不确定) 6. return (“合数合数)2022-1-1.56概率方面的考虑概率方面的考虑n如果如果Miller-Rabin测试返回测试返回 “合数合数”，则该数，则该数一定不是素数；返回一定不是素数；返回“不确定不确定”，则该数可，则该数可能是素数，也可能是伪素数能是素数，也可能是伪素数n遇到伪素数的概率遇到伪素数的概率 1, (a, m) = 1, 则使得同余式则使得同余式 ai 1(mod m)成立的最小正整数成立的最小正整数i，叫做，叫做a对模对模m的离散对数。的离散对数。n指数一定是欧拉函数的因子指数一定是欧拉函数的因子n对任意整数对任意整数b和模数和模数p的本原根的本原根a，有唯一的幂，有唯一的幂i，使得，使得b ai mod p, 其中其中0 i p-1该指数该指数i称为以称为以a为底模为底模p的离散对数，记为的离散对数，记为 dloga, p(b)n离散对数不仅与模有关，而且与本原根有关。离散对数不仅与模有关，而且与本原根有关。n