《信息安全数学基础.》全套教学课件.pptx

信息安全数学基础全套可编辑PPT课件

数论部分数论是研究整数性质的一个数学分支。整数的基本元素是素数，所以数论的本质是对素数性质的研究。数论被称为“纯而又纯的数学”。高斯曾经说过“数学是科学的皇后，数论是数学中的皇冠”。数学家们把数论中一些悬而未决的疑难问题，称为“皇冠上的明珠”。2

小故事德国数学家高斯集前人大成，写了一本书叫做《算术探讨》，1800年寄给了法国科学院，但是法国科学院拒绝了高斯的这部杰作，高斯只好在1801年自己发表了这部著作。这部书开始了现代数论的新纪元。在《算术探讨》中，高斯把过去研究整数性质所用的符号标准化，把当时的定理系统化并进行了推广，把要研究的问题和方法进行了分类，还引进了新的方法。3

4第1章整数的整除与唯一分解1.1带余除法和整除1.2整数的表示1.3最大公因子与辗转相除法1.4最小公倍数1.5整数的唯一分解1.6素数有无穷多1.7麦什涅数与费马数*1.8素数的著名问题*

5重点内容概念最大公因子、互素定理整数唯一分解算法欧几里德算法（辗转相除法）扩展的欧几里德算法

61.1带余除法和整除正整数（如1,2,3,…）、负整数（如–1,–2,–3,…）与零（0）统称为整数。通常，用符号Z={0,±1,±2,±3,…}表示整数集合，零与正整数称为自然数。两个整数的和、差、积仍然是整数，但两个整数相除得到的商未必是整数。为此，我们引入整除、带余除法概念。

7定义1.1任意两个整数a,b，其中b≠0，如果存在一个整数q，使等式a=bq(1.1)成立，我们就说b整除a，或a被b整除，记为b|a。此时，称b为a的因子，a为b的倍数。0是任何非零整数的倍数，1是任何整数的因子。

8若b|a，且b≠1,b≠a，就称b是a的真因子；否则，就称b为a的平凡因子，任何非零整数是自身的因子和倍数。式(1.1)中的整数q，常写成a/b或。如果不存在整数q满足式(1.1)，我们就说b不整除a，记为ba。a=bq(1.1)

9设a,b,c为整数，根据整除的定义，不难得到以下性质：1.若c|b,b|a，则c|a；（传递性）2.若b|a，c≠0，则cb|ca；3.若cb|ca，则b|a；4.若b|a且a≠0，则|b|≤|a|；5.若b|a,a≠0，则；6.若c|a,c|b，则对任意整数m,n，有c|ma±nb。

10一般地，有下面的余数定理。定理1.1（带余除法）设a,b是两个整数，其中b0，则存在唯一的整数q和r，使得a=bq+r,0≤rb(1.2)成立。证明考虑b的整数倍序列…,–3b,–2b,–b,0,b,2b,3b,…，在该序列中，整数a必位于某两个相邻的整数之间，设该区间为[qb,(q+1)b),即存在整数q，使得qb≤a(q+1)b成立。

11令r=a–qb，则有a=qb+r,0≤rb。进一步，具有上述性质的整数q,r是唯一的。不妨假设存在另外一组整数q1,r1，满足a=bq1+r1,0≤r1b。(1.3)将式(1.3)与式(1.2)相减，得b(q–q1)=(r1–r)，所以b|q–q1|=|r1–r|。(1.4)等式(1.4)的左边为b的倍数，即b|q–q1|=0或b|q–q1|≥b；

12而由于0≤r,r1b，则等式(1.4)的右边必为0≤|r1–r|b。因此，要使等式(1.4)成立，只有q=q1，r1=r。□式(1.2)称为带余除法，或称为欧几里德除法。当r=0时，称q为a除以b的完全商；当r≠0时，称q为a除以b的不完全商；通常将q通称为商。r称为a除以b得到的余数，余数都是非负整数。a=bq+r,0≤rb(1.2)b|q–q1|=|r1–r|