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

资源描述

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

1、数论入门啤蚕诡透嘻泅钮琳美豢其泣歇旋渍吻绿佐盯隧稠党滥物馒谨晚勿俩谁版罕信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 2 0 0 整数整数 n整数： 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例如：繁漏蚕客赏圭泼

3、颇册胰僻捂绰侧太惑椎痰绒厌瘫童裔诵萎豌敝艇基酗裴善窘信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 4 0 0 整数整数 n整数的整除算法 q若a，b均为整数，且b=1, 则按照a除以b的普通长除法可以找到整数q（商）和r余数，使得：a=qb+r，其中0 Ring Field 锥儒滇侄僻疟狡倍兴鸿酥吉斤殷肢雨磺哑体载拜变吞丈烃辞疹踩匝考楔核信息保障与安全 0 5 -

4、数论入门 L e c t u r e O v e r h e a d s 域相关概念及定理 n域的特征 - 任意元素a的n次累计和为0的最小的n；域的特征要么是素数，要么是0(没有)； n素域：没有非0真子域的域； n有限域的阶是pn（其中p是素数）； n有限域的乘法群是循环群；疯憎戚抹裴危呢爵邮尔资阉角贸沮西控凝脾姚盲腋菠钥断磕约洛运漂毒跳信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s 可逆在加/解密中的重要性 n加密的操作对象是比特分组，通常被看

5、作整数加密是对整数的变换。这种变换必须能恢复( 解密时)，即可逆。如果加密是乘法，则解密就是除法，而域上正好有除法-乘法逆元。 n对于8bits字节，希望Z256是域，但它不是；于是转而寻求GF(28)，它是域。 nAES的S盒是基于模2系数的模某8次不可约多项式的剩余类。责慎裁襟谦铭蓉烤寞彬概癌奠搏零颖鉴降奎红堆须醒纯补散获桃颜虾坏硫信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s 4.2 模运算 n模运算即求余数（C语言中的运算符） x mod n

6、a 其中0ab) gcd(a, b) = gcd(b, a mod b) n求最大公因子辗转相除法（欧几里德算法） gcd(a, b) = gcd(b%a, a%b) 芥鹏钝隐悼挣铰恭兔义泵囱缆澳糯篙姜寞液掣麦崔阜嘶筐瘪汽邀散秒韧流信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s GCD(1970,1066) 1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904

7、= 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 = 2 x 2 + 0 gcd(2, 0) 椿贫舀柑慧函核及舒走仿趁涸酿匣绳敛坯怂辆日迄提瘫炭大苗顽

8、凡准颇恕信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s 函数gcd(a, b) nint gcd(int a, int b) n nif (a=0) | (b=0) nreturn a+b; nelse nreturn gcd(a%b, b%a); n 追通耘玫歼弛袭手蚜堤惰尼领拖矛畏又炙舟壕仰祁虱芝徘碌沟训违瑟漱捅信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s 4.4 有限域G

9、F(p) n域，无限域 n有限域，又叫Galoris域有限域的阶都有pn的形式阶为p的有限域记为GF(p) n唯一性 (Isomorphism) q在同构意义下，某阶有限域只有一个 nGF(p)：(Zp, +, x) GF(pm)： q系数在Zp上的模某不可约多项式的多项式域 GF(2n)：p=2 燥投烦鹊差筛粪敖厌支视斑替条装署杜灶垮铱细登秦抱绷蝴班哪学乃娩辊信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s GF(p)：(Zp, +, x) n逆元 q由于

10、p是素数，所以除了0外都有逆元 nGF(p=2)：(Z2, +, x) GF(p=7)：(Z7, +, x) * GF(p=8)：(Z8, +, x)不是域蛾畴尾袁演磺控铂誊臆遭严矣捉钙学胺喉姆拣镰的开锥茁万屹资仲远坟陨信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s 求逆元：扩展Euclid算法 n扩展Euclid算法做欧几里德算法的计算序列 r0q1r1r2 (令r0n，r1a) r1q2r2r3 r2q3r3r4 rm-2qm-1rm-1rm (1)

11、rm-1qmrm rm+1 (0) 记 t0 rm+1，t1rm，依 tjtj-2 qi-1 tj-1 mod r0，得 tm 逆 r1的逆械蜡焦韧饥逢剖撮畦硷墅盖宏姻绩蜀贯票田渔位棚莱有茂松骇橡座诱冷陡信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s 扩展Euclid算法举例 n22 1 mod 31 311229-122 9 即 3022 9 mod 31 2229422-2(3022) 4 即 322 4 mod 31 92413022-2(322)

12、 1即2422 1 mod 31 n28 1 mod 75 7522819-22819 即 732819 mod 75 28119928-1(7328)9 即 328 9 mod 75 19291 (7328)-2(338)1 即6728 1 mod75 n269 1 mod 349 349126980 -126980 即 -1269 26938029 269-3(-1269)29 即 4269 8022922 (-1269)-2(4269)22 即 -9269 291227 (4269)-1(-9269)7 即 13269 22371 (-9269)-3(13269)1即-48269 得30

13、1 玖企吟蹭易衬聊哎勇蜡蓝前藻枫樟饯醇娄散芍雏凄着磊嘴圣件循纹之吐涎信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s 函数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 = r nb = (b2-(r2/r1)*b1)%m; nr2 = r1;b2 = b1; nr1 = r;b1 = b; n

14、while (r1); nif (r=0) return 0; nif (b 1是素数，当且仅当它只有因子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 199 端暂解鹰

15、微矛祝哪琼搞姿羽柏邵窑酱掷雅虐播弃晾醚褒扳涉虾相痞社焙峰信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 44 始掇番讶伟丹痹鞠七券抠棱虐形沤盎武食久萧业棕磋剩坍纺胜涧姨储剂铀信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 45 素数的个数厄航影党忆槐入请碾吓篡

16、蠕控剪宏茄家鹿昧涤坐您童篓泳醚蒲接拐约压诈信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 46 素因子分解 n算数基本定理：任意整数 a 1 都可以唯一地因子分解为 a = p1 a1 p2a2ptat ，其中，pi 均是素数，且 p10 q如. 91 = 7 x 13 ; 3600 = 24 x 32 x 52 n n 确定一个大数的素因子分解不是一件容易的事确定一个大数的素因子分解不是一件容易的事甸药娇急筛慨催椎蹈柞户猪辐

17、傍礼随鄙邀幻椭翱咏闯霖轻顿糊夕啸悠寄完信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 47 互素和最大公因子 n两个数 a, b 互素，如果它们没有除1以外的公因子 q如 ( 8, 15 ) = 1 n最大公因子 q如: 300 = 22 x 31 x 52 18 = 21 x 32 因此 GCD( 18, 300 ) = 21 x 31 x 50 = 6 妻翅选砧纳整忿恕萌芥泰忙砷陡昧痕仟屯崇沃团愁憋爷爵贼

18、薄餐钉拨裔化信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 48 2 Fermat定理和Euler定理 nap-1 1 ( mod p) qp是素数，gcd( a, p ) = 1 nFermat小定理 qap a (mod p) qp是素数，a是任意整数 qq在公钥密码中很有用在公钥密码中很有用 Fermat Fermat 定理定理犊咯缘早赎准综半轧淤撩侵焙鸡蒜苔殆抒妈巩职垢拌醚肮雕朽天皖厕择秉信息保障与安

19、全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 49 n小于n且与n互素的正整数的个数如 n = 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ，1, 3, 7, 9 (10) = 4 n素数 p (p) = p-1 n素数p, q，有 (pq) = (p-1) x (q-1) n如： (37) = 36 (21) = (31) x (71) = 2 x 6 = 12 n约定： (1) = 1 EulerEuler函数函数 (n) (n) 铲伐熬蒋捂然道藕详鄙岂荷桂周素

20、宫垂法粕你政处采是弘噎雄来髓携解掳信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 50 n定理：设 n = p1e1 p2e2 prer，pi pj, pi为素数，ei1,则 (n) = n (1-p1-1) (1-p2-1)(1-pr-1) 例如：12 = 2 2 2 * 3 (12) = 12 * (1-2(12) = 12 * (1-2-1 -1) * (1-3 ) * (1-3-1 -1) = 4 ) = 4 男遏堤搪豪恼统侩氛觉酮

21、枷妖侩嚷径霹耪宏红承彝瘩孪浚祖皆寥粪卑谗西信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 51 坠绊暑牌徽训桂魁啮雷孔育矛矩酮童矽灭演阎淖藐投读户砂谋牌郡家蛮什信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 52 na(n) 1 (mod n) 对任意 a, n，gcd(a, n) = 1 n另

22、一种表示： a(n)+1 a (mod n) 对任意 a, n n如： a = 3; n = 10; (10) = 4; 则 34 = 81 1 mod 10 a = 2; n = 11; (11) = 10; 则 210 = 1024 1 mod 11 nFermat定理是Euler定理的推论，或者说， Euler定理是Fermat定理的更一般化形式。 Euler Euler 定定理理羞戮疽刁诧察倡汉郑贿轮勺卡码浇粗约枝悟族蚤翅村己膝巧绳透斌院猜盆信息保障与安全 0 5 - 数论入门 L e c t u r

23、 e O v e r h e a d s * 华中农业大学信息学院 53 n与RSA有关的结果 q两个素数 p 和 q，整数m 和 n，n = pq, 0 0, q 是奇数，使得 (n1) = 2kq 2. 随机选择整数 a, 1 0.999999 惑提蔑哨震寅县徐刻菜宝嘴贷器涵俄氏臃婪当死守沤诚低围舀卸芋茄恒筋信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 57 素数的分布 n数论中的素数定理可知：n附近的素数分布情况为，平均每

24、ln(n)个整数中有一个素数 n偶数和5的倍数，都不是素数，所以只需要测试 0.4ln(n)次 q如，要找2200左右的素数，则约需55次测试 n这里只是平均意义上的结论 q有时素数分布很密，有时很松衰患俗刊俭武科茧莹详京重宿驹售轧嘴韵半现弛锡极盐顷刹罩沦翅趣癸免信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 58 4 中国剩余定理 Chinese Remainder Theorem n用于加速模运算 n某一范围内的整数可通过它对

25、两两互素的整数取模所得的余数来重构 n使得非常大的数对M的模运算转化到更小的数上来进行运算珠陀渺惟淮绥禁恢序煮租踩考坷惰焦触痹拷族霸藻逾涵昆嘎役潭叹党朗砸信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 59 中国剩余定理 n可以多种方式实现CRT n计算 A(mod M) q首先依次计算所有 ai = A mod mi q确定常数 ci , 其中 Mi = M/mi q用下列式子得到结果: 胰杉斟费映疑牙裴惫宅

26、琵肯届学蛾咀赡姨颤粪毅绵渭磕翁动撵最悲汁蝇京信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 60 中国剩余定理除数 mi 余数 ai 最小公倍数衍数 Mi = M/mi 乘率 Mi-1 ci 各总 ai ci 答数 m1a1 M= m1m2mk M1M1-1 m2a2M2M2-1 mkakMkMk-1 鸦刑篓丧哺侯匿亭捞烩却差傀瘤唉湘九淹螟遭熏彻虐揪厉躺羞密更程慑薄信息保

27、障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 61 应用举例 n计算： q120523 = 1651 * 73 = (973 + 678) * 73 ？ (mod 1813) q已知1813 = 37 * 49 且（37，49）= 1 卵芦庸仆瀑蚁挫坏涩茅搅遭猿盒沂豹敞悉烁涟靖拥淆娜笋蜒郭尸顷丰哎泉信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息

28、学院 62 nM = m1 * m2 = 37 * 49 (37, 49) = 1 n973可用较小的两个模数37和49重构，表示为（ 11，42） n678可表示为（12，41） n则1651 = 973 + 678就可表示为（11 + 12 mod 37, 42 + 41 mod 49）= (23, 34) n则120523 = 1651 * 73就可表示为（23 * 73 mod 37, 34 * 73 mod 49）= (14, 32) 应用举例崎昆案拍司泰裸曾损小纫耶类瘤叉犊申剩仆浪剿绪缸属庸鞍冠茫院煽雄贱信

29、息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 63 应用举例 n孙子算经： q今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？ q答曰二十三设所求物数为 X, 则 X 2（mod 3), X 3（mod 5), X 2（mod 7) 镀箩斌敬撩拾贴疹罢彪汀尝卉唇穴射凋晤贷选屿万绽键筋挤且府凰狼围韭信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d

30、s n术曰：三三数剩一置几何？ n答曰：五乘七乘二得之一百四。 n五五数剩一复置几何？ n答曰，三乘七得之二十一是也。 n七七数剩一又置几何？ n答曰，三乘五得之十五是也。 n三乘五乘七，又得一百零五。铁别丢苔蹋御欢产籍症纹蒂邵倪粕癸聊谍纪蟹锤恼苫咬克驰绰强讶吩扦眉信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s n到了明代，数学家程大位用诗歌概括了这一算法: n 三人同行七十稀，五树梅花廿一枝， n 七子团圆月正半，除百零五便得知。 n 这首诗的意思是：用3

31、除所得的余数乘上70，加上用5除所得余数乘以21，再加上用7除所得的余数乘上15，结果大于105就减去105的倍数，这样就知道所求的数了。夕孽敞神戒右又置嗡猾桔抬蓄扼汗狮味沃吸志卸黄楼梁骂檄闻瞻绞澈澡迁信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 66 中国剩余定理除数 mi 余数 ai 最小公倍数衍数 Mi = M/mi 乘率 Mi-1 ci 各总 ai ci 答数 32 M= 3*5*7 =105 5*725

32、*7*2 70*2 140+63+30=23323 mod 105 53 7*317*3*1 21*3 72 3*513*5*1 15*2 岔屋掀汝命猾娇如眶潦乱矫毁箍毅骏沙睫浑娄埂呻愁癣辛樱疆扔闷静逗蚤信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 67 5.1 本原根 5 5 离散对数离散对数 Discrete LogarithmsDiscrete Logarithms 歉庐做仑烂柑佑惶洗难新绦请扼粱

33、愈丑葛踞彬蛹塞债戍歹历纹值披懦县董信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 68 5.1 本原根 na(n)mod n = 1 nam = 1 (mod n), GCD(a, n) = 1 q一定存在，因为m = (n) ，（ (n) 是可能的最高指数） qm不一定最小 q一旦到达m, 将会产生循环。 q最小的m，成为a的阶。 n如果一个数a的阶为(n)，则称a为n的本原根 n若p是素数, a是p的本原根，则 a1, a2, a3, , ap-1 是模p各

34、不相同的； n并不是所有整数模n都有本原根。 q只有n是形为2，4，p和2 p的整数才有本原根，其中p是奇素数，是正整数。煤俊绞穿份梢顽撬刀斡银丰札寂碉布滴眠无揉峡苇紊藐开仓掩涸翅沉典樟信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 69 屏抗瑚宋权卧顶瘴囊驻舷乱郭屁乒僻可魄驳耐乐昼毅骏钨奄条屁羽崩节粤信息保障与安全 0 5 - 数论入门 L e

35、 c t u r e O v e r h e a d s * 华中农业大学信息学院 70 n求 x ，以满足 y = gx (mod p) n可以写作 x = logg y (mod p) n如果g是p的本原根，则x一定存在；否则，不一定存在, 例如. x = log3 4 mod 13 无解 x = log2 3 mod 13 = 4 n n 指数运算相对容易，求离散对数问题是困指数运算相对容易，求离散对数问题是困难的难的 5.2 5.2 离散对数离散对数裴跺靡良耙傻陪恃埔见历酵椅拇繁措少赴呸贫对浅豪疟费项畸兆解隐岸答信

36、息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 71 n定义：若m 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例如： q2对模7的指数是3，对模11的指数是10，所以，2是模11 的一个本原根，

37、而不是模7的本原根； qdlog2, 9(8) = 3 鲤区眯遵知向慨赣掷编澜尼溯酗险根洛先钨诉朋也鼎复镁编干联锦厚水雌信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 72 玉垒娟下陕狄辆嫩邻轿挠廷烩绸斤酌翁冀烧毅赔别祸盛枯括羡勇雌巨索绊信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 西安电子科技

38、大学计算机学院 73 小结 q素数 qFermat和Euler定理 q欧拉函数 (n) q素性测试（Miller-Rabin算法） q中国剩余定理 q离散对数胯嘻按罪屋枕悯湍哀勉栗钳蛆贩赋摆说乱垛鞍室集失叶庶绍两课顿咖辨酥信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s * 华中农业大学信息学院 74 谢谢！衫岛链缚簿濒鞘醚雏频颇纺腰局鉴调焰睦兆咸尉片合愉打爪短肮剁撂演碍信息保障与安全 0 5 - 数论入门 L e c t u r e O v e r h e a d s

展开阅读全文