1、Chapter 4 有限體群(Group)nGroup, G,n具二元運算的元素集合n(a,b) 運算遵守:nA1. 封閉性 (closure): a,bG abG nA2. 結合性 (associative law): (ab)c=a(bc)nA3. 單位元素 (identity) e: ea=ae=anA4. 反元素 (inverses) a-1:aa-1=enif A5. 交換性 commutative ab=ba 交換群(abelian group)循環群(Cyclic Group)n引用群運算方式,定義成群的指數運算(exponentiation) ex.: a3=aaan單位元素

2、(identity): e=a0na group G is cyclic if G中的每一元素都可表示成ak 對於某個固定元素 aG, 其中 kZ na 是G的產生器(generator)環(Ring)nRing, R,+,n一具有兩個二元運算的元素集合(加法與乘法)n加法(addition)n交換群(an abelian group)nA1A5n乘法(multiplication)nM1.乘法封閉性 (closure): a,bR a bRnM2.乘法結合性 (associative law): (ab)c=a(bc)nM3.分配律 a(b+c)= ab+ac & (a+b)c= a

3、c+bcn交換環(commutative ring)nM4.乘法交換性 a b=b a整數域(Integral domain)n交換環(commutative ring)nM5.乘法單位元素: a R,1R s.t. a1=1a=an0不可為除數: a,b R and ab=0 a=0 or b=0nEx.nS=Z+Z0 S,+, is integral domain.體(Field)nField, F,+,n一具有兩個二元運算的元素集合(加法與乘法),若a,b,c F遵守:nA1M6, 即F為整數域nM7 乘法反元素: a F0, a-1 F s.t. aa-1 =(a-1)a =1群,環,

4、體關係n圖4-14.2 同餘運算(modular arithmetic)na=qn+r, 0r a, b同餘(congruent modulo n)n除數 :If b0, a=mb, a,b,m Z = nb整除 anb|anb為a的因數4.3 EUCLID 演算法n求兩正整數的最大公因素(n輾轉相除法ngcd(a,b)=gcd(b,a mod b)na = kb+r r mod bna mod b = rnEx. gcd(55,22)4.4 有限體 GF(p)nGalois fieldsnGF(p) 為一整數集合 Zp =0,1, , p1 na finite fieldn乘法反元素 w1(multiplicative inverses)wZp, w 0, zZp , s.t. wz 1 (mod p) w1 = zGF(p)求乘法反元素n若gcd(m,b)=1 在取同餘m的情況下,b會有乘法反元素n即正整數bm, b1 g(x) 整除 f(x) ( g(x)|f(x) )n若 f(x) 無法表成兩個多項式的乘積 = 不可分解(irreducible) or 質數(prime)多項式多項式最大公因式GCDEUCLIDa(x), b(x)1. A(x) = a(x); B(x) = b(x)2. if B(x) = 0 return