密碼學與網路安全 第8章 數論介紹

質數 質數的因數只有1及自己 例如2、3、5、7是質數，4、6、8、9、10不是 質數是數論的主軸 小於200的質數： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

分解質數 分解數值 n，是將 n 寫成其他質數的乘積：n = a × b × c 例如： 91 = 7 × 13 ; 3600 = 24 × 32 × 52 以下是另一種有用的表達方式；若P是所有質數的集合，那麼任何正整數a都能用以下唯一的方式來表示：

互質與最大公因數（GCD） 如果兩數值除了1之外沒有公因數，兩數則為互質 例如 8 和 15 互質，因為 8 的因數為 1、2、4、8、15的因數為 1、3、5、15；8 和 15 的公因數只有 1 如果將每個整數表示成質數的乘積，就很容易找出兩個正整數的最大公因數，例如 300 = 21 × 31 × 52 ；18 = 21 × 32 因此最大公因數 GCD(18,300)=21 × 31 × 50 = 6

費馬定理 若p 為質數且 gcd(a,p)=1 則 ap-1 = 1 (mod p) 也稱為費馬小定理 ap = p (mod p) 費馬定理和尤拉定理在公開金鑰和質數測試扮演了重要的角色

證明: (中文本的證明部分翻得有問題) 令X = {1a mod p, 2a mod p, …, (p1)a mod p} a 無法被p整除  0  X. X中之元素均相異 (因為a和p互質，若 xa mod p = ya mod p，則x=y) 所以X = {1, 2, …, p1} a  2a  …  (p1)a mod p = (1a mod p  2a mod p  …, (p1)a mod p) mod p = (1 2  …  (p1)) mod p a p1 (p1)! mod p = (p1)! mod p a p1  1 mod p

尤拉函數 ø(n) 尤拉函數 ø(n)的定義為小於n且與n互質的正整數之個數 通常 ø(1) = 1，請計算ø(37)和ø(35) 對質數p而言： 假設兩個質數 p 和 q，且 p ≠ q，若 n = pq： 為了證明 先假設有一個小於n的正整數集合{1, …, (pq - 1)}，集合裡不與n互質的整數是集合{p, 2p, …, (q - 1)p}和集合{q, 2q, …, (p - 1) q}。因此：

尤拉函數 ø(n) 計算 ø(37)： 因為37為質數，所以1到36的所有正整數皆與37互質，因此 ø(37) = 36 計算 ø(35)： 列出所有小於35且與35互質的正整數： 1 , 2 , 3 , 4 , 6 , 8 , 9 , 11 , 12 , 13 , 16 , 17 , 18 , 19 , 22 , 23 , 24 , 26 , 27 , 29 , 31 , 32 , 33 , 34 以上共有24個數值，所以 ø(35) = 24 計算 ø(21)： ø(21) = (3–1)×(7–1) = 2 × 6 = 12 其中的12個整數是 1,2,4,5,8,10,11,13,16,17,19,20

尤拉定理 由費馬定理產生 aø(n) = 1 (mod n) 例如 對a、n而言，gcd(a,n)=1 a=3;n=10; ø(10)=4;

測試質數 許多密碼演算法必須隨機選取一或多個很大的質數 因此要確定所選取的大數是不是質數 但目前並沒有簡單而有效的判定方法

米勒－拉賓演算法 Miller Rabin Algorithm 測試的基礎是費馬定理 以下程序TEST的輸入為整數n TEST (n) 1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq 2. Select a random integer a, 1<a<n–1 3. if aq mod n = 1 then return (“inconclusive"); 4. for j = 0 to k – 1 do 5. if (a2jq mod n = n-1) then return("(“inconclusive") 6. return ("composite") n1必為偶數(why?) 請用此演算法測29、221是否為質數！

米勒－拉賓演算法的機率 如果n完全不符合質數的條件，TEST會傳回composite（合數） 如果n可能為質數，TEST會傳回inconclusive（不確定），表示可能是質數 利用TEST測試非質數的奇數n以及隨機選取的整數a，傳回inconclusive的機率小於1/4 若選取t次不同的a值，以TEST檢查n而能通過TEST的機率將小於(1/4)t 例如t = 10，非質數而能通過這所有10次測試的機率小於10-6。因此對夠大的t值而言，如果米勒－拉賓演算法的測試傳回值都是inconclusive，n是質數的機率大於 0.99999

質數的分佈 接近n的質數，其平均間隔是(ln n)個整數 平均來說，找到質數之前必須先測試大約(ln n) 個整數 但這只是平均估算，質數在數線的某些地方會密集出現，而在其他地方則會相隔較遠才會出現質數

中國餘數定理（CRT）(略) 令xZ10 CRT能從一組互質模數的餘數重建特定範圍的整數 CRT可以讓我們各自處理每個模數 mi 例如 mod M = m1m2..mk CRT可以讓我們各自處理每個模數 mi CRT能以一組較小的數值計算可能非常大的數值的取M同餘，尤其若M超過150位數，這項特色更顯實用。不過要注意的是，必須事先知道M的因數分解

總結 質數 費馬定理 尤拉定理及 ø(n) 中國餘數定理(略) 離散對數(略)