Skip to main content
Secologies

群論

•4 min•873 words
乘法群加法群數論群

在數論當中群(Group)是其中一種重要的概念，代數最基本由三種結構組成：群 Group, 環 Ring, 體 Field，而群作為最基本的代數結構，也是我們在密碼系統中常常使用的，故需要先了解群的定義對於後續密碼系統分析會比較方便

定義

一個群由一個集合和運算元組成G=(S,⊙)G = (S, \odot)，集合S以及運算元⊙\odot(這個意思表示任何運算元皆可，而我們在密碼系統內最常表達的是加法+與乘法*)，而一個群需要滿足下列四個條件：

  • (封閉性 Closure)：For  every  x,y∈S,x⊙y∈SFor\>\> every\>\> x, y \in S, x \odot y \in S ，對於任何元素xx和yy屬於SS這個集合裡面，做任何的運算後該元素也應該要屬於這個集合內。
  • (關聯性 Associativity)：For  every  x,y,z∈S,(x⊙y)⊙z=x⊙(y⊙z)For\>\> every\>\> x,y,z \in S,(x \odot y) \odot z = x \odot (y \odot z)，對於任何元素xx, yy, zz屬於這個集合SS內，先運算xx與yy最後再與zz運算，跟yy與zz做運算最後再跟xx做運算的結果是一樣的
  • (單位元素 Identity)：Exist  e∈S such that for every x∈S,x⊙e=e⊙x=xExist\>\> e \in S\ such\ that\ for\ every\ x \in S, x \odot e = e \odot x = x，在集合SS內存在一個單位元素ee能夠讓集合內任何一個元素xx與這個ee做運算會得到xx本身
  • (反元素 Inverse)：For  every  x∈S,exist y∈S,x⊙y=eFor\>\> every\>\> x \in S, exist\ y \in S, x \odot y = e，對這個集合SS的xx元素存在一個yy元素，而xx元素與yy元素進行運算能夠得到單位元素ee

滿足以上四點的話該集合S就能構成一個群，而在多一項條件的話可以變成阿貝爾群(Abelian)：

  • (交換性 Commutative)：For  every  x,y∈S,x⊙y=y⊙xFor\>\> every\>\> x, y \in S, x \odot y = y \odot x，對於任意xx, yy元素在SS集合內，xx對yy進行運算跟yy跟xx進行運算結果都一樣

Additive Groups 加法群

滿足群的條件，如果整個群裡面運算元使用加法，代表這是一個加法群，其定義如下：

  • 運算元 ⊙→+\odot \to +
  • 單位元素 Identity：0
  • 反元素 inverse: ∃−x\exists -x 對於x∈Sx \in S
  • multiple：kx=x+x+….+xkx = x + x +….+ x

範例

(Z,+)(Z, +)：Z是整數集合−∞…−2,−1,0,1,2,…,∞{-\infty…-2,-1,0,1,2,…,\infty}，而++則代表在這個整數群內通通使用加法運算

(Zn,+)(Z_n, +)：Zn=0,1,…,n−1Z_n={0,1,…,n-1}，ZnZ_n是0到n-1的整數群並且使用加法運算在(mod n)(mod\ n)的條件之下，(mod n)(mod\ n)才能把條件限制在n−1n-1之下

  • ∥Zn∥=n\lVert Z_n \rVert = n，ZnZ_n這個整數群內的元素個數總共有nn個，從 0 到 n−1n-1
  • −x→n−x-x \to n-x：x−x=0 (mod n)→−x=n−xx - x = 0\ (mod\ n) \to -x = n - x

(Zp[x],+)(Z_p[x],+)：集合由多項式組成而係數在ZpZ_p集合內

Multiplicative Groups 乘法群

滿足群的條件，如果整個群裡面運算元使用乘法，代表這是一個乘法群，其定義如下：

  • 運算元 ⊙→∗\odot \to *
  • 單位元素 Identity：1
  • 反元素 Inverse：x−1x^{-1}
  • multiple：xk=x∗x∗...∗xx^{k} = x * x * ... * x

範例

(Q\0,∗)(Q\backslash{0}, *)：QQ是有理數集合排除掉0，並且這個群使用乘法運算元

(Zn∗,∗)：Zn∗=x∣x∈Zn,x⊥n(Z_n^{*}, *)：Z_n^{*}={x | x \in Z_n, x\perp n}，Zn∗Z_n^{*}代表這個整數群在(mod n)(mod \> n)之下，並且整個群都是使用乘法運算元

  • ∥Zn∗∥=φ(n)\lVert Z_n^{*} \rVert = \varphi(n)
  • x−1x^{-1}指的是x−1(mod n)x^{-1} (mod\> n)在x∈Zn∗x \in Z_{n}^*的條件下