信息安全数学基础1课件

1、信息安全数学基础张 立 江2022/8/61计算机科学与技术学院信息安全数学(数论、代数和椭圆曲线理论)身份识别技术、防火墙技术、入侵检测技术等2022/8/62计算机科学与技术学院课程内容数论代数(群、环、域)-新第8章(第8,9,10,11,12章)椭圆曲线-新第9章(第13章)同余式(第3章)二次同余式与平方剩余(第4章)原根与指标(第5章)素性检测(第6+14章)连分数(第7章)不定方程与同余(第2章)整数的可除性(第1章)2022/8/63计算机科学与技术学院选用教材：信息安全数学基础陈恭亮 著参考书目： 初等数论 潘承洞 潘承彪 著代数学引论 第2版 聂灵沼 丁石孙 著“Commu

2、tative Algebra”第1、2卷 O. Zariski & P. Samuel 著“Primality and Cryptography”E. Kranakis 著椭圆曲线密码学导论张焕国 等译2022/8/64计算机科学与技术学院课件邮箱 邮箱： 密码：1234562022/8/65计算机科学与技术学院信息安全数学基础第1章：整数的可除性2022/8/66计算机科学与技术学院数的集合：，-3，-2，-1，0，1，2，3， 在数学中有一门称为“整数论”的分支早在公元前50年左右，在我国第一部数学专著九章算术(作者不详)的第一章中就开始讨论整数，介绍了辗转相除法它与公元前三世纪欧几里德所

3、著几何原本中介绍的辗转相除法是各自独立地总结出来的五世纪时，在我国的孙子算经中更有闻名于世的中国剩余定理(即孙子定理)，也对整数做了研究整数论是研究整数的学科整数什么叫整数？整数的一部分最简单的数学模型就是自然数自然数的严格定义是在集合论的基础上，由Peano(皮亚诺)给出了自然数公理如果有一些对象(可数集)，除了它们的数目之外其它性质我们不予考虑的话，我们就可以用自然数来数它们无穷大总有一些数目由于太大而没有名称。这种现象或许就是人们第一次碰到无穷大这在古代就已经导致这种严肃的问题：有没有大得不能数的数？阿基米德在一本题为数沙器(公元前200年)的书中回答了他列举了一系列增长很快的数目，并且

4、通过体积的估计而证明：这些数目当中有些数目比地球上甚至比太阳系中的沙粒的数目还大素数的数目是有限多还是无穷多？有了研究的对象集合，再建立对象集合上的运算。一些乘法的经验表明，有些数是一些比1大的其它数的乘积而有些数，就没有这种性质-质数(素数)在欧几里德的原本中，已经有一个简单而巧妙的推理能够得出结论：质数无穷多计算机只能处理有限数和有限个数，计算机的计算模型，硬件体系结构的设计与实现，代数编码，软件设计与实现，计算机通信及密码学等，都广泛使用了整数理论而数学可以处理无穷大数论特点任意两个整数可以相加，相减，相乘，结果仍是整数但两个整数不一定能在整数的范围内相除，这是整数系统的特点研究整数就针

5、对这一特点加以分析实际上，研究整数的性质基本上就是要研究整除性和因数分解等问题以及其它一些有关的问题数论内容介绍数论中一些最基本的事实介绍整数的一些最基本的性质有时似乎在叙述或证明一些尽人皆知非常明显的事实。实则并非如此有些事情，我们习而不察，知其然而不知其所以然。有些事情，虽然知道，却知道的不确切若未特别指明，凡出现的数都是指整数本章主要内容：整除的概念欧几里得算法(*)整数的表示最大公因子与广义欧几里得算法(*)最小公倍数素数与算数基本定理(*)素数定理2022/8/613计算机科学与技术学院1.1 整除的概念 欧几里得除法一、整除基本概念及性质 14152022/8/616计算机科学与技

6、术学院1718192021练习：1. 设a，b是两个给定的非零整数，且有整数x，y使得ax+by=1.证明：若a|n且b|n，则ab|n2. 设 是整系数多项式。若d|b-c，则d|2022/8/622计算机科学与技术学院解答：1.证明：由n=n(ax+by)=(na)x+(nb)y,及ab|na，ab|nb 得证。2.证明： 又 得证。 2022/8/623计算机科学与技术学院二、素数(质数)及其判别法24252627282930三、欧几里得除法(带余除法)313233342022/8/635计算机科学与技术学院2022/8/636计算机科学与技术学院373839402022/8/641计算

7、机科学与技术学院2022/8/642计算机科学与技术学院思考题作业431.2 整数的表示4445464748例1 表示整数642为二进制因为：491111F150111771110E140110661101D130101551100C120100441011B110011331010A10001022100199000111100088000000二进制十六进制十进制二进制十六进制十进制二进制,十进制和十六进制换算表50 一般地,将十进制转换为二进制比转换为十六进制要容易些.因此要将十进制转换为十六进制,可先将十进制转换为二进制,再将二进制转换为十六进制.(四位二进制数对应一个十六进制数)51

8、1.3 最大公因数与广义欧几里得除法一、最大公因数5253545556如何才能计算出两个整数的最大公因数哪？(*)方法1：直接分解两个整数但当整数很大时不可行(后面我们会讲到大整数分解是很困难的事情)方法2：广义欧几里得算法/辗转相除法2022/8/657计算机科学与技术学院58二、广义欧几里得除法5960求最大公因数的步骤(*)：2022/8/661计算机科学与技术学院6263646566676869707172ja(r0)b(r1)101100123n7374j 01234567576是否也有(a，d)=1和(b，c)=1？2022/8/677计算机科学与技术学院787980818283欧

9、几里得除法的应用：2022/8/684计算机科学与技术学院85868788891.4 整除的进一步性质及最小公倍数一、整除的性质9091922022/8/693计算机科学与技术学院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)2022/8/695计算机科学与技术学院二、最小公倍数969798991001011021031041.5 素数 算术基本定理1051061071

10、082022/8/6109计算机科学与技术学院110111112113114115116117118119每个正整数可表示成素数幂的乘积素数是否有无穷多个？如果有无穷多个，那么作为无穷大量，素数个数具有怎样的形状？对正实数x，以(x)表示不超过x的素数个数例如：(15) = 6，(10.4) = 4，(50) = 152022/8/6120计算机科学与技术学院定理1 素数有无限多个 2022/8/6121计算机科学与技术学院2022/8/6122计算机科学与技术学院2022/8/6123计算机科学与技术学院费尔马-业余数学家之王费尔马(Pierre de Fermat，16011665)法国著

11、名数学家1601.8.17出生于法国图卢兹。父亲开了一家大皮革商店，拥有相当丰厚的产业小时候受教于他的叔叔14岁时，才进入博蒙德洛马涅公学，毕业后先后在奥尔良大学和图卢兹大学学习法律还没大学毕业，便买好了“律师”和“参议员”的职位。 1631年毕业返回家乡以后，便成为图卢兹议会的议员直到去世都没失去官职，而且逐年得到提升1646年，费马升任议会首席发言人，还当过天主教联盟的主席等职。费马的官场生涯没有突出政绩费马生有三女二男，长子整理了费马的数学论著并积极出版费马的数学论著数学论集2022/8/6124计算机科学与技术学院对数论的贡献主要有：费马大定理：n2的整数，则方程xn+yn=zn没有满

12、足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时的Fn2022/8/6125计算机科学与技术学院1261272022/8/6128计算机科学与技术学院2022/8/6129计算机科学与技术学院证明可参考： 素数定理的初等证明 潘承洞 潘成彪 著2022/8/6130计算机科学与技术学院2022/8/6131计算机科学与技术学院问题：当n为素数时，2n-1一定是素数吗？211-1=2047=23*892022/8/6132计算机科学与技术学院2022/8/6133计算机科学与技术学院2022/8/6134计算机科学与技术学院高斯函数x和