信息安全数学基础1.ppt

信息安全数学基础张张 立立 江江2024/5/12 周日1.信息安全信息安全数学(数论、代数和椭圆曲线理论)身份识别技术、防火墙技术、入侵检测技术等2024/5/12 周日2.课程内容课程内容数论代数(群、环、域)-新第8章(第8,9,10,11,12章)椭圆曲线-新第9章(第13章)同余式(第3章)二次同余式与平方剩余(第4章)原根与指标(第5章)素性检测(第6+14章)连分数(第7章)不定方程与同余(第2章)整数的可除性(第1章)2024/5/12 周日3.选用教材：信息安全数学基础陈恭亮 著参考书目：初等数论 潘承洞 潘承彪 著代数学引论 第2版 聂灵沼 丁石孙 著“Commutative Algebra”第1、2卷 O.Zariski&P.Samuel 著“Primality and Cryptography”E.Kranakis 著椭圆曲线密码学导论张焕国 等译2024/5/12 周日4.课件邮箱 邮箱：邮箱： 密码：密码：1234562024/5/12 周日5.信息安全数学基础第1章：整数的可除性2024/5/12 周日6.数的集合：，-3，-2，-1，0，1，2，3，在数学中有一门称为“整数论”的分支早在公元前50年左右，在我国第一部数学专著九章算术九章算术(作者不详)的第一章中就开始讨论整数，介绍了辗转相除法它与公元前三世纪欧几里德所著几何原本几何原本中介绍的辗转相除法是各自独立地总结出来的五世纪时，在我国的孙子算经孙子算经中更有闻名于世的中国剩余定理(即孙子定理)，也对整数做了研究整数论是研究整数的学科整数什么叫整数？整数的一部分最简单的数学模型就是自然数自然数的严格定义是在集合论的基础上，由Peano(皮亚诺)给出了自然数公理如果有一些对象(可数集)，除了它们的数目之外其它性质我们不予考虑的话，我们就可以用自然数来数它们无穷大总有一些数目由于太大而没有名称。这种现象或许就是人们第一次碰到无穷大这在古代就已经导致这种严肃的问题：有没有大得不能数的数？阿基米德在一本题为数沙器(公元前200年)的书中回答了他列举了一系列增长很快的数目，并且通过体积的估计而证明：这些数目当中有些数目比地球上甚至比太阳系中的沙粒的数目还大素数的数目是有限多还是无穷多？有了研究的对象集合，再建立对象集合上的运算。一些乘法的经验表明，有些数是一些比1大的其它数的乘积而有些数，就没有这种性质-质数(素数)在欧几里德的原本中，已经有一个简单而巧妙的推理能够得出结论：质数无穷多质数无穷多计算机只能处理有限数和有限个数，计算机的计算模型，硬件体系结构的设计与实现，代数编码，软件设计与实现，计算机通信及密码学等，都广泛使用了整数理论而数学数学可以处理无穷大数论特点任意两个整数可以相加，相减，相乘，结果仍是整数但两个整数不一定能在整数的范围内相除，这是整数系统的特点研究整数就针对这一特点加以分析实际上，研究整数的性质基本上就是要研究整除性和因数分解等问题以及其它一些有关的问题数论内容介绍数论中一些最基本的事实介绍整数的一些最基本的性质有时似乎在叙述或证明一些尽人皆知非常明显的事实。实则并非如此有些事情，我们习而不察，知其然而不知其所以然。有些事情，虽然知道，却知道的不确切若未特别指明，凡出现的数都是指整数本章主要内容：整除的概念欧几里得算法(*)整数的表示最大公因子与广义欧几里得算法(*)最小公倍数素数与算数基本定理(*)素数定理2024/5/12 周日13.1.1 1.1 整除的概念整除的概念 欧几里得除法欧几里得除法一、整除基本概念及性质一、整除基本概念及性质 14152024/5/12 周日16.1718192021练习：1.设a，b是两个给定的非零整数，且有整数x，y使得ax+by=1.证明：若a|n且b|n，则ab|n2.设 是整系数多项式。若d|b-c，则d|2024/5/12 周日22.解答：1.证明：由n=n(ax+by)=(na)x+(nb)y,及ab|na，ab|nb 得证。2.证明：又 得证。2024/5/12 周日23.二、素数二、素数(质数质数)及其判别法及其判别法24252627282930三、欧几里得除法三、欧几里得除法(带余除法带余除法)313233342024/5/12 周日35.2024/5/12 周日36.373839402024/5/12 周日41.2024/5/12 周日42.1.2 1.2 整数的表示整数的表示4445464748例例1 表示整数表示整数642为二进制为二进制因为：因为：4911111111F1515011101117 77 711101110E1414011001106 66 611011101D1313010101015 55 511001100C1212010001004 44 410111011B1111001100113 33 310101010A1010001000102 22 2100110019 99 9000100011 11 1100010008 88 8000000000 00 0二进制二进制十六进制十六进制十进制十进制二进制二进制十六进制十六进制十进制十进制二进制二进制,十进制和十六进制换算表十进制和十六进制换算表50 一般地一般地,将十进制转换为二进制比转换为十六将十进制转换为二进制比转换为十六进制要容易些进制要容易些.因此要将十进制转换为十六进制因此要将十进制转换为十六进制,可先将十进制转换为二进制可先将十进制转换为二进制,再将二进制转换为十再将二进制转换为十六进制六进制.(.(四位二进制数对应一个十六进制数四位二进制数对应一个十六进制数)511.3 1.3 最大公因数与广义欧几里得除法最大公因数与广义欧几里得除法一、最大公因数一、最大公因数5253545556如何才能计算出两个整数的最大公因数哪？(*)方法1：直接分解两个整数但当整数很大时不可行不可行(后面我们会讲到大整数分解是很困难的事情)方法2：广义欧几里得算法广义欧几里得算法/辗转相除法辗转相除法2024/5/12 周日57.58二、广义欧几里得除法二、广义欧几里得除法5960求最大公因数的步骤(*)：2024/5/12 周日61.6263646566676869707172ja(r0)b(r1)101100123n7374j 01234567576是否也有是否也有(a，d)=1和和(b，c)=1？2024/5/12 周日77.787980818283欧几里得除法的应用：2024/5/12 周日84.85868788891.4 1.4 整除的进一步性质及最小公倍数整除的进一步性质及最小公倍数一、整除的性质一、整除的性质9091922024/5/12 周日93.94练习：设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)=1 a=a(ak-1,b)=(ak,ab)=(ak,ck)2024/5/12 周日95.二、最小公倍数二、最小公倍数969798991001011021031041.5 1.5 素数素数 算术基本定理算术基本定理1051061071082024/5/12 周日109.110111112113114115116117118119每个正整数可表示成素数幂的乘积素数是否有无穷多个？如果有无穷多个，那么作为无穷大量，素数个数具有怎样的形状？对正实数x，以(x)表示不超过x的素数个数例如：(15)=6，(10.4)=4，(50)=152024/5/12 周日120.定理定理1 素数有无限多个素数有无限多个 2024/5/12 周日121.2024/5/12 周日122.2024/5/12 周日123.费尔马-业余数学家之王费尔马费尔马(Pierre de Fermat，16011665)法国著名数学家1601.8.17出生于法国图卢兹。父亲开了一家大皮革商店，拥有相当丰厚的产业小时候受教于他的叔叔14岁时，才进入博蒙德洛马涅公学，毕业后先后在奥尔良大学和图卢兹大学学习法律还没大学毕业，便买好了“律师”和“参议员”的职位。1631年毕业返回家乡以后，便成为图卢兹议会的议员直到去世都没失去官职，而且逐年得到提升1646年，费马升任议会首席发言人，还当过天主教联盟的主席等职。费马的官场生涯没有突出政绩费马生有三女二男，长子整理了费马的数学论著并积极出版费马的数学论著数学论集2024/5/12 周日124.对数论的贡献对数论的贡献主要有：费马大定理：n2的整数，则方程xn+yn=zn没有满足xyz0的整数解。由英国数学家怀尔斯证明(1995年)，证明过程是相当艰深的！费马小定理：ap-a0(mod p)，其中p是素数，a是正整数，证明比较简单错误贡献错误贡献1640年，费马说他发现形如Fn=2(2n)+1的数全是素数，比如当n=04时，3，5，17，257，65537都是素数，不过从第五个数开始由于数字过大，费马并没有进行验算。但后来在1732年时，大数学家欧拉欧拉发现，n=5时，641*6700417=4294967297却是个合数。并且以后被发现的数都是合数，最大的是n=1495时的Fn2024/5/12 周日125.1261272024/5/12 周日128.2024/5/12 周日129.证明可参考：素数定理的初等证明 潘承洞 潘成彪 著2024/5/12 周日130.2024/5/12 周日131.问题：当问题：当n n为素数时，为素数时，2 2n n-1-1一定是素数吗？一定是素数吗？211-1=2047=23*892024/5/12 周日132.2024/5/12 周日133.2024/5/12 周日134.高斯函数高斯函数x和和x的定义及其性质的定义及其性质135136137138本章主要内容本章主要内容139本章重点：整除的概念和性质欧几里得除法及其应用（求最大公因子及线性表达式）最大公因子和最小公倍数的性质素数的判定方法了解素数定理及素数的分布情况；习题：1,2,4,7,8,13,17,18,22,28,29,32,33,34,35,39,46,47,49,50,51,52,54,55,56其他选作2024/5/12 周日140.