信息保障与安全05数论入门ppt课件

《信息保障与安全05数论入门ppt课件》由会员分享，可在线阅读，更多相关《信息保障与安全05数论入门ppt课件（74页珍藏版）》请在金锄头文库上搜索。

1、 数论入门数论入门 2024/7/19华中农业大学信息学院20 整数整数n整数：整数：n整数集整数集 , -3, -2, -1, 0, 1, 2, 3, 记为Z。n整除：整除：n设a, b为整整数数。假假设存存在在某某个个整整数数c, 使使得得b=ac, 那那么么称称a整整除除b等等价价地地，称称a是是b的的一一个个因因子子，或或者者说a为b的的一一个个因因子子。假假设a整数整数b，那么，那么记为 a | b 。n例如：例如：2024/7/19华中农业大学信息学院30 整数整数n整除的根本性质：整除的根本性质：n对对一一切切的的整整数数a，b，c，有有以以下下正正确确结结论：论：n a | a

2、n假设假设 a | b 且且 b | c ，那么，那么 a | c 。n假假设设 a | b 且且 a | c，那那么么对对于于一一切切的的整整数数x，y，有，有a |bx+cy。n假假设设 a | b 且且 b | a，那那么么 a = + b 或或 a = -b 。n例如例如 2024/7/19华中农业大学信息学院40 整数整数n整数的整除算法整数的整除算法n假假设设a，b均均为为整整数数，且且b=1, 那那么么按按照照a除除以以b的的普普通通长长除除法法可可以以找找到到整整数数q商商和和r余数，使得：余数，使得：a=qb+r，其中，其中0=r Ring Field域相关概念及定理n域的特

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

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

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)函数gcd(a, b)nint gcd(int a, int b)nnif (a=0) | (b=0)nreturn a+b;nelsenreturn gcd(a%b, b%a);n4.4 有限域GF(p)n域，无限域n有限域，又叫Galoris域n有限域的阶都有pn的方式n阶为p的有限域记为GF(p)n独一性 (Isomorphism)n在同构意义下，某阶有限域只需一个nGF(p)：(Zp, +, x)nGF(pm)

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

7、0，n得得tmn逆逆r1的逆的逆扩展Euclid算法举例n22 1 mod 31n311229-122 9 即即 3022 9 mod 31n2229422-2(3022) 4 即即 322 4 mod 31n 92413022-2(322) 1即即2422 1 mod 31n28 1 mod 75n7522819-22819 即即 732819 mod 75n28119928-1(7328)9 即即 328 9 mod 75n19291 (7328)-2(338)1 即即6728 1 mod75n269 1 mod 349n349126980 -126980 即即 -1269n2693802

8、9 269-3(-1269)29 即即 4269n 8022922 (-1269)-2(4269)22 即即 -9269n 291227 (4269)-1(-9269)7 即即 13269n 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 w

9、hile (r1);nif (r=0) return 0;nif (b 1是素数，当且是素数，当且仅当它只需因子当它只需因子1和和 p。n素数不能写作其它数的乘素数不能写作其它数的乘积 n1是素数，但普通是素数，但普通对它没它没兴趣趣 n例如：例如：2, 3, 5, 7是素数，是素数，4, 6, 8, 9, 10 不是素数不是素数n200以内的素数以内的素数: n2 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 149 151 157 163 16

10、7 173 179 181 191 193 197 199 素数的个数素因子分解素因子分解n算数根本定理：算数根本定理：n恣意整数恣意整数 a 1 都可以独一地因子分解都可以独一地因子分解为a = p1a1p2a2ptat ，其中，其中，pi 均是素数，且均是素数，且p1p20n如如. 91 = 7 x 13 ; 3600 = 24 x 32 x 52 n确定一个大数的素因子分解不是一件容易的事确定一个大数的素因子分解不是一件容易的事互素和最大公因子互素和最大公因子n两个数两个数 a, b 互素，假设它们没有除互素，假设它们没有除1以外的公因子以外的公因子 n如如 ( 8, 15 ) = 1

11、n最大公因子最大公因子n如如: 300 = 22 x 31 x 52 n 18 = 21 x 32 n 因此因此 GCD( 18, 300 ) = 21 x 31 x 50 = 62 Fermat定理和定理和Euler定理定理nap-1 1 ( mod p)np是素数，是素数，gcd( a, p ) = 1nFermat小定理小定理nap a (mod p)np是素数，是素数，a是恣意整数是恣意整数n在公在公钥钥密密码码中很有用中很有用Fermat 定理定理n小于小于n且与且与n互素的正整数的个数互素的正整数的个数 n如如 n = 10, n 0, 1, 2, 3, 4, 5, 6, 7, 8

12、, 9 ，1, 3, 7, 9 n (10) = 4n素数素数 p (p) = p-1 n素数素数p, q，有，有 (pq) = (p-1) x (q-1) n如：如：n(37) = 36n(21) = (31) x (71) = 2 x 6 = 12n商定：商定： (1) = 1Euler函数函数 (n)n定定 理：理：n设 n = p1e1 p2e2 prer，pi pj, pi为素数，素数，ei1,那么那么n(n) = n (1-p1-1) (1-p2-1)(1-pr-1)例如：例如：12 = 22 * 3 (12) = 12 * (1-2-1) * (1-3-1) = 4na(n) 1

13、 (mod n)n对对恣意恣意 a, n，gcd(a, n) = 1n另一种表示：另一种表示：na(n)+1 a (mod n)n对对恣意恣意 a, nn如：如：na = 3; n = 10; (10) = 4; n那么那么 34 = 81 1 mod 10na = 2; n = 11; (11) = 10;n那么那么 210 = 1024 1 mod 11nFermat定理是定理是Euler定理的推定理的推论论，或者，或者说说， Euler定理是定理是Fermat定理的更普通化方式。定理的更普通化方式。Euler 定定 理理n与与RSA有关的有关的结果果n两个素数两个素数 p 和和 q，整数

14、，整数m 和和 n，n = pq, 0 m 0, q 是奇数，使得是奇数，使得 (n1) = 2kqn 2. 随机随机选择整数整数 a, 1 a n1n 3. if aq mod n = 1 then 前往前往 (“不确定不确定);n 4. for j = 0 to k 1 don 5. if (a2jq mod n = n-1)n then 前往前往(“ 不确定不确定)n 6. return (“合数合数)概率方面的思索概率方面的思索n假假设Miller-Rabin测试前往前往 “合数，那么合数，那么该数一定不是素数；前往数一定不是素数；前往“不确定，那么不确定，那么该数数能能够是素数，也能

15、是素数，也能够是是伪素数素数n遇到遇到伪素数的概率素数的概率 0.999999素数的分布素数的分布n数论中的素数定理可知：数论中的素数定理可知：n附近的素数分布附近的素数分布情况为，平均每情况为，平均每 ln(n)个整数中有一个素数个整数中有一个素数n偶数和偶数和5的倍数，都不是素数，所以只需求的倍数，都不是素数，所以只需求测试测试 0.4ln(n)次次n如，要找如，要找2200左右的素数，那么约需左右的素数，那么约需55次测次测试试n这里只是平均意义上的结论这里只是平均意义上的结论n有时素数分布很密，有时很松有时素数分布很密，有时很松4 中国剩余定理中国剩余定理Chinese Remaind

16、er Theoremn用于加速模运算用于加速模运算 n某某一一范范围围内内的的整整数数可可经经过过它它对对两两两两互互素素的的整数取模所得的余数来重构整数取模所得的余数来重构 n使使得得非非常常大大的的数数对对M的的模模运运算算转转化化到到更更小小的数上来进展运算的数上来进展运算中国剩余定理中国剩余定理n可以多种方式实现可以多种方式实现CRTn计算计算 A(mod M)n首先依次计算一切首先依次计算一切 ai = A mod mi n确定常数确定常数 ci , 其中其中 Mi = M/min用以下式子得到结果用以下式子得到结果:中国剩余定理中国剩余定理除除数数mi余余数数ai最小公最小公倍数倍

17、数衍衍数数Mi = M/mi乘率乘率Mi-1ci各总各总ai ci答数答数m1a1M=m1m2mkM1M1-1m2a2M2M2-1mkakMkMk-1应应 用用 举举 例例n计 算：算：n120523 = 1651 * 73 = (973 + 678) * 73 ？ (mod 1813)n知知1813 = 37 * 49 且且37，49= 1nM = m1 * m2 = 37 * 49 (37, 49) = 1n973可用较小的两个模数可用较小的两个模数37和和49重构，表示为重构，表示为11，42n678可表示为可表示为12，41n那么那么1651 = 973 + 678就可表示为就可表示为

18、n 11 + 12 mod 37, 42 + 41 mod 49= (23, 34)n那么那么120523 = 1651 * 73就可表示为就可表示为n 23 * 73 mod 37, 34 * 73 mod 49= (14, 32)应应 用用 举举 例例运用举例运用举例n孙子算经：孙子算经：n今有物不知其数，三三数之剩二，五五数之剩今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？三，七七数之剩二，问物几何？n答曰二十三答曰二十三设所求物数所求物数为 X, 那么那么 X 2mod 3), X 3mod 5), X 2mod 7)n术曰：三三数剩一置几何？术曰：三三数剩一置几

19、何？n答曰：五乘七乘二得之一百四。答曰：五乘七乘二得之一百四。 n五五数剩一复置几何？五五数剩一复置几何？n答曰，三乘七得之二十一是也。答曰，三乘七得之二十一是也。 n七七数剩一又置几何？七七数剩一又置几何？n答曰，三乘五得之十五是也。答曰，三乘五得之十五是也。 n三乘五乘七，又得一百零五。三乘五乘七，又得一百零五。 n到了明代，数学家程大位用诗歌概括了这一算法到了明代，数学家程大位用诗歌概括了这一算法:n三人同行七十稀，五树梅花廿一枝，三人同行七十稀，五树梅花廿一枝， n七子聚会月正半，除百零五便得知。七子聚会月正半，除百零五便得知。 n这首诗的意思是：用这首诗的意思是：用3除所得的余数乘上

20、除所得的余数乘上70，加上用加上用5除所得余数乘以除所得余数乘以21，再加上用，再加上用7除所得的除所得的 余数乘上余数乘上15，结果大于，结果大于105就减去就减去105的倍数，这的倍数，这样就知道所求的数了。样就知道所求的数了。 中国剩余定理中国剩余定理除除数数mi余余数数ai最小公最小公倍数倍数衍衍数数Mi = M/mi乘率乘率Mi-1ci各总各总ai ci答数答数32M=3*5*7=1055*725*7*270*2140+63+30=23323 mod 105537*317*3*121*3723*513*5*115*25.1 本原根本原根5 离散离散对对数数Discrete Logar

21、ithms5.1 本原根本原根na(n)mod n = 1 nam = 1 (mod n), GCD(a, n) = 1n一定存在一定存在 ，由于，由于m = (n) ， (n) 是能是能够够的最高指数的最高指数 nm不一定最小不一定最小n一旦到达一旦到达m, 将会将会产产生循生循环环。n最小的最小的m，成，成为为a的的阶阶。n假假设设一个数一个数a的的阶为阶为(n)，那么称，那么称a为为n的本原根的本原根n假假设设p是素数是素数, a是是p的本原根，那么的本原根，那么na1, a2, a3, , ap-1 是模是模p各不一各不一样样的的 ；n并不是一切整数模并不是一切整数模n都有本原根。都有

22、本原根。n只需只需n是形是形为为2，4，p和和2 p的整数才有本原根，其中的整数才有本原根，其中p是奇素是奇素数，数， 是正整数。是正整数。n求求 x ，以满足，以满足 y = gx (mod p) n可以写作可以写作 x = logg y (mod p)n假设假设g是是p的本原根，那么的本原根，那么x一定存在；否一定存在；否那么，不一定存在那么，不一定存在, 例如例如.nx = log3 4 mod 13 无解无解 nx = log2 3 mod 13 = 4 n指数运算相对容易，求离散对数问题是困指数运算相对容易，求离散对数问题是困难的难的5.2 离散离散对对数数n定定义：n假假设m 1,

23、 (a, m) = 1, 那么使得同余式那么使得同余式 ai 1(mod m)n成立的最小正整数成立的最小正整数i，叫做，叫做a对模模m的离散的离散对数。数。n指数一定是欧拉函数的因子指数一定是欧拉函数的因子n对恣意整数恣意整数b和模数和模数p的本原根的本原根a，有独一的，有独一的幂i，使得，使得nb ai mod p, 其中其中0 i p-1n该指数指数i称称为以以a为底模底模p的离散的离散对数，数，记为 dloga, p(b)n离散离散对数不数不仅与模有关，而且与本原根有关。与模有关，而且与本原根有关。n例如：例如：n2对模模7的指数是的指数是3，对模模11的指数是的指数是10，所以，所以，2是模是模11的的一个本原根，而不是模一个本原根，而不是模7的本原根；的本原根；ndlog2, 9(8) = 3小小 结结q素数素数qFermat和和Euler定理定理q欧拉函数欧拉函数 (n) q素性素性测试Miller-Rabin算法算法q中国剩余定理中国剩余定理q离散离散对数数谢谢 谢谢 ！