Chapter 2 密碼基礎數學I：模數算數、同餘 與矩陣.

Presentation on theme: "Chapter 2 密碼基礎數學I：模數算數、同餘 與矩陣."— Presentation transcript:

1 Chapter 2 密碼基礎數學I：模數算數、同餘 與矩陣

2 學習目標 回顧整數算術，特別是整除性，並利用歐幾里德演算法來找出最大公因數。
學習利用歐幾里德延伸演算法來解線性 Diophantine 方程式、線性同餘方程式，以及找出乘法反元素。 著重在模數算術和模運算子的學習，因為它們在密碼學中被大量地使用。

3 學習目標 (續) 強調並回顧矩陣和餘數矩陣的運算，因為它們在密碼學中的應用非常廣泛。 學習利用餘數矩陣來解同餘方程組。

4 1.2 整數算數 在整數算術 (integer arithmetic) 中，我們使用一個集合和一些運算。或許你對這個集合和運算可能已經非常熟悉，但為了建立模數算術的背景知識，在此我們還是對整數算術做一個回顧。

5 1.2 整數算數 (續) 在本節討論的主題： 整數集合 二元運算 整數除法 整除性 線性Diophantine方程式

6 整數集合 整數集合，標記為 Z，是從負無窮大到正無窮大的所有整數形成的集合(圖 2.1) 圖 2.1 整數集合

7 二元運算 在密碼學中，我們對於三種作用於整數集合的二元運算 (binary operation) 感到興趣。二元運算可接受兩個輸入值，然後產生一個輸出值。

8 圖 2.2 三種作用在整數集合上的二元運算

9 範例2.1 下列的例子顯示出三種二元運算作用於兩個整數後所產生的結果。由於每個輸入值均可為正值或負值，因此對於每一種運算我們討論四種情形。

10 2.1.3 整數除法 在整數算術中，如果我們使用 n 來除 a，可以得到 q 和 r。這四個整數之間的關係可以表示為：
整數除法 在整數算術中，如果我們使用 n 來除 a，可以得到 q 和 r。這四個整數之間的關係可以表示為： a = q × n + r

11 範例2.2 假設 a = 255 且 n = 11。利用過去所學的除法算術，我們可以得到 q = 23 且 r = 2。（圖2.3）

12 圖 2.4 整數的除法演算法

13 範例2.3 當我們使用電腦或計算機計算除法時，若 a 為負數，則 r 和 q 也為負數。我們要如何根據限制讓 r 變為正數呢？很簡單，我們只要將 q 值減 1，並且將 r 值加 n ，就可以讓 r 變成正數。

14 圖 2.5 除法演算法的圖形

15 2.1.4 整除性 在一個除法關係中，如果 a 不為 0 且令 r = 0，則可以得到： a = q × n 若餘數為零，則 若餘數為零，則

16 範例2.4 整數 4 可以整除 32，因為 32 = 8 × 4。我們將此關係表示成
整數 4 可以整除 32，因為 32 = 8 × 4。我們將此關係表示成 整除 8 無法整除 42，因為 42 = 5 × 8 + 2，此方程式的餘數為2。我們將此關係表示成

17 範例2.5 我們可以得到 13|78, 7|98, -6|24, 4|44 以及 11|(-33)。 我們可以得到 以及 。

18 2.1.4 整除性 (續) 性質1：若 a|1，則 a = ±1。 性質2：若 a|b 且 b|a，則 a = ±b。
性質3：若 a|b 且 b|c，則 a|c。 性質4：若 a|b 且 a|c，則a|(m × b + n × c)， 其中 m 和 n 為任意整數。

19 範例2.6 因為 3|15 且 15|45，根據性質3, 3|45。 因為 3|15 且 3|9，根據性質4， 3|(15 × × 4 ) ，亦即 3|66。

20 2.1.4 整除性 (續) 事實1：整數 1 只有一個因數，就是它自己
注意 事實1：整數 1 只有一個因數，就是它自己 事實2：任何整數至少有2個因數，1 和 它自己 （但也可能有更多其他因數）

21 圖 2.6 兩個整數的公因數

22 2.1.4 整除性 (續) 兩個整數的最大公因數為所有能整除這兩個整數之最大整數。 事實 1: gcd (a, 0) = a。
注意 最大公因數 兩個整數的最大公因數為所有能整除這兩個整數之最大整數。 注意 歐幾里德演算法 事實 1: gcd (a, 0) = a。 事實 2: gcd (a, b) = gcd (b, r), 其中 r 是 a 除以 b 的餘數。

23 圖 2.7 歐幾里德演算法

24 2.1.4 整除性 (續) 注意 當 gcd (a, b) = 1 時，我們說 a 和 b 為互質。

25 範例2.7 試求 2740 和 1760 的最大公因數。 解法：我們得到 gcd (2740, 1760) = 20。

26 範例2.8 試求 25 和 60 的最大公因數。 解法：我們得到 gcd (25, 65) = 5。

27 歐幾里德延伸演算法 給定兩個整數 a 和 b，我們時常需要去找出另外兩個整數 s 和 t，使得
歐幾里德延伸演算法可以同時計算出 gcd (a, b) 以及 s 和 t 的值。

28 圖 2.8 歐幾里德延伸演算法

29 圖 2.8 歐幾里德延伸演算法 (續)

30 範例2.9 給定 a = 161 和 b = 28，求出 gcd (a, b) 以及 s 和 t 的值。
解法：我們得到 gcd (161, 28) = 7，s = −1 和 t = 6。

31 範例2.10 給定 a = 17和 b = 0，求出 gcd (a, b) 以及 s 和 t 的值。
解法：我們得到 gcd (17, 0) = 17，s = 1 和 t = 0。

32 範例2.11 給定 a = 0 和 b = 45，求出 gcd (a, b) 以及 s 和 t 的值。
解法：我們得到 gcd (0, 45) = 45，s = 0 和 t = 1。

33 2.1.5 線性Diophantine方程式 雙變數之線性Diophantine方程式是一種形態為 ax + by = c 的方程式。
注意 雙變數之線性Diophantine方程式是一種形態為 ax + by = c 的方程式。 注意 特解： x0 = (c/d)s 和 y0 = (c/d)t

34 2.1.5 線性Diophantine方程式(續) 通解：
注意 通解： x = x0 + k (b/d) 和 y = y0 − k(a/d) 其中 k 為整數

35 範例2.12 求出方程式 21x + 14y = 35 的特解和通解。 解法：

36 範例2.13 舉例來說，我們要把100美元的支票兌換成一些由20美元和5美元的鈔票。利用求解線性Diophantine方程式 20x + 5y = 10，可以找出許多不同的兌換方式。因為 d = gcd (20, 5) = 5，而且 5 | 100，此方程式有無限多解，但本例中，這些解中只有少數是合理的 ( x 值和 y 值必須同時為非負整數解)。這條方程式之非負整數的通解為 (0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0)

37 2.2 模數算數 前一節所討論的除法關係 (a = q × n + r) 有兩個輸入值 (a 和 n) 以及兩個輸出值 (q 和 r)。在模數算術中，我們只對其中一個輸出值餘數 r 感興趣。

38 2.2 模數算數 (續) 本節所探討的主題包含： 模運算子 餘數集合：Zn 同餘 Zn下的運算 反元素 加法表和乘法表 加法和乘法的不同集合
另外兩種集合

39 2.2.1 模運算子 模運算子 (modulo operator)，符號為 mod。第二個輸入值 (n) 稱為模數 (modulus) ，輸出值 r 則被稱為餘數 (residue)。

40 圖 2.9 除法關係與模運算子

41 範例2.14 求解下列運算式： a. 27 mod 5 b. 36 mod 12 c. −18 mod 14 d. −7 mod 10 解法
27 除以 5 可得 r = 2。 36 除以 12 可得 r = 0 。 -18 除以 14 可得 r = −4。−4 加上模數之後， r = 10 。 -7 除以 10 可得 r = −7。−7加上模數之後，r = 3 。

42 2.2.2 餘數集合：Zn 模數運算會產生一個集合，此集合在模數算數中被稱為模 n 之最小餘數集合 (set of least residues modulo n)，或記為 Zn。 圖 一些 Zn 的集合

43 同餘 我們使用同餘運算子 ( ≡ )來表示兩個整數是同餘的。舉例來說，我們寫出：

44 圖 2.11 同餘的概念

45 剩餘類 剩餘類 (Residue class) [a] 或 [a]n，是一個在模 n 之下所有餘數為 a 的整數集合。

46 圖 利用圖形來比較 Z 和 Zn

47 範例2.15 日常生活都會用到模數算術，例如使用時鐘來測量時間。時鐘系統是模數為12的算術。然而在時鐘系統中，我們使用數字12來代替0，所以時鐘系統從0 (或12) 開始前進，直到11為止。因為一天是24小時，因此會沿著時鐘的圓形循環兩次，並且把第一次的循環記為A.M.，然後把第二次的循環記為P.M.。

48 2.2.4 Zn下的運算 我們之前討論集合 Z 中的三個運算 (加法、減法和乘法) 也可以在集合 Zn 中定義。這些運算的結果可能需要使用模運算子將其對應到 Zn中。

49 圖2.13 Zn中的二元運算

50 範例2.16 計算下列各運算式 (輸入值為 Zn 中的元素)： a. 在 Z15 中計算 14 加 7。
b. 在 Z13 中計算 7 減 11。 c. 在 Z20 中計算 7 乘 11。 解法

51 範例2.17 計算下列各運算式 (輸入值為 Z或 Zn 中的元素)： a. 在 Z14 中計算 17 加 27。
b. 在 Z13 中計算 12 減 43。 c. 在 Z19 中計算 123 乘 -10。 解法

52 2.2.4 Zn下的運算 (續) 性質

53 圖 模運算子的性質

54 範例2.18 下列運算式顯示出如何應用上述性質： a. (1,723, ,124,945) mod 11 = (8 + 9) mod 11 = 6 b. (1,723,345 − 2,124,945) mod 16 = (8 − 9) mod 11 = 10 c. (1,723,345 × 2,124,945) mod 16 = (8 × 9) mod 11 = 6

55 範例2.19 在算術中，我們經常需要計算10 的冪次方除以某個整數所得之餘數。

56 範例2.20 我們在過去被教導過，算術中一個整數除以3的餘數，和其每一位數之總和除以3的餘數是相同的。我們可以使用模運算子的性質來證明這個宣稱。我們先將整數改寫成每一個位數乘以10的冪次方之總和。