n之质数多项式在GF23.PPT

 第4章 有限體 簡介 有限體在密碼學日漸益重要 許多密碼學演算法，都很依賴有限體的特性，尤其是進階加密標準（AES）和橢圓曲線密碼學 群(groups)、環(rings)、和體(fields)是抽象代數或現代代數的基本要素 在抽象代數中，我們關心的是哪些集合元素可以代數運算 群 「群」（有時表示成{G,?}）是內含二元運算的元素集合 對G裡的每組元素（a, b）來說，（a?b）也是G裡的元素(即符合封閉性closure) 還必須遵守： 結合性：(a.b).c = a.(b.c) 單位元素： e: e.a = a.e = a 反元素： a.a’= e 若 a.b = b.a 即為交換群(abelian group) 循環群Cyclic Group 將群的重複運算定義為群的指數運算：a3 = a.a.a 此外也定義：e=a0 和 a-n = (a’)n 假如G裡的每個元素都是某固定元素a的指數(可以為負)，G就是循環群 a: generator (產生器) 循環群必為交換群，而且可能是有限群或無限群 環(ring) 含兩個二元運算（加法和乘法）的數值 加法交換群： 乘法封閉性 乘法結合性 分配律：a(b+c) = ab + ac 若滿足乘法交換性，即為交換環 整數域(integral domain) 乘法單位元素 0不可為除數 體Field 「體」（有時表示成{F, ＋, ×}）是具有兩個二元運算的元素集合 「體」是可以計算加法、減法、乘法、除法的集合 除法規則的定義是a/b = a( b-1) 「體」常見的例子包括了有理數、實數、複數 群、環、體 模數運算 若a 為整數、n 為正整數 將a mod n 的值定義為a 除n 的餘數 整數n稱為模數 若（a mod n ) =( b mod n ) 整數a、b是n的同餘 寫成a ≡ b(mod n) 除數 若b ≠ 0而a 、b 、m 皆為整數，且某個數值m能讓a = mb 表示b 能整除a 也就是b 除以a 不會有餘數 通常以b｜a表示b 能整除a 而b也就是a的因數(divisor) 例如1,2,3,4,6,8,12,24都可以整除24 模數算術 若n｜(a - b)，a ≡ b(mod n) 若a ≡ b(mod n)，b ≡a(mod n) 若a ≡ b(mod n)且b ≡ c(mod n)，a ≡ c(mod n) 模數算術 Zn是小於n的非負整數集合：Zn = {0, 1, … , n-1} 這是模數n的餘數集合或餘數類別；Zn裡的每個整數都是餘數類別 一般運算所沒有的兩項特性： 若(a+b)=(a+c) mod n，則b=c mod n 但a、n 互為質數，且若(a.b)=(a.c) mod n，則b=c mod n 模數為8的模數加法運算 最大公因數（GCD） 數論的共同問題 若a、b、m為整數，對m來說，如果a = mb，非零的b就是a的因數 GCD(a, b)表示a和b的最大公因數；正整數c若符合以下兩點，就是a、b的最大公因數： c是a、b的因數 a、b的任何因數也是c的因數 例如GCD(60,24) = 12 若兩整數a、b只有正公因數1，則a、b互為質數 以等式表示即為 GCD(a, b) = 1 例如 GCD(8,15) = 1（8、15互為質數） 歐幾里德演算法 找出最大公因數的有效方法 對任何非負整數a和任何正整數b而言： GCD(a,b) = GCD(b, a mod b) 歐幾里德演算法計算最大公因數的方式： EUCLID(a,b) 1. A = a; B = b 2. if B = 0 return A = gcd(a, b) 3. R = A mod B 4. A = B 5. B = R 6. goto 2 範例：GCD(1970,1066) 1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904 = 5 x 162 + 94 gcd(162, 94) 162 = 1 x 94 + 68 gcd(94, 68) 94 = 1 x 68 + 26 gcd(68, 26) 68 = 2 x 26 + 16 gcd(26, 16) 26 = 1 x 16 + 10 gcd(16, 10) 16 = 1 x 10 + 6 gcd(10, 6) 10 = 1 x 6 + 4 gcd(6, 4) 6 = 1 x 4 + 2 gcd(4, 2) 4 = 2 x 2 + 0 gcd(2, 0) 有限體(Finite Fields,Galois Fields) 有限