Chapter 2 密碼基礎數學I:模數算數、同餘 與矩陣
學習目標 回顧整數算術,特別是整除性,並利用歐幾里德演算法來找出最大公因數。 學習利用歐幾里德延伸演算法來解線性 Diophantine 方程式、線性同餘方程式,以及找出乘法反元素。 著重在模數算術和模運算子的學習,因為它們在密碼學中被大量地使用。
學習目標 (續) 強調並回顧矩陣和餘數矩陣的運算,因為它們在密碼學中的應用非常廣泛。 學習利用餘數矩陣來解同餘方程組。
1.2 整數算數 在整數算術 (integer arithmetic) 中,我們使用一個集合和一些運算。或許你對這個集合和運算可能已經非常熟悉,但為了建立模數算術的背景知識,在此我們還是對整數算術做一個回顧。
1.2 整數算數 (續) 在本節討論的主題: 整數集合 二元運算 整數除法 整除性 線性Diophantine方程式
2.1.1 整數集合 整數集合,標記為 Z,是從負無窮大到正無窮大的所有整數形成的集合(圖 2.1) 圖 2.1 整數集合
2.1.2 二元運算 在密碼學中,我們對於三種作用於整數集合的二元運算 (binary operation) 感到興趣。二元運算可接受兩個輸入值,然後產生一個輸出值。
圖 2.2 三種作用在整數集合上的二元運算
範例2.1 下列的例子顯示出三種二元運算作用於兩個整數後所產生的結果。由於每個輸入值均可為正值或負值,因此對於每一種運算我們討論四種情形。
2.1.3 整數除法 在整數算術中,如果我們使用 n 來除 a,可以得到 q 和 r。這四個整數之間的關係可以表示為: 2.1.3 整數除法 在整數算術中,如果我們使用 n 來除 a,可以得到 q 和 r。這四個整數之間的關係可以表示為: a = q × n + r
範例2.2 假設 a = 255 且 n = 11。利用過去所學的除法算術,我們可以得到 q = 23 且 r = 2。(圖2.3)
圖 2.4 整數的除法演算法
範例2.3 當我們使用電腦或計算機計算除法時,若 a 為負數,則 r 和 q 也為負數。我們要如何根據限制讓 r 變為正數呢?很簡單,我們只要將 q 值減 1,並且將 r 值加 n ,就可以讓 r 變成正數。
圖 2.5 除法演算法的圖形
2.1.4 整除性 在一個除法關係中,如果 a 不為 0 且令 r = 0,則可以得到: a = q × n 若餘數為零,則 若餘數為零,則
範例2.4 整數 4 可以整除 32,因為 32 = 8 × 4。我們將此關係表示成 整數 4 可以整除 32,因為 32 = 8 × 4。我們將此關係表示成 整除 8 無法整除 42,因為 42 = 5 × 8 + 2,此方程式的餘數為2。我們將此關係表示成
範例2.5 我們可以得到 13|78, 7|98, -6|24, 4|44 以及 11|(-33)。 我們可以得到 以及 。
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 為任意整數。
範例2.6 因為 3|15 且 15|45,根據性質3, 3|45。 因為 3|15 且 3|9,根據性質4, 3|(15 × 2 + 9 × 4 ) ,亦即 3|66。
2.1.4 整除性 (續) 事實1:整數 1 只有一個因數,就是它自己 注意 事實1:整數 1 只有一個因數,就是它自己 事實2:任何整數至少有2個因數,1 和 它自己 (但也可能有更多其他因數)
圖 2.6 兩個整數的公因數
2.1.4 整除性 (續) 兩個整數的最大公因數為所有能整除這兩個整數之最大整數。 事實 1: gcd (a, 0) = a。 注意 最大公因數 兩個整數的最大公因數為所有能整除這兩個整數之最大整數。 注意 歐幾里德演算法 事實 1: gcd (a, 0) = a。 事實 2: gcd (a, b) = gcd (b, r), 其中 r 是 a 除以 b 的餘數。
圖 2.7 歐幾里德演算法
2.1.4 整除性 (續) 注意 當 gcd (a, b) = 1 時,我們說 a 和 b 為互質。
範例2.7 試求 2740 和 1760 的最大公因數。 解法:我們得到 gcd (2740, 1760) = 20。
範例2.8 試求 25 和 60 的最大公因數。 解法:我們得到 gcd (25, 65) = 5。
歐幾里德延伸演算法 給定兩個整數 a 和 b,我們時常需要去找出另外兩個整數 s 和 t,使得 歐幾里德延伸演算法可以同時計算出 gcd (a, b) 以及 s 和 t 的值。
圖 2.8 歐幾里德延伸演算法
圖 2.8 歐幾里德延伸演算法 (續)
範例2.9 給定 a = 161 和 b = 28,求出 gcd (a, b) 以及 s 和 t 的值。 解法:我們得到 gcd (161, 28) = 7,s = −1 和 t = 6。
範例2.10 給定 a = 17和 b = 0,求出 gcd (a, b) 以及 s 和 t 的值。 解法:我們得到 gcd (17, 0) = 17,s = 1 和 t = 0。
範例2.11 給定 a = 0 和 b = 45,求出 gcd (a, b) 以及 s 和 t 的值。 解法:我們得到 gcd (0, 45) = 45,s = 0 和 t = 1。
2.1.5 線性Diophantine方程式 雙變數之線性Diophantine方程式是一種形態為 ax + by = c 的方程式。 注意 雙變數之線性Diophantine方程式是一種形態為 ax + by = c 的方程式。 注意 特解: x0 = (c/d)s 和 y0 = (c/d)t
2.1.5 線性Diophantine方程式(續) 通解: 注意 通解: x = x0 + k (b/d) 和 y = y0 − k(a/d) 其中 k 為整數
範例2.12 求出方程式 21x + 14y = 35 的特解和通解。 解法:
範例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)
2.2 模數算數 前一節所討論的除法關係 (a = q × n + r) 有兩個輸入值 (a 和 n) 以及兩個輸出值 (q 和 r)。在模數算術中,我們只對其中一個輸出值餘數 r 感興趣。
2.2 模數算數 (續) 本節所探討的主題包含: 模運算子 餘數集合:Zn 同餘 Zn下的運算 反元素 加法表和乘法表 加法和乘法的不同集合 另外兩種集合
2.2.1 模運算子 模運算子 (modulo operator),符號為 mod。第二個輸入值 (n) 稱為模數 (modulus) ,輸出值 r 則被稱為餘數 (residue)。
圖 2.9 除法關係與模運算子
範例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 。
2.2.2 餘數集合:Zn 模數運算會產生一個集合,此集合在模數算數中被稱為模 n 之最小餘數集合 (set of least residues modulo n),或記為 Zn。 圖 2.10 一些 Zn 的集合
2.2.3 同餘 我們使用同餘運算子 ( ≡ )來表示兩個整數是同餘的。舉例來說,我們寫出:
圖 2.11 同餘的概念
剩餘類 剩餘類 (Residue class) [a] 或 [a]n,是一個在模 n 之下所有餘數為 a 的整數集合。
圖 2.12 利用圖形來比較 Z 和 Zn
範例2.15 日常生活都會用到模數算術,例如使用時鐘來測量時間。時鐘系統是模數為12的算術。然而在時鐘系統中,我們使用數字12來代替0,所以時鐘系統從0 (或12) 開始前進,直到11為止。因為一天是24小時,因此會沿著時鐘的圓形循環兩次,並且把第一次的循環記為A.M.,然後把第二次的循環記為P.M.。
2.2.4 Zn下的運算 我們之前討論集合 Z 中的三個運算 (加法、減法和乘法) 也可以在集合 Zn 中定義。這些運算的結果可能需要使用模運算子將其對應到 Zn中。
圖2.13 Zn中的二元運算
範例2.16 計算下列各運算式 (輸入值為 Zn 中的元素): a. 在 Z15 中計算 14 加 7。 b. 在 Z13 中計算 7 減 11。 c. 在 Z20 中計算 7 乘 11。 解法
範例2.17 計算下列各運算式 (輸入值為 Z或 Zn 中的元素): a. 在 Z14 中計算 17 加 27。 b. 在 Z13 中計算 12 減 43。 c. 在 Z19 中計算 123 乘 -10。 解法
2.2.4 Zn下的運算 (續) 性質
圖 2.14 模運算子的性質
範例2.18 下列運算式顯示出如何應用上述性質: a. (1,723,345 + 2,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
範例2.19 在算術中,我們經常需要計算10 的冪次方除以某個整數所得之餘數。
範例2.20 我們在過去被教導過,算術中一個整數除以3的餘數,和其每一位數之總和除以3的餘數是相同的。我們可以使用模運算子的性質來證明這個宣稱。我們先將整數改寫成每一個位數乘以10的冪次方之總和。