離散數學及其應用第2章-整數與算法基礎(上)課件

1、2022/7/25計算機應用技術研究所1離散數學Discrete Mathematics 汪榮貴 教授合肥工業(yè)大學計算機與信息學院2022/7/25計算機應用技術研究所2第2章 整數與算法設計基礎（上）2022/7/25 同余算術及其運用2 算法設計的基本知識3 整數的基本知識1 算法設計策略與應用4 本章學習內容2022/7/25計算機應用技術研究所4整數的基本知識 整數的基本知識 整數與整除算法 整數的因數分解 素數的性質與查找2022/7/25計算機應用技術研究所6整數在第一章，我們得到自然數和自然數集的定義。在自然數集中加入每個非零的相反數就得到整個整數集合Z。對于整數集合Z ，有：Z

2、=,-4,-3,-2,-1,0,1,2,3,42022/7/25計算機應用技術研究所7整除的概念與性質2022/7/25計算機應用技術研究所8素數（質數）與合數如何判斷一個數是不是素數呢？目前使用較有效的方法是試除法。用試除法判斷一個自然數a是不是素數時，用各個素數從小到大依次去除a，如果到某一個素數正好整除，這個a就可以斷定不是素數；如果不能整除，當不完全商又小于這個素數時，就不必再繼續(xù)試除，可以斷定a必然是素數。2022/7/25計算機應用技術研究所9整數相關的定理怎么證明以上的定理呢？2022/7/25計算機應用技術研究所10例 題2022/7/25計算機應用技術研究所11例題2022/

3、7/25計算機應用技術研究所12整數相關的定理2022/7/25計算機應用技術研究所13總結從上述定理的證明過程可以看出，整除是帶余除法中余數等于 0 的情形。 因此，帶余除法可以看成是對整除的一種推廣。 事實上，還可通過帶余除法的概念來定義和理解整除的概念，即 a 能夠整除 b 的當且僅當 b 除以 a 的余數為 0。 整數的因數分解 整數與整數除法 整數的因數分解 素數的性質和查找2022/7/25計算機應用技術研究所15 因數分解的概念把一個整數分解成兩個或更多的除1外的整數相乘的過程。這些整數稱為這個數的因數。2022/7/25計算機應用技術研究所16 公因數與公倍數這兩個問題該怎么求

4、解呢？這就用到了下面介紹的公因數與公倍數的概念2022/7/25計算機應用技術研究所17 最大公因數與最小公倍數的概念最小公倍數最大公因數自然數1可以整除任意整數，因此對于任意兩個整數，它們的公因數總是存在的。 公因數表達的是兩個整數的共同部分，通常需要考察兩個整數之間的共同部分最大值能達到多少，故有所謂最大公因數的概念。同樣，對于任意兩個整數，這兩個整數的乘積就是它們的公倍數，因此，公倍數總是存在的，需要著重考察的通常式公倍數的最小值，因而有最小公倍數的概念。 2022/7/25計算機應用技術研究所18 最大公因數與最小公倍數的概念前面已經學習了兩個整數的最大公因數與最小公倍數的概念，現在推

5、廣到K個整數的情況2022/7/25計算機應用技術研究所19 最大公因數與最小公倍數的概念2022/7/25計算機應用技術研究所20最大公因數與最小公倍數的關系通過最大公因數與最小公倍數的定義，我們可以看到這二者是通過兩個自然數的某種運算得到的，那么這二者之間是否存在某種關系呢？2022/7/25計算機應用技術研究所21 最大公因數的性質帶余除法最大公因數在帶余除法中有一個比較好的性質，在這里加以介紹2022/7/25計算機應用技術研究所22 例題2022/7/25計算機應用技術研究所23 輾轉相除法輾轉相除法是一種古老的算法，在國際上也稱為歐幾里得算法，起初源于歐幾里得幾何原本第卷命題，在中

6、國也稱為更相減損術，最初來源于九章算術方田第六題。2022/7/25計算機應用技術研究所24輾轉相除法輾轉相除法步驟:第一步:輸入兩個正整數m,n(mn);第二步:計算m除以n所得的余數r;第三步: m=nn=r;第四步:若r=0,則m,n的最大公約數等于m;否則轉到第二步;第五步:輸出最大公約數m。用程序框圖表示出來:2022/7/25計算機應用技術研究所25輾轉相除法2022/7/25計算機應用技術研究所26輾轉相除法2022/7/25計算機應用技術研究所27 例題做輾轉相除法從后向前迭代2022/7/25計算機應用技術研究所28輾轉相除法上述定理表明，整數 a 和 b 的最大公因數可以表

7、示為它們的一個線性組合。這就給出了最大公因式一種具體表達形式，這種表達形式對于考察最大公因數的性質具有非常重要的作用。例如，使用上述線性組合表達式，可得到最大公因數下述性質： 現在我們舉個例子對上述定理進行深入地了解。例如，gcd(56,24)=8,因此有m=-1,n=2使得：8=56*（-1）+24*2通過這個例子我們可以看到，8不僅是56與24兩個整數的最大公因數，也是這兩個整數的所有因數的倍數，這才是這個定理所要告訴我們的地方。 互素的概念從整除的角度看，兩個整數的公因數表達的是這兩個整數共性成分。如果兩個整數的最大公因數為1，則表明這兩個整數除1之外沒有任何額外的共性成分。因此，從結構

8、上看，這兩個整數之間具有很強的獨立性。這種很強的獨立性我們稱之為互素。下面就介紹互素的概念。2022/7/25計算機應用技術研究所30 例題【例題2.9】小于12的哪些正整數與12互素？【例題2.10】判斷整數10, 17和21是否兩兩互素，整數10, 19和24是否兩兩互素。2022/7/25計算機應用技術研究所31前面介紹了互素的概念，從互素的概念出發(fā)，能夠得到一些比較好的性質，下面一一介紹 互素的性質2022/7/25計算機應用技術研究所32 互素性質的證明2022/7/25計算機應用技術研究所33 互素性質的證明2022/7/25計算機應用技術研究所34 例題2022/7/25計算機應

9、用技術研究所35 算術基本定理算術基本定理是初等數論中一條非?；竞椭匾亩ɡ恚褜ψ匀粩档难芯哭D化為對其最基本的元素一素數的研究。它所體現的唯一因子分解的思想，在現代交換環(huán)理論中起著非常重要的作用。唯一因子分解的思想從本質上講是指以下兩種性質:“存在性和唯一性”。所謂“存在性”就是指一個元素可以分解為有限多個不可約因子的乘積;“唯一性”是指這種分解表示在某種意義上來說是唯一的。唯一因子分解的思想最初作為一個自然數的性質而出現，這個性質就是通常所說的算術基本定理。2022/7/25計算機應用技術研究所36引理2022/7/25計算機應用技術研究所37算術基本定理整數素數分解的存在性與唯一性2

10、022/7/25計算機應用技術研究所38素冪分解式整數的素冪分解式給出了整數一種基于素數的結構表達，在數論研究中具有非常重要的作用。2022/7/25計算機應用技術研究所39例題【例1】寫出51480的素冪分解式?！纠?】寫出10個連續(xù)的正整數，使他們都是合數。2022/7/25計算機應用技術研究所40素冪分解式上面這個定理表明，可以使用其素冪分解式計算兩個整數的最大公約數和最小公倍數，還可以證明最大公約數和最小公倍數之間的關系。2022/7/25計算機應用技術研究所41例題【例2】求132與240的最大公因數與最小公倍數。 整數的基本知識 整數與整數除法 整數的因數分解 素數的性質與查找20

11、22/7/25計算機應用技術研究所43素數的性質如果一個問題的求解過程復雜度遠高于其設立過程復雜度，那么它就有潛力被設計為一個密碼學算法。至于像公鑰密碼這種天才的構想，就需要這個問題難的同時還具有一些特殊特性。目前為止，公鑰密碼在本質上也就RSA和橢圓曲線兩套內核而已，在二者中素數都有很重要的地位。那素數又有哪些比較好的性質值得我們去學習呢？要好好學習這些性質！這也是后面我們學習加密算法的基礎。2022/7/25計算機應用技術研究所44 素數的性質【定理2.15】假設p是任意一個給定的素數，則它與其它任意整數a之間的關系是：要么p與a互素，要么p能夠整除a。素數的一個非常獨特性質是它與其它整數

12、之間具有如上非常簡單而直接的關系，這種簡單直接的關系是使用素數考察整數性質的基礎。2022/7/25計算機應用技術研究所45 素數的性質2022/7/25計算機應用技術研究所46 素數的查找下面討論素數的計數問題。首先考慮在整個正整數集合中，到底有多少個素數？下面的定理給出了答案：【定理2.17】正整數集合中的素數有無窮多個。2022/7/25計算機應用技術研究所47現在我們考慮給定一個正整數集合，如何找到這個集合中的所有素數呢？ 素數的查找2022/7/25計算機應用技術研究所48 【例1】判斷137和157是否是素數。 例題2022/7/25計算機應用技術研究所49 愛氏曬法下面再介紹另外

13、一種查找指定正整數集合素數的方法，它來源于定理2.18，但較之更為方便簡潔，讀者閱讀之后便會有這樣的感覺。愛氏篩法：2022/7/25計算機應用技術研究所50 例 題2022/7/25計算機應用技術研究所51 例題2022/7/25計算機應用技術研究所52 總結與拓展2022/7/25計算機應用技術研究所53本節(jié)結束！2022/7/25整數的基本知識1算法設計的基本知識3同余算術及其運用2算法設計策略與應用4 本章學習內容2022/7/25計算機應用技術研究所55同余算術及其運用 同余算術及其運用 同余關系及其運算 同余方程與方程組 整數加密算法2022/7/25計算機應用技術研究所57 同余

14、算術的產生背景 1801年,24 歲的高斯(1777-1855)出版了專著算術研究,在其中他提出了模演算法,以統(tǒng)一的觀點處理了數論中的許多問題,從而開創(chuàng)了數論研究的新時代。 同余算術是整理理論一個重要發(fā)展并構成初等數論的理論核心，它從在一種比整除約束更為寬松的條件下考察整數的運算及性質并得到很多非常精彩的數論成果，這些成果在整數加密算法設計等多個領域得到廣泛應用。2022/7/25計算機應用技術研究所58 同余關系及其運算對于任一給定的正整數m，通過考察所有整數除以m所得余數的差異，把所有具有相同余數的整數歸為一類，則可將所有整數分為m個基本類型。基于上述思想，我們給出同余關系的定義。2022

15、/7/25計算機應用技術研究所59 同余關系的判定定理 有了同余關系的概念后，對于給定的兩個整數，我們如何準確判定這兩個整數是否具有同余關系呢？這就用到了我們下面要講的同余關系的判定定理2022/7/25計算機應用技術研究所60 同余關系的判定定理同余關系的判定定理也有第二種表示方式：在現實生活中，時鐘的鐘點讀數模12同余或者模24同余，分和秒讀數模60同余，星期幾的讀法則是模7同余。2022/7/25計算機應用技術研究所61 同余關系的性質同余關系的保加性和保乘性：2022/7/25計算機應用技術研究所62 同余關系的性質同余關系的運算律：2022/7/25計算機應用技術研究所63 同余關系

16、的性質 同余關系的性質2022/7/25計算機應用技術研究所65 例題2022/7/25計算機應用技術研究所66 例題2022/7/25計算機應用技術研究所67 同余類前面已經介紹了同于關系的相關知識，利用同余關系可以實現對整數集合的劃分，得到的結果就是劃分為m個互不相交的子集合。2022/7/25計算機應用技術研究所68 同余類的性質2022/7/25計算機應用技術研究所69 同余類的性質上述定理表明，每個整數必定屬于且僅屬于其中一個剩余類，屬于同一個剩余類的任意兩個整數都是模m同余的，屬于不同剩余類的任意兩個整數不可能是模m同余的。2022/7/25計算機應用技術研究所70 同余類的加法與

17、乘法2022/7/25計算機應用技術研究所71 例題2022/7/25計算機應用技術研究所72 例題2022/7/25計算機應用技術研究所73 例題2022/7/25計算機應用技術研究所74 完全剩余系2022/7/25計算機應用技術研究所75 模m簡化同余類2022/7/25計算機應用技術研究所76 歐拉函數2022/7/25計算機應用技術研究所77 歐拉函數2022/7/25計算機應用技術研究所78 例題 例題 同余算術及其應用 同余關系及其運算 同余方程與方程組 整數加密算法2022/7/25計算機應用技術研究所81 同余方程 孫子算經中的題目：有物不知其數，三個一數余二，五個一數余三，

18、七個一數又余二，問該物總數幾何？孫子算經中的解法：三三數之，取數七十，與余數二相乘；五五數之，取數二十一，與余數三相乘；七七數之，取數十五，與余數二相乘。 這其實就是利用方程的思想求解帶余除法問題，我們現在給出解決這類問題的數學方法。2022/7/25計算機應用技術研究所82 同余方程解的存在性如何求解一個同余方程，即該方程是否存在解？2022/7/25計算機應用技術研究所83 證明2022/7/25計算機應用技術研究所84 例題2022/7/25計算機應用技術研究所85化1法 在解一元一次方程的時候，經常將等式兩邊同時乘以未知數一次項系數的倒數，將未知數一次項的系數化為1，由此實現對方程組的

19、求解?，F通過類似方法對同余方程求解?；?法2022/7/25計算機應用技術研究所862022/7/25計算機應用技術研究所87 證明2022/7/25計算機應用技術研究所88 例題2022/7/25計算機應用技術研究所89 例題2022/7/25計算機應用技術研究所903.3 集合定義的自然數和歸納法證明同余方程組2022/7/25計算機應用技術研究所91 中國余數定理中國余數定理,也稱中國剩余定理，孫子剩余定理。 從孫子算經到秦九韶數書九章對一次同余式問題的研究成果，在19世紀中期開始受到西方數學界的重視。1852年，英國傳教士偉烈亞力向歐洲介紹了 孫子算經的“物不知數”題和秦九韶的“大衍求

20、一術”；1876年，德國人馬蒂生指出，中國的這一解法與西方19世紀高斯算術探究中關于一次同余式 組的解法完全一致。從此，中國古代數學的這一創(chuàng)造逐漸受到世界學者的矚目，并在西方數學史著作中正式被稱為“中國剩余定理”。2022/7/25計算機應用技術研究所92 中國余數定理2022/7/25計算機應用技術研究所93 證明當以上定義的同余方程組中所有模兩兩互素時，方程組一定有唯一的一組解。如何用算法步驟表示中國剩余定理？2022/7/25計算機應用技術研究所94 中國剩余定理第一步: 求各除數的最小公倍數；第二步: 求各除數的基礎數；第三步： 求各基礎數和；第四步: 求基準數(最小的，只有一個)；第

21、五步: 求適合條件的數X。2022/7/25計算機應用技術研究所95 例題同余算術及其運用 同余關系及其運算 同余方程與方程組 整數加密算法2022/7/25計算機應用技術研究所973.3 集合定義的自然數和歸納法證明 仿射加密算法為防止機密信息被泄露或破壞，需采用數據加密技術對其進行保護。數據加密的基本思想是對原始數據加以偽裝，使非法接入者無法理解信息的真正含義，基本過程就是對原來為明文信息或數據按某種算法進行處理，使其成為不可讀的一段代碼，稱為密文，使其只能在輸入相應密鑰之后才能顯示出本來內容。2022/7/25計算機應用技術研究所98仿射加密算法2022/7/25計算機應用技術研究所99

22、 仿射加密算法仿射加密算法2022/7/25計算機應用技術研究所100 例題【例】對“WELCOME TO HEFEI”進行加密 首先用數字代替字母，然后使用加密函數 fp=（p+3）mod 26代替翻譯成字母后，得到獲得到的加密信息為：“ZHOFRPH VR KHIHL”。具體過程如下： 2022/7/25計算機應用技術研究所101 RSA算法RSA算法由三位數學家Rivest、Shamir和Adleman于1977年共同提出，是至今最為廣泛使用的非對稱加密算法，特別適合于對通過互聯(lián)網傳送的數據進行加密，通常于數字簽名等場合。RSA算法使用整數模余運算性質生成公鑰和私鑰，并進行加密和解密。R

23、SA算法原理基于歐拉定理和費馬小定理，為此首先介紹這兩個定理。2022/7/25計算機應用技術研究所1023.3 集合定義的自然數和歸納法證明歐拉定理2022/7/25計算機應用技術研究所103 證明2022/7/25計算機應用技術研究所104 費馬小定理判定整數p為素數的一個重要方法是證明它不能被任何小于或等于其平方根的素數整除。但是，這種判定方法的效率并不高。法國數學家費馬給出一個更為有效的方法，稱之為費馬小定理。2022/7/25計算機應用技術研究所105 證明2022/7/25計算機應用技術研究所106 例題2022/7/25計算機應用技術研究所107RSA加密 前面已經介紹了RSA算法的基本思想，以及實現這個算法的理論基礎歐拉定理和費馬小定理，那么如何利用RSA算法生成一個秘鑰進行加密過程呢？下面就