5數(shù)論簡介

1、,離散數(shù)學(xué),第5章 數(shù) 論 簡 介,,數(shù)論是數(shù)學(xué)里研究整數(shù)的一個分支。傳統(tǒng)上，由于它的抽象本質(zhì)大于它的應(yīng)用，因此將數(shù)論看做是數(shù)學(xué)的一個純粹的分支。英國數(shù)學(xué)家G. H. Hardy將數(shù)論看做是一個漂亮的、但不實用的數(shù)學(xué)分支。然而，在20 世紀后期，數(shù)論在密碼系統(tǒng)（為了通信安全的系統(tǒng)）中得到了極大的應(yīng)用。,內(nèi)容,基本的數(shù)論定義，如“整除”和“素數(shù)”。因子分解、最大公因子和最小公倍數(shù)。整數(shù)的表示和一些整數(shù)算術(shù)的算法。用來計算最大公因

2、子的歐幾里得算法用于安全通信的RSA 系統(tǒng)。,5.1 因子,定義5.1.1 令n 和d 是整數(shù)，d ≠ 0。如果存在一個整數(shù)q 滿足n = dq，稱d 整除n。稱q 是商，d是n 的一個因子或者約數(shù)。如果d 整除n，記做d | n。如果d 不能整除n，記做d | n。,,例5.1.2,由于21 = 3*7，3 整除21，記做3 | 21。商是7，稱3 是21 的一個因子或者約數(shù)。注意到如果n 和d 是正整數(shù)，且d | n，那么d ≤

3、 n。（如果d | n ，那么存在一個整數(shù)q 使得n = dq。由于n 和d 是正整數(shù)，1 ≤ q。因此，d ≤ dq = n。）無論整數(shù)d > 0 是否整除整數(shù)n，存在一個惟一的整數(shù)q（商）和r（余數(shù)）滿足n = dq + r，0 ≤ r < d）。余數(shù)r 等于0 當(dāng)且僅當(dāng)d可以整除n。,定理5.1.3,令m、n 和d 是正整數(shù)。如果d | m 且d | n， 那么d | (m + n)。(b) 如果d | m

4、且d | n， 那么d | (m - n)。(c) 如果d | m，那么d | mn。,定義5.1.4,對于一個大于1 的整數(shù)，它的因子只有其自身和1 被稱為素數(shù)。一個大于1 的不是素數(shù)的整數(shù)稱為合數(shù)。 整數(shù)23 是一個素數(shù)，因為只有其本身和1 是它的因子。整數(shù)34 是合數(shù)因為它可以被17整除，17 既不是1 也不是34。,,如果整數(shù)n > 1是合數(shù)，那么它有一個正因子d 既不是1 也不是其自身。由于d 是正的且d ≠ 1，

5、d > 1。因為d 是n 的一個因子，d ≤ n。由于d ≠ n，d < n。因此，判斷一個正整數(shù)n 是否是合數(shù)，只需要試驗一下整數(shù)2, 3,..., n - 1中的任何一個是否可以整除n。如果序列中存在某個整數(shù)能整除n，那么n 是合數(shù)。如果序列中沒有整數(shù)可以整除n，那么n 是素數(shù)。,例5.1.6,序列 2, 3, 4, 5,..., 41, 42中沒有數(shù)可以整除43；因此，43 是一個素數(shù)。檢查序列2, 3,

6、4, 5,..., 449, 450中451 的可能的因子。11 可以整除451（451 = 11·41）；因此，451 是一個合數(shù)。,定理5.1.7,一個大于1 的正整數(shù)n 是合數(shù)當(dāng)且僅當(dāng)它有一個因子d，滿足2 ≤ d ≤ 。證明 必須證明如果n 是合數(shù)，那么n 有一個因子d，滿足2 ≤ d ≤ ，而且如果n 有一個因子d，滿足2 ≤ d ≤ ，那么n 是合數(shù)。,算法5.1.8

7、時間為?( ),判斷一個整數(shù)是否是素數(shù)判斷一個整數(shù)n > 1 是否是素數(shù)。如果n 是素數(shù)，算法返回0。如果n 是合數(shù)，算法返回一個因子d 滿足2 ≤ d ≤ 。為了判斷d 是否整除n，算法檢查n 被d 整除后余數(shù)n mod d 是否是0。,例5.1.10,如果一個合數(shù)n 輸入到算法5.1.8 中，返回的因子是一個素數(shù)；也就是算法5.1.8 中返回一個合數(shù)的素數(shù)因子。如果輸入n = 1274 到算法5.1.8

8、中，算法返回素數(shù)2，因為素數(shù)2 整除1274，即1274 = 2·637如果現(xiàn)在輸入n = 637 到算法5.1.8 中，算法返回素數(shù)7，因為素數(shù)7 整除637，即637 = 7·91如果現(xiàn)在輸入n = 91 到算法5.1.8 中，算法返回素數(shù)7，因為素數(shù)7 整除91，即91 = 7·13如果現(xiàn)在輸入n = 13 到算法5.1.8 中，算法返回0，因為13 是素數(shù)。把前面的過程組合起來得到1247

9、是素數(shù)的乘積： 1274 = 2·637 = 2·7·91 = 2·7·7·13,定理5.1.11,任何一個大于1 的整數(shù)可以寫成素數(shù)乘積的形式。此外，如果這些素數(shù)按非遞減順序?qū)懗?，這種分解是惟一的。 用符號表示，如果 n = p1p2?pi 其中pk 是素數(shù)，p1 ≤ p2 ≤?≤ pi，且 n = p1’ p2’?pj’

10、 其中pk’ 是素數(shù)，p1’ ≤ p2 ’ ≤?≤ pj ’ ，那么 i = j，并且 pk = pk’對所有的k = 1,..., i,定理5.1.12 素數(shù)的個數(shù)是無限的。,證明 只要能夠證明如果p 是素數(shù)，存在一個比p 大的素數(shù)就夠了。為此，令 p1, p2,..., pn 代表所有比p 小或等于p 的不同素數(shù)。考慮整數(shù) m = p1 p2?pn + 1

11、 注意到m被pi 除時，余數(shù)是1： m = piq + 1, q = p1 p2?pi-1 pi+1?pn 因此，對所有的i = 1 到n，pi 不能整除m。令p‘ 表示m 的一個素數(shù)因子（m 自身可以是也可以不是素數(shù)），那么p’ 不等于任何一個pi，i = 1, 2,..., n。由于p1, p2,..., pn 是所有比p 小或相等的素數(shù)，那么必須有p‘> p。證明完成。,例5.1.13,如何生成一個比1

12、1 大的素數(shù)。先列出所有小于或等于11 的素數(shù) 2, 3, 5, 7, 11 令 m = 2·3·5·7·11 + 1 = 2311 利用算法5.1.8，發(fā)現(xiàn)2311 是素數(shù)。現(xiàn)在已經(jīng)找到了一個素數(shù)，就是2311。,最大公因子,兩個整數(shù)m和n（不全為0）的最大公因子（greatest common divisor）是所有能夠整除m 和n的最大正整數(shù)。例如，4 和6 的最大公因子是2，3

13、和8 的最大公因子是1。當(dāng)檢查分數(shù)m/n（其中m和n 是整數(shù)時）是否是最簡的時，會用到最大公因子的概念。如果m和n 的最大公因子是1，m/n 是最簡表示；否則，可以約減m/n。例如，4/6 不是最簡表示，因為4 和6 的最大公因子是2，不是1。3/8 是最簡表示，因為3 和8 的最大公因子是1。,定義5.1.14,令m和n 是整數(shù)，兩者不同時為0。m 和n 的公因子是能夠整除m和n 的整數(shù)。最大公因子記做 gcd (m,

14、 n) 是m 和n 的最大的公因子。,例5.1.15,30 的正因子是 1, 2, 3, 5, 6, 10, 15, 30105 的正因子是 1, 3, 5, 7, 15, 21, 35, 105所以30 和105 的正公因子是 1, 3, 5, 15立刻可以得出30 和105 的公因子gcd(30, 105)是15。,例5.1.16,通過仔細觀察30 和105 的素數(shù)因子來尋找它們的最大公因

15、子：30 = 2·3·5 105 = 3·5·7,定理5.1.17 例5.1.18,定義5.1.19 例5.1.20,令m 和n 是正整數(shù)。m 和n 的一個公倍數(shù)是一個可以同時被m 和n 整除的整數(shù)。最小公倍數(shù)，記做 lcm(m, n) 是m 和n 的最小的正的公倍數(shù)30 和105 的最小公倍數(shù)lcm(30, 105)是210，因為210 可以同時被30

16、和105 整除，并且經(jīng)過試驗，沒有比210 小的整數(shù)可以同時被30 和105 整除。,例5.1.21,可以通過觀察30 和105 的素數(shù)因子，找到它們的最小公倍數(shù) 30 = 2·3·5 105 = 3·5·7lcm(30, 105)的素數(shù)因子必須包含2、3 和5 作為因子（使得30 能整除lcm(30, 105)）。同樣，必須包含3、5 和7（使得105 能整除lcm(30, 10

17、5)）。具有這個性質(zhì)的最小數(shù)是 2·3·5·7 = 210因此，lcm(30, 105) = 210。,定理5.1.22,定理5.1.25,對任意正整數(shù)m 和n，gcd(m, n)·lcm(m, n)=mn證明 如果m = 1，那么gcd (m, n) = 1 且lcm(m, n) = n，因此 gcd(m, n)·lcm(m, n) = 1·n =

18、 mn同樣，如果n = 1，那么gcd(m, n) = 1 且lcm(m, n) = m，因此 gcd(m, n)·lcm(m, n) = 1·m = mn假設(shè)m > 1，n > 1，將計算gcd 的公式（定理5.1.17）和lcm 的公式（定理5.1.22）組合起來，注意到 min(x, y) + max(x, y) = x + y,問題求解要點,判斷一個整數(shù)n > 1

19、是素數(shù)的最直接的辦法是測試2, 3,..., ? ? 中任何一個是否能整除n。這個辦法隨著n 的增長太費時，因此只能用來判斷相對比較小的n。本節(jié)給出了兩個求a 和b 的最大公因子的方法。第一個方法是列出a 和b 的所有正因子，然后在所有公因子中，選擇最大的。第二個方法是比較a 和b 的素數(shù)因子，如果pi 在a 中出現(xiàn)，p j 在b 中出現(xiàn)，那么pmin(i, j)在最大公因子的素數(shù)因子中。,5.2 整數(shù)的表示和整數(shù)算法,

20、一個位（bit）是指一位二進制數(shù)字，即一個0 或一個1。計算機中，數(shù)據(jù)和指令都編碼為位的形式。在計算機系統(tǒng)中，位在物理上如何表示依賴于所用技術(shù)。這一節(jié)討論用位表示整數(shù)的二進位數(shù)制（二進制）和用16 個符號表示整數(shù)的十六進位數(shù)制。用8 個符號表示整數(shù)的八進位數(shù)制。,,在十進制中，用10 個符號0、1、2、3、4、5、6、7、8 和9 表示整數(shù)。在表示整數(shù)時，符號的位置是有重要意義的：從右邊開始，第一個符號表示1 的個數(shù)，下一個符號表示

21、10 的個數(shù)，再下一個符號表示100 的個數(shù)，依次類推。例如， 3854 = 3·103 + 8·102 + 5·101 + 4·100,,在二進制（基數(shù)為2）中，為表示整數(shù)只需兩個符號：0 和1。表示一個整數(shù)時，從右邊開始，第一個符號表示1 的個數(shù)，下一個符號表示2 的個數(shù)，再下一個符號表示4 的個數(shù)，再下一個符號表示8 的個數(shù)，依次類推。例如，以2 為基數(shù)，,例5.2.2,二進制數(shù)轉(zhuǎn)換為

22、十進制數(shù) 二進制數(shù)1011012 表示由1 個1，沒有2、1 個4、1 個8、沒有16 和1 個32 組成的數(shù)，可以表示為 1011012 = 1·25 + 0·24 + 1·23 + 1·22 + 0·21 + 1·20 用十進制計算等式的右邊有 1011012 = 1·32 + 0·16 + 1·8 + 1·4 + 0&#

23、183;2 + 1·1 = 32 + 8 + 4 + 1 = 4510,算法5.2.3,將以b 為基數(shù)的整數(shù)轉(zhuǎn)換成十進制 這個算法返回以b 為基數(shù)的整數(shù)cncn-1?c1c0 的十進制值。,,在十六進制中，用符號0、1、2、3、4、5、6、7、8、9、A、B、C、D、E 和F 來表示整數(shù)。符號A~F 相當(dāng)于十進制中的10~15。B4F = 11·162 + 4·161 + 15·160,,現(xiàn)在來

24、考慮相反的問題—把十進制數(shù)轉(zhuǎn)換為以b 為基數(shù)的數(shù)。例，把十進制數(shù)91 轉(zhuǎn)換為二進制數(shù)。如果把91 除以2，可得到 91 = 2·45 + 1 45 = 2·22 + 1,例5.2.6,將十進制數(shù)130 轉(zhuǎn)換成二進制數(shù)。13010 = 100000102,,算法5.2.7 轉(zhuǎn)換成b為基數(shù)的整數(shù),例5.2.9十進制轉(zhuǎn)換成十六進制,將十進制數(shù)20385 轉(zhuǎn)換為十六進制數(shù)2038510 = 4FA116,,任意基數(shù)

25、的加法。,例5.2.13 十六進制加法,,,下面討論計算an mod z 。首先討論計算冪an的算法。最直接的計算冪的辦法是重復(fù)乘以a這需要n - 1 次乘法。優(yōu)化：a29 = a1·a4·a8·a16,算法5.2.16 重復(fù)乘方計算指數(shù),定理5.2.17,如果a、b 和z 是正整數(shù)， ab mod z = [(a mod z)(b mod z)] mod z,例5.2.18,計算57229 mo

26、d 713為了計算a29，連續(xù)計算 a， a5 = a·a4, a13 = a5·a8, a29 = a13·a16,,a2 mod z = [(a mod z)(a mod z)] mod za4 mod z = a2a2 mod z = [(a2 mod z)(a2 mod z)] mod za5 mod z = aa4 mod z = [(a mod z)( a4

27、mod z)] mod za13 mod z = a5a8 mod z = [(a5 mod z)( a8 mod z)] mod z,計算,算法5.2.19,問題求解要點,將以b 為基數(shù)的數(shù) cnbn + cn-1bn-1 +?+ c1b1 + c0b0轉(zhuǎn)換成十進制，用十進制執(zhí)行每位的乘法和加法。將十進制數(shù)n 轉(zhuǎn)換成以b 為基數(shù)，用b 除，結(jié)果的商用b 除，結(jié)果的商接著用b 除，繼續(xù)下去。這些余數(shù)給出了以b 為基數(shù)的n 的

28、表示。第一個余數(shù)給出了第一個位的系數(shù)，下一個給出了第二個b 位的系數(shù)，如此下去。,5.3 歐幾里得算法,尋找兩個整數(shù)的最大公因子，歐幾里得算法是一個古老、有名且有效的算法。歐幾里得算法是基于這個事實，如果 r = a mod b，那么 gcd (a, b) = gcd (b, r) gcd(105, 30) = gcd(30, 15) gcd(105, 30) = gcd(30, 15) =gcd

29、(15, 0) = 15,定理5.3.2,如果a 是一個非負整數(shù)，b 是一個正整數(shù)，r = a mod b，那么 gcd(a, b) = gcd(b, r),算法5.3.3 歐幾里得算法,例5.3.4,gcd(504, 396)a mod b = 504 mod 396 = 108a mod b = 396 mod 108 = 72a mod b = 108 mod 72 = 36a mod b = 72 mod 36

30、 = 0a(36)，即396 和504 的最大公因子,定理5.3.6,如果0 到m（m ≥ 8）之間不同時為0 的一對整數(shù)作為歐幾里得算法的輸入，那么最多需要執(zhí)行 次模運算。歐幾里得算法最多需要執(zhí)行33 次模運算就可以計算出從0 到1 000 000 之間不同時為0 的一個整數(shù)對的最大公因子。,定理5.3.7,如果a 和b 是非負整數(shù)，不同時為0，存在整數(shù)s 和t，使得 gcd(a, b) =

31、sa + tb,,假設(shè)有兩個整數(shù)n > 0， ? > 1，使得gcd(n, ?) = 1。如何有效地計算一個整數(shù)s，其中 0 < s < ? ，可以使ns mod ? = 1。稱s 是n mod ?的逆。,5.4 RSA公用密碼系統(tǒng),密碼學(xué)加密解密專用密碼,專用密碼,ABCDEFGHIJK LMNOPQRSTUVWXYZEIJFUAXVHWP GSRKOBTQYDMLZNC,,SEND MON

32、EYQARUESKRANSKRANEKRELINMONEY ON WAY,RSA 公用密碼系統(tǒng),公用加密密碼私人解密密碼01 02 A02 B,,SEND MONEY20061505011416150626,工作原理,選擇一對素數(shù) p qz=pq? = (p-1)(q-1)選擇滿足 gcd(n, ?)=1 的n (一般為素數(shù))計算滿足 ns mod ? =1 的唯一的s (0<s< ?),o

33、pen,open,保密,密碼,公用密碼 z n私用密碼 s,加密解密過程,,a,,z, n,,,,c=an mod z,,s,,a,cs mod z,原理,au mod z =a u mod ? =1cs mod z = (an mod z )s mod z = (an)s mod z = ans mod z =a,例 5.7.2,p=23 q=31 n=29 z=pq=713?=(p-1)(q-1)=66

34、0s=569 (29*569 mod 660 =1)公用密碼 29 713私用密碼=569,,a=57257229 mod 713=113 加密ab mod z = ((a mod z)(b mod z)) mod z113 569 mod 713=572 解密,c=an mod z,cs mod z,解密?,RSA 密碼系統(tǒng)第一次出現(xiàn)在1977 年2 月Martin Gardner 的Scientific

35、American 專欄中，在這個專欄里，消息利用密鑰z, n 加密，其中z 是64 位和65 位素數(shù)的乘積，n =9007，且懸賞$100 給首次破解這個密碼的人。在撰寫這篇文章的時候，分解z 估計需要40 × 10005年。實際上，在1994 年5 月，Arjen Lenstra、Paul Leyland、Michael Graff 和Derek Atkins，在來自25 個國家的600 名志愿者的幫助下，利用超過1600