信息安全数学基础 第2版 课件 第1章-整除

第1章整除《信息安全数学基础（第2版）》整除主要内容本章主要介绍数论理论中的整除。涉及整除与带余除法、素数、公因数与公倍数、辗转相除、算术基本定理等概念与性质。另外，还会讨论连分数及其在公钥密码RSA攻击中的应用，最后讨论对于密码学有重要价值的完全数、梅森素数和费马素数等概念。学习要求：掌握整除和带余除法的概念与性质，以及相关的计算方法及应用；掌握最大公因子和辗转相除的概念与性质，以及相关的计算方法及应用；了解连分数的概念与性质及其在RSA的Wiener攻击中的应用；了解完全数、梅森素数和费马素数的概念及相关性质。2CONTENTS目录整除整除与带余除法1最大公因子与辗转相除法2算数基本定理3连分数4完全数、梅森素数和费马素数53第1节整除与带余除法整除与带余除法4整除与带余除法5主要内容本节主要介绍和整除与带余除法相关的基础定义和定理，涉及内容如下：倍数、因子和真因子的定义和相关定理；良序定理；整除中被除数、商和余数的定义和相关定理；奇数和偶数的定义和相关定理；素数和合数的定义和相关定理。

整除与带余除法6

整除与带余除法7

整除与带余除法8

整除与带余除法9第2节最大公因子与辗转相除法最大公因子与辗转相除法10最大公因子与辗转相除法11主要内容本节首先介绍最大公因子的概念，随后引出求两数最大公因子的辗转相除法，之后则介绍与最大公因子相关的定义和定理，最后则介绍最小公倍数。所涉及内容如下：公因子和最大公因子的定义；互素的概念；辗转相除法；线性组合等定义和定理；公倍数和最小公倍数的定义和相关定理。1.2最大公因子与辗转相除法

定义1.2.1

设a1,a2,…,an是n个不全为零的整数.若整数d是它们之中每一个数的因子,那么d就称为a1,a2,…,an的一个公因子.在整数a1,a2,…,an的所有公因子中最大的一个称为最大公因子,记作(a1,a2,…,an)或者gcd(a1,a2,…,an).特别地,若(a1,a2,…,an)=1,我们称a1,a2,…,an互素(或互质).

定理1.2.1

设a,b,c是任意三个不全为零的整数,且a=bq+c,其中q是整数,则(a,b)=(b,c).证明:（思路）

因为(a,b)|a,(a,b)|b,又c=a−bq,所以(a,b)|c=>(a,b)≤(b,c)……最大公因子与辗转相除法12

最大公因子与辗转相除法13最大公因子与辗转相除法

14

最大公因子与辗转相除法15

最大公因子与辗转相除法16

最大公因子与辗转相除法17第3节算术基本定理算术基本定理18算术基本定理19主要内容本节首先介绍与素数运算相关的定理和推论，随后引出算术基本定理，该定理用于整数的分解，最后介绍标准分解式和相关定理。所涉及的内容总结如下：素数运算的相关定理和推理；算术基本定理；素数的标准分解式及相关定理。

算术基本定理20

算术基本定理21

算术基本定理22

算术基本定理23第4节连分数连分数24连分数25主要内容本节主要介绍连分数，首先分别介绍有限连分数和无限连分数的相关定义，并介绍了它们的简单连分数和渐进分数。之后则介绍了相关定理，包括渐进分数和简单连分数在满足特定条件时的情况。最后则通过RSA算法中的Wiener攻击介绍了连分数在现实中的应用。内容总结如下：有限连分数和无限连分数，以及简单连分数和渐进分数的定义；渐进分数和简单连分数的相关定理；循环连分数；RSA公钥加密算法和Wiener攻击。

连分数26

连分数27

连分数28

连分数29

连分数30

连分数31

连分数32

连分数33

连分数应用34

连分数应用35第5节*梅森素数和费马素数梅森素数和费马素数36梅森素数和费马素数37主要内容本节分别首先引出完全数的概念，并介绍了相关背景定理，随后分别介绍梅森素数和费马素数的定义和相关定理。内容总结如下：完全数及其相关定理；梅森数和梅森素数；费马数和费马素数；

梅森素数和费马素数38

梅森素数和费马素数39

梅森素数和费马素数40小结本章小结数论与编码理论、密码学等信息科学领域具有紧密的联系，而整除是数论理论的重要基础.本章对整数整