目錄
[latexpage]
在數論當中群(Group)是其中一種重要的概念，代數最基本由三種結構組成：群 Group, 環 Ring, 體 Field，而群作為最基本的代數結構，也是我們在密碼系統中常常使用的，故需要先了解群的定義對於後續密碼系統分析會比較方便。
定義
一個群由一個集合和運算元組成$G = (S, \odot)$，集合S以及運算元$\odot$(這個意思表示任何運算元皆可，而我們在密碼系統內最常表達的是加法+與乘法*)，而一個群需要滿足下列四個條件：
- (封閉性 Closure)：$For\ every\ x, y \in S, x \odot y \in S$ ，對於任何元素x和y屬於S這個集合裡面，做任何的運算後該元素也應該要屬於這個集合內。
- (關聯性 Associativity)：$For\ every\ x,y,z \in S,(x \odot y) \odot z = x \odot (y \odot z)$，對於任何元素x, y, z屬於這個集合S內，先運算x與y最後再與z運算，跟y與z做運算最後再跟x做運算的結果是一樣的。
- (單位元素 Identity)：$Exist\ e \in S\ such\ that\ for\ every\ x \in S, x \odot e = e \odot x = x$，在集合S內存在一個單位元素e能夠讓集合內任何一個元素x與這個e做運算會得到x本身。
- (反元素 Inverse)：$For\ every\ x \in S, exist\ y \in S, x \odot y = e$，對這個集合S的x元素存在一個y元素，而x元素與y元素進行運算能夠得到單位元素e。
滿足以上四點的話該集合S就能構成一個群，而在多一項條件的話可以變成阿貝爾群(Abelian)：
- (交換性 Commutative)：$For\ every x, y \in S, x \odot y = y \odot x$，對於任意x, y元素在S集合內，x對y進行運算跟y跟x進行運算結果都一樣。
Additive Groups 加法群
滿足群的條件，如果整個群裡面運算元使用加法，代表這是一個加法群，其定義如下：
- 運算元 $\odot \to +$
- 單位元素 Identity：0
- 反元素 inverse: $\exists -x$ 對於$x \in S$
- multiple：$kx = x + x +….+ x$
範例
$(Z, +)$：Z是整數集合$\{-\infin…-2,-1,0,1,2,…,\infin\}$，而+則代表在這個整數群內通通使用加法運算
$(Z_n, +)$：$Z_n=\{0,1,…,n-1\}$，$Z_n$是0到n-1的整數群並且使用加法運算在$(mod\ n)$的條件之下，$(mod\ n)$才能把條件限制在n-1之下
- $\lVert Z_n \rVert = n$，$Z_n$這個整數群內的元素個數總共有n個，從0到n-1
- $-x \to n-x$：$x – x = 0\ (mod\ n) \to -x = n – x$
$(Z_p[x],+)$：集合由多項式組成而係數在$Z_q$集合內
Multiplicative Groups 乘法群
滿足群的條件，如果整個群裡面運算元使用乘法，代表這是一個乘法群，其定義如下：
- 運算元 $\odot \to *$
- 單位元素 Identity：1
- 反元素 Inverse：$x^{-1}$
- multiple：$x^{k} = x * x * … * x$
範例
$(Q\text{\textbackslash}\{0\}, *)$：Q是有理數集合排除掉0，並且這個群使用乘法運算元
$(Z_n^{*}, *)：Z_n^{*}=\{x | x \in Z_n, x\perp n\}$，$Z_n^{*}$代表這個整數群在$(mod \> n)$之下，並且整個群都是使用乘法運算元
- $\lVert Z_n^{*} \rVert = \varphi(n)$
- $x^{-1}$指的是$x^{-1} (mod\> n)$在$x \in Z_n^{*}$的條件下
