1、2022-8-5计算机应用技术研究所计算机应用技术研究所1离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第2 2章章 整数与算法设计基础整数与算法设计基础（上）（上）2022-8-52022-8-5 同余算术及其运用同余算术及其运用2 2 算法设计的基本知识算法设计的基本知识3 3 整数整数的基本知识的基本知识1 1 算法设计策略与应用算法设计策略与应用4 4&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所4整数的
2、基本知识整数的基本知识&整数的基本知识整数的基本知识J 整数与整除算法整数与整除算法4 整数的因数分解整数的因数分解4 素数的性质与查找素数的性质与查找2022-8-5计算机应用技术研究所计算机应用技术研究所6&整数整数在第一章，我们得到自然数和自然数集的定义。在自然数集中加入每个非零的相反数就得到整个整数集合Z。对于整数集合Z，有：Z=,-4,-3,-2,-1,0,1,2,3,42022-8-5计算机应用技术研究所计算机应用技术研究所7&整除的概念与性质整除的概念与性质2022-8-5计算机应用技术研究所计算机应用技术研究所8&素数（质数）与合数素数（质数）与合数目前使用较有效的方法是试除法
3、。用试除法判断一个自然数a是不是素数时，用各个素数从小到大依次去除a，如果到某一个素数正好整除，这个a就可以断定不是素数；如果不能整除，当不完全商又小于这个素数时，就不必再继续试除，可以断定a必然是素数。2022-8-5计算机应用技术研究所计算机应用技术研究所9&整数相关的定理整数相关的定理2022-8-5计算机应用技术研究所计算机应用技术研究所10&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所11&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所12&整数相关的定理整数相关的定理2022-8-5计算机应用技术研究所计算机应用技术研究所13&总结总结从上述
4、定理的证明过程可以看出，整除是带余除法中余数等于 0 的情形。因此，带余除法可以看成是对整除的一种推广。事实上，还可通过带余除法的概念来定义和理解整除的概念，即 a 能够整除 b 的当且仅当 b 除以 a 的余数为 0。&整数的因数分解整数的因数分解4 整数与整数除法整数与整数除法J 整数的因数分解整数的因数分解4 素数的性质和查找素数的性质和查找2022-8-5计算机应用技术研究所计算机应用技术研究所15&因数分解的概念因数分解的概念把一个整数分解成两个或更多的除1外的整数相乘的过程。这些整数称为这个数的因数。2022-8-5计算机应用技术研究所计算机应用技术研究所16&公因数与公倍数公因数
5、与公倍数这两个问题该怎么求解呢？这就用到了下面介绍的公因数与公倍数的概念2022-8-5计算机应用技术研究所计算机应用技术研究所17&最大公因数与最小公倍最大公因数与最小公倍数的概念数的概念最小公最小公倍数倍数最大公最大公因数因数自然数1可以整除任意整数，因此对于任意两个整数，它们的公因数总是存在的。公因数表达的是两个整数的共同部分，通常需要考察两个整数之间的共同部分最大值能达到多少，故有所谓最大公因数的概念。同样，对于任意两个整数，这两个整数的乘积就是它们的公倍数，因此，公倍数总是存在的，需要着重考察的通常式公倍数的最小值，因而有最小公倍数的概念。2022-8-5计算机应用技术研究所计算机应
6、用技术研究所18&最大公因数与最小公倍最大公因数与最小公倍数的概念数的概念前面已经学习了两个整数的最大公因数与最小公倍数的概念，现在推广到K个整数的情况2022-8-5计算机应用技术研究所计算机应用技术研究所19&最大公因数与最小公倍最大公因数与最小公倍数的概念数的概念2022-8-5计算机应用技术研究所计算机应用技术研究所20&最大公因数与最小公倍最大公因数与最小公倍数的关系数的关系通过最大公因数与最小公倍数的定义，我们可以看到这二者是通过两个自然数的某种运算得到的，那么这二者之间是否存在某种关系呢？2022-8-5计算机应用技术研究所计算机应用技术研究所21&最大公因数的性质最大公因数的性
7、质最大公因数在带余除法中有一个比较好的性质，在这里加以介绍2022-8-5计算机应用技术研究所计算机应用技术研究所22&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所23&辗转相除法辗转相除法辗转相除法是一种古老的算法，在国际上也称为欧几里得算法，起初源于欧几里得几何原本第卷命题，在中国也称为更相减损术，最初来源于九章算术方田第六题。2022-8-5计算机应用技术研究所计算机应用技术研究所24&辗转相除法辗转相除法 第一步:输入两个正整数m,n(mn);第二步:计算m除以n所得的余数r;第三步:m=n n=r;第四步:若r=0,则 m,n的最大公约数等于m;否则转到第二步;第
8、五步:输出最大公约数m。2022-8-5计算机应用技术研究所计算机应用技术研究所25&辗转相除法辗转相除法2022-8-5计算机应用技术研究所计算机应用技术研究所26&辗转相除法辗转相除法2022-8-5计算机应用技术研究所计算机应用技术研究所27&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所28&辗转相除法辗转相除法上述定理表明，整数 a 和 b 的最大公因数可以表示为它们的一个线性组合。这就给出了最大公因式一种具体表达形式，这种表达形式对于考察最大公因数的性质具有非常重要的作用。例如，使用上述线性组合表达式，可得到最大公因数下述性质：现在我们举个例子对上述定理进行深入地
9、了解。例如，gcd(56,24)=8,因此有m=-1,n=2使得：8=56*（-1）+24*2通过这个例子我们可以看到，8不仅是56与24两个整数的最大公因数，也是这两个整数的所有因数的倍数，这才是这个定理所要告诉我们的地方。&互素的概念互素的概念从整除的角度看，两个整数的公因数表达的是这两个整数共性成分。如果两个整数的最大公因数为1，则表明这两个整数除1之外没有任何额外的共性成分。因此，从结构上看，这两个整数之间具有很强的独立性。这种很强的独立性我们称之为互素。下面就介绍互素的概念。2022-8-5计算机应用技术研究所计算机应用技术研究所30&例题例题【例题2.9】小于12的哪些正整数与12
10、互素？【例题2.10】判断整数10,17和21是否两两互素，整数10,19和24是否两两互素。2022-8-5计算机应用技术研究所计算机应用技术研究所31&互素的性质互素的性质2022-8-5计算机应用技术研究所计算机应用技术研究所32&互素性质的证明互素性质的证明2022-8-5计算机应用技术研究所计算机应用技术研究所33&互素性质的证明互素性质的证明2022-8-5计算机应用技术研究所计算机应用技术研究所34&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所35&算术基本定理算术基本定理算术基本定理是初等数论中一条非常基本和重要的定理，它把对自然数的研究转化为对其最基本的元
11、素一素数的研究。它所体现的唯一因子分解的思想，在现代交换环理论中起着非常重要的作用。唯一因子分解的思想从本质上讲是指以下两种性质:“存在性和唯一性”。所谓“存在性”就是指一个元素可以分解为有限多个不可约因子的乘积;“唯一性”是指这种分解表示在某种意义上来说是唯一的。唯一因子分解的思想最初作为一个自然数的性质而出现，这个性质就是通常所说的算术基本定理。2022-8-5计算机应用技术研究所计算机应用技术研究所36&引理引理2022-8-5计算机应用技术研究所计算机应用技术研究所37&算术基本定理算术基本定理整数素数分解的存在性与唯一性2022-8-5计算机应用技术研究所计算机应用技术研究所38&素
12、幂分解式素幂分解式整数的素幂分解式给出了整数一种基于素数的结整数的素幂分解式给出了整数一种基于素数的结构表达，在数论研究中具有非常重要的作用。构表达，在数论研究中具有非常重要的作用。2022-8-5计算机应用技术研究所计算机应用技术研究所39&例题例题【例1】写出51480的素幂分解式。【例2】写出10个连续的正整数，使他们都是合数。2022-8-5计算机应用技术研究所计算机应用技术研究所40&素幂分解式素幂分解式上面这个定理表明，可以使用其素幂分解式计算两个整数的最大公约数和最小公倍数，还可以证明最大公约数和最小公倍数之间的关系。2022-8-5计算机应用技术研究所计算机应用技术研究所41&
13、例题例题【例2】求132与240的最大公因数与最小公倍数。&整数的基本知识整数的基本知识4 整数与整数除法整数与整数除法4 整数的因数分解整数的因数分解J 素数的性质与查找素数的性质与查找2022-8-5计算机应用技术研究所计算机应用技术研究所43&素数的性质素数的性质如果一个问题的求解过程复杂度远高于其设立过程复杂度，那么它就有潜力被设计为一个密码学算法。至于像公钥密码这种天才的构想，就需要这个问题难的同时还具有一些特殊特性。目前为止，公钥密码在本质上也就RSA和椭圆曲线两套内核而已，在二者中素数都有很重要的地位。那素数又有哪些比较好的性质值得我们去学习呢？2022-8-5计算机应用技术研究
14、所计算机应用技术研究所44&素数的性质素数的性质【定理【定理2.152.15】假设p是任意一个给定的素数，则它与其它任意整数a之间的关系是：要么p与a互素，要么p能够整除a。素数的一个非常独特性质是它与其它整数之间具有如上非常简单而直接的关系，这种简单直接的关系是使用素数考察整数性质的基础。2022-8-5计算机应用技术研究所计算机应用技术研究所45&素数的性质素数的性质2022-8-5计算机应用技术研究所计算机应用技术研究所46&素数的查找素数的查找下面讨论素数的计数问题。首先考虑在整个正整数集合中，到底有多少个素数？下面的定理给出了答案：【定理定理2.172.17】正整数集合中的素数有无穷
15、多个。2022-8-5计算机应用技术研究所计算机应用技术研究所47现在我们考虑给定一个正整数集合，现在我们考虑给定一个正整数集合，如何找到这个集合中的所有素数呢？如何找到这个集合中的所有素数呢？&素数的查找素数的查找2022-8-5计算机应用技术研究所计算机应用技术研究所48【例1】判断137和157是否是素数。&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所49&爱氏晒法爱氏晒法2022-8-5计算机应用技术研究所计算机应用技术研究所50&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所51&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所
16、52&总结与拓展总结与拓展2022-8-5计算机应用技术研究所计算机应用技术研究所532022-8-52022-8-5整数整数的基本知识的基本知识1 1算法设计的基本知识算法设计的基本知识3 3同余算术及其运用同余算术及其运用2 2算法设计策略与应用算法设计策略与应用4 4&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所55同余算术及其运用同余算术及其运用&同余算术及其运用同余算术及其运用J 同余关系及其运算同余关系及其运算4 同余方程与方程组同余方程与方程组4 整数加密算法整数加密算法2022-8-5计算机应用技术研究所计算机应用技术研究所57&同余算术的产
17、生背景同余算术的产生背景 1801年,24 岁的高斯(1777-1855)出版了专著算术研究,在其中他提出了模演算法,以统一的观点处理了数论中的许多问题,从而开创了数论研究的新时代。同余算术是整理理论一个重要发展并构成初等数论的理论核心，它从在一种比整除约束更为宽松的条件下考察整数的运算及性质并得到很多非常精彩的数论成果，这些成果在整数加密算法设计等多个领域得到广泛应用。2022-8-5计算机应用技术研究所计算机应用技术研究所58&同余关系及其运算同余关系及其运算对于任一给定的正整数m，通过考察所有整数除以m所得余数的差异，把所有具有相同余数的整数归为一类，则可将所有整数分为m个基本类型。基于
18、上述思想，我们给出同余关系的定义。2022-8-5计算机应用技术研究所计算机应用技术研究所59&同余关系的判定定理同余关系的判定定理有了同余关系的概念后，对于给定的两个整数，我们如何准确判定这两个整数是否具有同余关系呢？这就用到了我们下面要讲的2022-8-5计算机应用技术研究所计算机应用技术研究所60&同余关系的判定定理同余关系的判定定理2022-8-5计算机应用技术研究所计算机应用技术研究所61&同余关系的性质同余关系的性质同余关系的保加性和保乘性：同余关系的保加性和保乘性：2022-8-5计算机应用技术研究所计算机应用技术研究所62&同余关系的性质同余关系的性质同余关系的同余关系的运算律
19、运算律：2022-8-5计算机应用技术研究所计算机应用技术研究所63&同余关系的性质同余关系的性质&同余关系的性质同余关系的性质2022-8-5计算机应用技术研究所计算机应用技术研究所65&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所66&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所67&同余类同余类前面已经介绍了同于关系的相关知识，利用同余关系可以实现对整数集合的划分，得到的结果就是划分为m个互不相交的子集合。2022-8-5计算机应用技术研究所计算机应用技术研究所68&同余类的性质同余类的性质2022-8-5计算机应用技术研究所计算机应用技术研究所6
20、9&同余类的性质同余类的性质2022-8-5计算机应用技术研究所计算机应用技术研究所70&同余类的加法与乘同余类的加法与乘法法2022-8-5计算机应用技术研究所计算机应用技术研究所71&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所72&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所73&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所74&完全剩余系完全剩余系2022-8-5计算机应用技术研究所计算机应用技术研究所75&模模m m简化同余类简化同余类2022-8-5计算机应用技术研究所计算机应用技术研究所76&欧拉函数欧拉函数2022-8
21、-5计算机应用技术研究所计算机应用技术研究所77&欧拉函数欧拉函数2022-8-5计算机应用技术研究所计算机应用技术研究所78&例题例题&例题例题&同余算术及其应用同余算术及其应用4 同余关系及其运算同余关系及其运算J 同余方程与方程组同余方程与方程组4 整数加密算法整数加密算法2022-8-5计算机应用技术研究所计算机应用技术研究所81&同余方程同余方程 孙子算经中的题目：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？孙子算经中的解法：三三数之，取数七十，与余数二相乘；五五数之，取数二十一，与余数三相乘；七七数之，取数十五，与余数二相乘。这其实就是利用方程的思想求
22、解带余除法问题，我们现在给出解决这类问题的数学方法。2022-8-5计算机应用技术研究所计算机应用技术研究所82&同余方程解的存在性同余方程解的存在性如何求解一个同余方程，即该方程是否存在解？2022-8-5计算机应用技术研究所计算机应用技术研究所83&证明证明2022-8-5计算机应用技术研究所计算机应用技术研究所84&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所85&化化1 1法法 在解一元一次方程的时候，经常将等式两边同时乘以未知数一次项系数的倒数，将未知数一次项的系数化为1，由此实现对方程组的求解。现通过类似方法对同余方程求解。化1法2022-8-5计算机应用技术研
23、究所计算机应用技术研究所862022-8-5计算机应用技术研究所计算机应用技术研究所87&证明证明2022-8-5计算机应用技术研究所计算机应用技术研究所88&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所89&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所903.3 集合定义的自然数和归纳法证明集合定义的自然数和归纳法证明&同余方程组同余方程组2022-8-5计算机应用技术研究所计算机应用技术研究所91&中国余数定理中国余数定理中国余数定理,也称中国剩余定理，孙子剩余定理。从孙子算经到秦九韶数书九章对一次同余式问题的研究成果，在19世纪中期开始受到西方数学
24、界的重视。1852年，英国传教士伟烈亚力向欧洲介绍了 孙子算经的“物不知数”题和秦九韶的“大衍求一术”；1876年，德国人马蒂生指出，中国的这一解法与西方19世纪高斯算术探究中关于一次同余式 组的解法完全一致。从此，中国古代数学的这一创造逐渐受到世界学者的瞩目，并在西方数学史著作中正式被称为“中国剩余定理”。2022-8-5计算机应用技术研究所计算机应用技术研究所92&中国余数定理中国余数定理2022-8-5计算机应用技术研究所计算机应用技术研究所93&证明证明如何用算法步骤表示中国剩余定理？2022-8-5计算机应用技术研究所计算机应用技术研究所94&中国剩余定理中国剩余定理p 第一步:求各
25、除数的最小公倍数；p 第二步:求各除数的基础数；p 第三步：求各基础数和；p 第四步:求基准数(最小的，只有一个)；p 第五步:求适合条件的数X。2022-8-5计算机应用技术研究所计算机应用技术研究所95&例题例题&同余算术及其运用同余算术及其运用4 同余关系及其运算同余关系及其运算4 同余方程与方程组同余方程与方程组J 整数加密算法整数加密算法2022-8-5计算机应用技术研究所计算机应用技术研究所973.3 集合定义的自然数和归纳法证明集合定义的自然数和归纳法证明&仿射加密算法仿射加密算法为防止机密信息被泄露或破坏，需采用数据加密技术对其进行保护。数据加密的基本思想是对原始数据加以伪装，
26、使非法接入者无法理解信息的真正含义，基本过程就是对原来为明文信息或数据按某种算法进行处理，使其成为不可读的一段代码，称为密文，使其只能在输入相应密钥之后才能显示出本来内容。2022-8-5计算机应用技术研究所计算机应用技术研究所98&仿射加密算法仿射加密算法2022-8-5计算机应用技术研究所计算机应用技术研究所99&仿射加密算法仿射加密算法仿射加密算法2022-8-5计算机应用技术研究所计算机应用技术研究所100&例题例题【例】对“WELCOME TO HEFEI”进行加密 首先用数字代替字母，然后使用加密函数 fp=（p+3）mod 26代替翻译成字母后，得到获得到的加密信息为：“ZHOF
27、RPH VR KHIHL”。具体过程如下：2022-8-5计算机应用技术研究所计算机应用技术研究所101&RSARSA算法算法RSA算法由三位数学家Rivest、Shamir和Adleman于1977年共同提出，是至今最为广泛使用的非对称加密算法，特别适合于对通过互联网传送的数据进行加密，通常于数字签名等场合。RSA算法使用整数模余运算性质生成公钥和私钥，并进行加密和解密。RSA算法原理基于欧拉定理和费马小定理，为此首先介绍这两个定理。2022-8-5计算机应用技术研究所计算机应用技术研究所1023.3 集合定义的自然数和归纳法证明集合定义的自然数和归纳法证明&欧拉定理欧拉定理2022-8-5
28、计算机应用技术研究所计算机应用技术研究所103&证明证明2022-8-5计算机应用技术研究所计算机应用技术研究所104&费马小定理费马小定理判定整数p为素数的一个重要方法是证明它不能被任何小于或等于其平方根的素数整除。但是，这种判定方法的效率并不高。法国数学家费马给出一个更为有效的方法，称之为费马小定理。2022-8-5计算机应用技术研究所计算机应用技术研究所105&证明证明2022-8-5计算机应用技术研究所计算机应用技术研究所106&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所107&RSARSA加密加密 前面已经介绍了RSA算法的基本思想，以及实现这个算法的理论基础欧
29、拉定理和费马小定理，那么如何利用RSA算法生成一个秘钥进行加密过程呢？下面就给出具体的求解过程与实例。2022-8-5计算机应用技术研究所计算机应用技术研究所108&RSARSA加密加密.密钥密钥的生成的生成p和q是属于解密信息，不可对外公开，整数n属于加密信息，需要对外公开。2022-8-5计算机应用技术研究所计算机应用技术研究所109&RSARSA加密加密.加密过程加密过程首先将每个字母翻译成相应的整数将这些由明文字母对应的整数合并成若干组，每个组分别形成一个大整数，代表一个字母段。可以使用前述的凯撒加密算法完成这项工作2022-8-5计算机应用技术研究所计算机应用技术研究所110&RSA
30、RSA加密加密.解密过程解密过程2022-8-5计算机应用技术研究所计算机应用技术研究所111&RSARSA加密加密2022-8-5计算机应用技术研究所计算机应用技术研究所112&素数素数p p和和q q的选择的选择1978年Rivest等人在关于RSA公开密钥的论文中，对p和q如何选择给出了如下的约束条件：p和q要足够长，在长度上应相差几位，且二者之差与p和q位数相近；p-1和q-1的最大公约数gcd(p-1，q-1)要尽量小；p-1和q-1均应至少含有一个大的素数因子。并把满足这些条件的素数称为。2022-8-5计算机应用技术研究所计算机应用技术研究所113&例题例题2022-8-5计算机
31、应用技术研究所计算机应用技术研究所114&例题的进一步探讨例题的进一步探讨2022-8-5计算机应用技术研究所计算机应用技术研究所115&例题例题2022-8-5计算机应用技术研究所计算机应用技术研究所116&结论结论对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。2022-8-5计算机应用技术研究所计算机应用技术研究所117
