《信息安全导论》 课件 第2章 信息安全数学基础

第二章信息安全数学基础网络安全(应用技术)密码学(理论基础)信息安全数学(数论、代数和椭圆曲线理论)身份识别技术、防火墙技术、入侵检测技术等数的集合：{…，-3，-2，-1，0，1，2，3，…}在数学中有一门称为“整数论”的分支早在公元前50年左右，在我国第一部数学专著《九章算术》(作者不详)的第一章中就开始讨论整数，介绍了辗转相除法它与公元前三世纪欧几里德所著《几何原本》中介绍的辗转相除法是各自独立地总结出来的五世纪时，在我国的《孙子算经》中更有闻名于世的中国剩余定理(即孙子定理)，也对整数做了研究整数论是研究整数的学科整数什么叫整数？整数的一部分—最简单的数学模型就是自然数自然数的严格定义是在集合论的基础上，由Peano(皮亚诺)给出了自然数公理如果有一些对象(可数集)，除了它们的数目之外其它性质我们不予考虑的话，我们就可以用自然数来数它们无穷大总有一些数目由于太大而没有名称。这种现象或许就是人们第一次碰到无穷大这在古代就已经导致这种严肃的问题：有没有大得不能数的数？阿基米德在一本题为《数沙器》(公元前200年)的书中回答了他列举了一系列增长很快的数目，并且通过体积的估计而证明：这些数目当中有些数目比地球上甚至比太阳系中的沙粒的数目还大素数的数目是有限多还是无穷多？有了研究的对象集合，再建立对象集合上的运算。一些乘法的经验表明，有些数是一些比1大的其它数的乘积而有些数，就没有这种性质----质数(素数)在欧几里德的《原本》中，已经有一个简单而巧妙的推理能够得出结论：质数无穷多计算机只能处理有限数和有限个数，计算机的计算模型，硬件体系结构的设计与实现，代数编码，软件设计与实现，计算机通信及密码学等，都广泛使用了整数理论而数学可以处理无穷大数论特点任意两个整数可以相加，相减，相乘，结果仍是整数但两个整数不一定能在整数的范围内相除，这是整数系统的特点研究整数就针对这一特点加以分析实际上，研究整数的性质基本上就是要研究整除性和因数分解等问题以及其它一些有关的问题数论内容介绍数论中一些最基本的事实介绍整数的一些最基本的性质有时似乎在叙述或证明一些尽人皆知非常明显的事实。实则并非如此有些事情，我们习而不察，知其然而不知其所以然。有些事情，虽然知道，却知道的不确切若未特别指明，凡出现的数都是指整数本章主要内容：整除的概念欧几里得算法(*)整数的表示最大公因子与广义欧几里得算法(*)最小公倍数素数与算数基本定理(*)素数定理1.1整除的概念欧几里得除法一、整除基本概念及性质

练习：1.设a，b是两个给定的非零整数，且有整数x，y使得ax+by=1.证明：若a|n且b|n，则ab|n2.设是整系数多项式。若d|b-c，则d|解答：1.证明：由n=n(ax+by)=(na)x+(nb)y,及ab|na，ab|nb得证。2.证明：

又得证。二、素数(质数)及其判别法三、欧几里得除法(带余除法)思考题作业1.2整数的表示例1表示整数642为二进制因为：1111F150111771110E140110661101D130101551100C120100441011B110011331010A10001022100199000111100088000000二进制十六进制十进制二进制十六进制十进制二进制,十进制和十六进制换算表

一般地,将十进制转换为二进制比转换为十六进制要容易些.因此要将十进制转换为十六进制,可先将十进制转换为二进制,再将二进制转换为十六进制.(四位二进制数对应一个十六进制数)1.3最大公因数与广义欧几里得除法一、最大公因数如何才能计算出两个整数的最大公因数？方法1：直接分解两个整数但当整数很大时不可行(后面我们会讲到大整数分解是很困难的事情)方法2：广义欧几里得算法/辗转相除法二、广义欧几里得除法求最大公因数的步骤(*)：ja(r0)b(r1)101100123……………………nj0123456是否也有(a，d)=1和(b，c)=1？？欧几里得除法的应用：1.4整除的进一步性质及最小公倍数一、整除的性质练习：设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)二、最小公倍数1.5素数算术基本定理每个正整数可表示成素数幂的乘积素数是否有无穷多个？如果有无穷多个，那么作为无穷大量，素数个数具有怎样的形状？对正实数x，以

(x)表示不超过x的素数个数例如：

(15)=6，

(10.4)=4，

(50)=15定理1素数有无限多个费尔马--业余数学家之王费尔马(PierredeFermat，1601～1665)法国著名数学家1601.8.17出生于法国图卢兹。父亲开了一家大皮革商店，拥有相当丰厚的产业小时候受教于他的叔叔14岁时，才进入博蒙·德·洛马涅公学，毕业后先后在奥尔良大学和图卢兹大学学习法律还没大学毕业，便买好了“律师”和“参议员”的职位。1631年毕业返回家乡以后，便成为图卢兹议会的议员直到去世都没失去官职，而且逐年得到提升1646年，费马升任议会首席发言人，还当过天主教联盟的主席等职。费马的官场生涯没有突出政绩费马生有三女二男，长子整理了费马的数学论著并积极出版费马的数学论著《数学论集》

对数论的贡献主要有：费马大定理：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时的Fn122计算机科学与技术学院2024/7/15证明可参考：《素数定理的初等证明》潘承洞潘成彪著问题：当n为素数时，2n-1一定是素数吗？211-1=2047=23*89高斯函数[x]和{x}的定