信息安全数学基础1.ppt

2020 3 31 计算机科学与技术学院 1 信息安全数学基础 张立江cheungcumt 2020 3 31 计算机科学与技术学院 2 信息安全 2020 3 31 计算机科学与技术学院 3 课程内容 数论 代数 群 环 域 新第8章 第8 9 10 11 12章 椭圆曲线 新第9章 第13章 2020 3 31 计算机科学与技术学院 4 选用教材 信息安全数学基础 陈恭亮著参考书目 初等数论 潘承洞潘承彪著 代数学引论 第2版聂灵沼丁石孙著 CommutativeAlgebra 第1 2卷O Zariski P Samuel著 PrimalityandCryptography E Kranakis著 椭圆曲线密码学导论 张焕国等译 2020 3 31 计算机科学与技术学院 5 课件邮箱 邮箱 infosecmath 密码 123456 2020 3 31 计算机科学与技术学院 6 信息安全数学基础第1章 整数的可除性 数的集合 3 2 1 0 1 2 3 在数学中有一门称为 整数论 的分支早在公元前50年左右 在我国第一部数学专著 九章算术 作者不详 的第一章中就开始讨论整数 介绍了辗转相除法它与公元前三世纪欧几里德所著 几何原本 中介绍的辗转相除法是各自独立地总结出来的五世纪时 在我国的 孙子算经 中更有闻名于世的中国剩余定理 即孙子定理 也对整数做了研究 整数论是研究整数的学科 整数 什么叫整数 整数的一部分 最简单的数学模型就是自然数自然数的严格定义是在集合论的基础上 由Peano 皮亚诺 给出了自然数公理如果有一些对象 可数集 除了它们的数目之外其它性质我们不予考虑的话 我们就可以用自然数来数它们 无穷大 总有一些数目由于太大而没有名称 这种现象或许就是人们第一次碰到无穷大这在古代就已经导致这种严肃的问题 有没有大得不能数的数 阿基米德在一本题为 数沙器 公元前200年 的书中回答了他列举了一系列增长很快的数目 并且通过体积的估计而证明 这些数目当中有些数目比地球上甚至比太阳系中的沙粒的数目还大 素数的数目是有限多还是无穷多 有了研究的对象集合 再建立对象集合上的运算 一些乘法的经验表明 有些数是一些比1大的其它数的乘积而有些数 就没有这种性质 质数 素数 在欧几里德的 原本 中 已经有一个简单而巧妙的推理能够得出结论 质数无穷多计算机只能处理有限数和有限个数 计算机的计算模型 硬件体系结构的设计与实现 代数编码 软件设计与实现 计算机通信及密码学等 都广泛使用了整数理论而数学可以处理无穷大 数论特点 任意两个整数可以相加 相减 相乘 结果仍是整数但两个整数不一定能在整数的范围内相除 这是整数系统的特点研究整数就针对这一特点加以分析实际上 研究整数的性质基本上就是要研究整除性和因数分解等问题以及其它一些有关的问题 数论内容 介绍数论中一些最基本的事实介绍整数的一些最基本的性质有时似乎在叙述或证明一些尽人皆知非常明显的事实 实则并非如此有些事情 我们习而不察 知其然而不知其所以然 有些事情 虽然知道 却知道的不确切若未特别指明 凡出现的数都是指整数 2020 3 31 计算机科学与技术学院 13 本章主要内容 整除的概念欧几里得算法 整数的表示最大公因子与广义欧几里得算法 最小公倍数素数与算数基本定理 素数定理 14 1 1整除的概念欧几里得除法 一 整除基本概念及性质 15 2020 3 31 计算机科学与技术学院 16 17 18 19 20 21 2020 3 31 计算机科学与技术学院 22 练习 1 设a b是两个给定的非零整数 且有整数x y使得ax by 1 证明 若a n且b n 则ab n2 设是整系数多项式 若d b c 则d 2020 3 31 计算机科学与技术学院 23 解答 1 证明 由n n ax by na x nb y 及ab na ab nb得证 2 证明 又得证 24 二 素数 质数 及其判别法 25 26 27 28 29 30 31 三 欧几里得除法 带余除法 32 33 34 2020 3 31 计算机科学与技术学院 35 2020 3 31 计算机科学与技术学院 36 37 38 39 40 2020 3 31 计算机科学与技术学院 41 2020 3 31 计算机科学与技术学院 42 43 思考题 作业 44 1 2整数的表示 45 46 47 48 49 例1表示整数642为二进制 因为 50 二进制 十进制和十六进制换算表 51 一般地 将十进制转换为二进制比转换为十六进制要容易些 因此要将十进制转换为十六进制 可先将十进制转换为二进制 再将二进制转换为十六进制 四位二进制数对应一个十六进制数 52 1 3最大公因数与广义欧几里得除法 一 最大公因数 53 54 55 56 2020 3 31 计算机科学与技术学院 57 如何才能计算出两个整数的最大公因数哪 方法1 直接分解两个整数但当整数很大时不可行 后面我们会讲到大整数分解是很困难的事情 方法2 广义欧几里得算法 辗转相除法 58 59 二 广义欧几里得除法 60 2020 3 31 计算机科学与技术学院 61 求最大公因数的步骤 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 2020 3 31 计算机科学与技术学院 77 是否也有 a d 1和 b c 1 78 79 80 81 82 83 2020 3 31 计算机科学与技术学院 84 欧几里得除法的应用 85 86 87 88 89 90 1 4整除的进一步性质及最小公倍数 一 整除的性质 91 92 2020 3 31 计算机科学与技术学院 93 94 2020 3 31 计算机科学与技术学院 95 练习 设k是正整数 证明 1 ak bk a b k 2 设a b是正整数 若 a b 1 ab ck 则a a c k b b c k提示 a b 1 ak 1 b 1a a ak 1 b ak ab ak ck 96 二 最小公倍数 97 98 99 100 101 102 103 104 105 1 5素数算术基本定理 106 107 108 2020 3 31 计算机科学与技术学院 109 110 111 112 113 114 115 116 117 118 119 2020 3 31 计算机科学与技术学院 120 每个正整数可表示成素数幂的乘积素数是否有无穷多个 如果有无穷多个 那么作为无穷大量 素数个数具有怎样的形状 对正实数x 以 x 表示不超过x的素数个数例如 15 6 10 4 4 50 15 2020 3 31 计算机科学与技术学院 121 定理1素数有无限多个 2020 3 31 计算机科学与技术学院 122 2020 3 31 计算机科学与技术学院 123 2020 3 31 计算机科学与技术学院 124 费尔马 业余数学家之王 费尔马 PierredeFermat 1601 1665 法国著名数学家1601 8 17出生于法国图卢兹 父亲开了一家大皮革商店 拥有相当丰厚的产业小时候受教于他的叔叔14岁时 才进入博蒙 德 洛马涅公学 毕业后先后在奥尔良大学和图卢兹大学学习法律还没大学毕业 便买好了 律师 和 参议员 的职位 1631年毕业返回家乡以后 便成为图卢兹议会的议员直到去世都没失去官职 而且逐年得到提升1646年 费马升任议会首席发言人 还当过天主教联盟的主席等职 费马的官场生涯没有突出政绩费马生有三女二男 长子整理了费马的数学论著并积极出版费马的数学论著 数学论集 2020 3 31 计算机科学与技术学院 125 对数论的贡献主要有 费马大定理 n 2的整数 则方程x n y n z n没有满足xyz 0的整数解 由英国数学家怀尔斯证明 1995年 证明过程是相当艰深的 费马小定理 a p a 0 modp 其中p是素数 a是正整数 证明比较简单错误贡献1640年 费马说他发现形如Fn 2 2 n 1的数全是素数 比如当n 0 4时 3 5 17 257 65537都是素数 不过从第五个数开始由于数字过大 费马并没有进行验算 但后来在1732年时 大数学家欧拉发现 n 5时 641 6700417 4294967297却是个合数 并且以后被发现的数都是合数 最大的是n 1495时的Fn 126 127 2020 3 31 计算机科学与技术学院 128 2020 3 31 计算机科学与技术学院 129 2020 3 31 计算机科学与技术学院 130 证明可参考 素数定理的初等证明 潘承洞潘成彪著 2020 3 31 计算机科学与技术学院 131 2020 3 31 计算机科学与技术学院 132 问题 当n为素数时 2n 1一定是素数吗 211 1 2047 23 89 2020 3 31 计算机科学与技术学院 133 2020 3 31 计算机科学与技术学院 134 135 高斯函数 x 和 x 的定义及其性质 136 137 138 139 本章主要内容 2020 3 31 计算机科学与技