5數(shù)論簡(jiǎn)介

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

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

3、 n。（如果d | n ，那么存在一個(gè)整數(shù)q 使得n = dq。由于n 和d 是正整數(shù)，1 ≤ q。因此，d ≤ dq = n。）無(wú)論整數(shù)d > 0 是否整除整數(shù)n，存在一個(gè)惟一的整數(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,對(duì)于一個(gè)大于1 的整數(shù)，它的因子只有其自身和1 被稱為素?cái)?shù)。一個(gè)大于1 的不是素?cái)?shù)的整數(shù)稱為合數(shù)。 整數(shù)23 是一個(gè)素?cái)?shù)，因?yàn)橹挥衅浔旧砗? 是它的因子。整數(shù)34 是合數(shù)因?yàn)樗梢员?7整除，17 既不是1 也不是34。,,如果整數(shù)n > 1是合數(shù)，那么它有一個(gè)正因子d 既不是1 也不是其自身。由于d 是正的且d ≠ 1，

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

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

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

8、中，算法返回素?cái)?shù)2，因?yàn)樗財(cái)?shù)2 整除1274，即1274 = 2·637如果現(xiàn)在輸入n = 637 到算法5.1.8 中，算法返回素?cái)?shù)7，因?yàn)樗財(cái)?shù)7 整除637，即637 = 7·91如果現(xiàn)在輸入n = 91 到算法5.1.8 中，算法返回素?cái)?shù)7，因?yàn)樗財(cái)?shù)7 整除91，即91 = 7·13如果現(xiàn)在輸入n = 13 到算法5.1.8 中，算法返回0，因?yàn)?3 是素?cái)?shù)。把前面的過(guò)程組合起來(lái)得到1247

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

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

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

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

13、和8 的最大公因子是1。當(dāng)檢查分?jǐn)?shù)m/n（其中m和n 是整數(shù)時(shí)）是否是最簡(jiǎn)的時(shí)，會(huì)用到最大公因子的概念。如果m和n 的最大公因子是1，m/n 是最簡(jiǎn)表示；否則，可以約減m/n。例如，4/6 不是最簡(jiǎn)表示，因?yàn)? 和6 的最大公因子是2，不是1。3/8 是最簡(jiǎn)表示，因?yàn)? 和8 的最大公因子是1。,定義5.1.14,令m和n 是整數(shù)，兩者不同時(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,通過(guò)仔細(xì)觀察30 和105 的素?cái)?shù)因子來(lái)尋找它們的最大公因

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 的一個(gè)公倍數(shù)是一個(gè)可以同時(shí)被m 和n 整除的整數(shù)。最小公倍數(shù)，記做 lcm(m, n) 是m 和n 的最小的正的公倍數(shù)30 和105 的最小公倍數(shù)lcm(30, 105)是210，因?yàn)?10 可以同時(shí)被30

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

17、5)）。具有這個(gè)性質(zhì)的最小數(shù)是 2·3·5·7 = 210因此，lcm(30, 105) = 210。,定理5.1.22,定理5.1.25,對(duì)任意正整數(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，將計(jì)算gcd 的公式（定理5.1.17）和lcm 的公式（定理5.1.22）組合起來(lái)，注意到 min(x, y) + max(x, y) = x + y,問題求解要點(diǎn),判斷一個(gè)整數(shù)n > 1

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

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

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

22、十進(jìn)制數(shù) 二進(jìn)制數(shù)1011012 表示由1 個(gè)1，沒有2、1 個(gè)4、1 個(gè)8、沒有16 和1 個(gè)32 組成的數(shù)，可以表示為 1011012 = 1·25 + 0·24 + 1·23 + 1·22 + 0·21 + 1·20 用十進(jìn)制計(jì)算等式的右邊有 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)換成十進(jìn)制 這個(gè)算法返回以b 為基數(shù)的整數(shù)cncn-1?c1c0 的十進(jìn)制值。,,在十六進(jìn)制中，用符號(hào)0、1、2、3、4、5、6、7、8、9、A、B、C、D、E 和F 來(lái)表示整數(shù)。符號(hào)A~F 相當(dāng)于十進(jìn)制中的10~15。B4F = 11·162 + 4·161 + 15·160,,現(xiàn)在來(lái)

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

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

26、d 713為了計(jì)算a29，連續(xù)計(jì)算 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,計(jì)算,算法5.2.19,問題求解要點(diǎn),將以b 為基數(shù)的數(shù) cnbn + cn-1bn-1 +?+ c1b1 + c0b0轉(zhuǎn)換成十進(jìn)制，用十進(jìn)制執(zhí)行每位的乘法和加法。將十進(jìn)制數(shù)n 轉(zhuǎn)換成以b 為基數(shù)，用b 除，結(jié)果的商用b 除，結(jié)果的商接著用b 除，繼續(xù)下去。這些余數(shù)給出了以b 為基數(shù)的n 的

28、表示。第一個(gè)余數(shù)給出了第一個(gè)位的系數(shù)，下一個(gè)給出了第二個(gè)b 位的系數(shù)，如此下去。,5.3 歐幾里得算法,尋找兩個(gè)整數(shù)的最大公因子，歐幾里得算法是一個(gè)古老、有名且有效的算法。歐幾里得算法是基于這個(gè)事實(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 是一個(gè)非負(fù)整數(shù)，b 是一個(gè)正整數(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）之間不同時(shí)為0 的一對(duì)整數(shù)作為歐幾里得算法的輸入，那么最多需要執(zhí)行 次模運(yùn)算。歐幾里得算法最多需要執(zhí)行33 次模運(yùn)算就可以計(jì)算出從0 到1 000 000 之間不同時(shí)為0 的一個(gè)整數(shù)對(duì)的最大公因子。,定理5.3.7,如果a 和b 是非負(fù)整數(shù)，不同時(shí)為0，存在整數(shù)s 和t，使得 gcd(a, b) =

31、sa + tb,,假設(shè)有兩個(gè)整數(shù)n > 0， ? > 1，使得gcd(n, ?) = 1。如何有效地計(jì)算一個(gè)整數(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,工作原理,選擇一對(duì)素?cái)?shù) p qz=pq? = (p-1)(q-1)選擇滿足 gcd(n, ?)=1 的n (一般為素?cái)?shù))計(jì)算滿足 ns mod ? =1 的唯一的s (0<s< ?),o

33、pen,open,保密,密碼,公用密碼 z n私用密碼 s,加密解密過(guò)程,,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 專欄中，在這個(gè)專欄里，消息利用密鑰z, n 加密，其中z 是64 位和65 位素?cái)?shù)的乘積，n =9007，且懸賞$100 給首次破解這個(gè)密碼的人。在撰寫這篇文章的時(shí)候，分解z 估計(jì)需要40 × 10005年。實(shí)際上，在1994 年5 月，Arjen Lenstra、Paul Leyland、Michael Graff 和Derek Atkins，在來(lái)自25 個(gè)國(guó)家的600 名志愿者的幫助下，利用超過(guò)1600