第1章整除《信息安全數(shù)學基礎（第2版）》整除主要內(nèi)容本章主要介紹數(shù)論理論中的整除。涉及整除與帶余除法、素數(shù)、公因數(shù)與公倍數(shù)、輾轉相除、算術基本定理等概念與性質(zhì)。另外，還會討論連分數(shù)及其在公鑰密碼RSA攻擊中的應用，最后討論對于密碼學有重要價值的完全數(shù)、梅森素數(shù)和費馬素數(shù)等概念。學習要求：掌握整除和帶余除法的概念與性質(zhì)，以及相關的計算方法及應用；掌握最大公因子和輾轉相除的概念與性質(zhì)，以及相關的計算方法及應用；了解連分數(shù)的概念與性質(zhì)及其在RSA的Wiener攻擊中的應用；了解完全數(shù)、梅森素數(shù)和費馬素數(shù)的概念及相關性質(zhì)。2CONTENTS目錄整除整除與帶余除法1最大公因子與輾轉相除法2算數(shù)基本定理3連分數(shù)4完全數(shù)、梅森素數(shù)和費馬素數(shù)53第1節(jié)整除與帶余除法整除與帶余除法4整除與帶余除法5主要內(nèi)容本節(jié)主要介紹和整除與帶余除法相關的基礎定義和定理，涉及內(nèi)容如下：倍數(shù)、因子和真因子的定義和相關定理；良序定理；整除中被除數(shù)、商和余數(shù)的定義和相關定理；奇數(shù)和偶數(shù)的定義和相關定理；素數(shù)和合數(shù)的定義和相關定理。

整除與帶余除法6

整除與帶余除法7

整除與帶余除法8

整除與帶余除法9第2節(jié)最大公因子與輾轉相除法最大公因子與輾轉相除法10最大公因子與輾轉相除法11主要內(nèi)容本節(jié)首先介紹最大公因子的概念，隨后引出求兩數(shù)最大公因子的輾轉相除法，之后則介紹與最大公因子相關的定義和定理，最后則介紹最小公倍數(shù)。所涉及內(nèi)容如下：公因子和最大公因子的定義；互素的概念；輾轉相除法；線性組合等定義和定理；公倍數(shù)和最小公倍數(shù)的定義和相關定理。1.2最大公因子與輾轉相除法

定義1.2.1

設a1,a2,…,an是n個不全為零的整數(shù).若整數(shù)d是它們之中每一個數(shù)的因子,那么d就稱為a1,a2,…,an的一個公因子.在整數(shù)a1,a2,…,an的所有公因子中最大的一個稱為最大公因子,記作(a1,a2,…,an)或者gcd(a1,a2,…,an).特別地,若(a1,a2,…,an)=1,我們稱a1,a2,…,an互素(或互質(zhì)).

定理1.2.1

設a,b,c是任意三個不全為零的整數(shù),且a=bq+c,其中q是整數(shù),則(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節(jié)算術基本定理算術基本定理18算術基本定理19主要內(nèi)容本節(jié)首先介紹與素數(shù)運算相關的定理和推論，隨后引出算術基本定理，該定理用于整數(shù)的分解，最后介紹標準分解式和相關定理。所涉及的內(nèi)容總結如下：素數(shù)運算的相關定理和推理；算術基本定理；素數(shù)的標準分解式及相關定理。

算術基本定理20

算術基本定理21

算術基本定理22

算術基本定理23第4節(jié)連分數(shù)連分數(shù)24連分數(shù)25主要內(nèi)容本節(jié)主要介紹連分數(shù)，首先分別介紹有限連分數(shù)和無限連分數(shù)的相關定義，并介紹了它們的簡單連分數(shù)和漸進分數(shù)。之后則介紹了相關定理，包括漸進分數(shù)和簡單連分數(shù)在滿足特定條件時的情況。最后則通過RSA算法中的Wiener攻擊介紹了連分數(shù)在現(xiàn)實中的應用。內(nèi)容總結如下：有限連分數(shù)和無限連分數(shù)，以及簡單連分數(shù)和漸進分數(shù)的定義；漸進分數(shù)和簡單連分數(shù)的相關定理；循環(huán)連分數(shù)；RSA公鑰加密算法和Wiener攻擊。

連分數(shù)26

連分數(shù)27

連分數(shù)28

連分數(shù)29

連分數(shù)30

連分數(shù)31

連分數(shù)32

連分數(shù)33

連分數(shù)應用34

連分數(shù)應用35第5節(jié)*梅森素數(shù)和費馬素數(shù)梅森素數(shù)和費馬素數(shù)36梅森素數(shù)和費馬素數(shù)37主要內(nèi)容本節(jié)分別首先引出完全數(shù)的概念，并介紹了相關背景定理，隨后分別介紹梅森素數(shù)和費馬素數(shù)的定義和相關定理。內(nèi)容總結如下：完全數(shù)及其相關定理；梅森數(shù)和梅森素數(shù)；費馬數(shù)和費馬素數(shù)；

梅森素數(shù)和費馬素數(shù)38

梅森素數(shù)和費馬素數(shù)39

梅森素數(shù)和費馬素數(shù)40小結本章小結數(shù)論與編碼理論、密碼學等信息科學領域具有緊密的聯(lián)系，而整除是數(shù)論理論的重要基礎.本章對整數(shù)整