# 密碼學簡介(二)_Cryptography

這次和大家介紹進入密碼學世界前，需要知道的最基本數學工具。我們將會講到 Group(群)、Ring (環)、 Field(體)、模運算(modular arithmetic)。本文會以數學語言來描述，需要基本的集合論，會對於符號比較能理解。

---

## Group (群)
$\textit{A group G is a set together with a binary operation, denoted "*"
having the}$ $\textit{following properties,}$

$1.$ $Associativity$

$$\forall a,b,c\in G, (a*b)*c = a*(b*c)$$

$2.$ $Identity$

$$\exists e \ni \forall a\in G, e*a = a*e = a$$

$3.$ $Inverse$

$$\forall a\in G, \exists b \ni a*b = b*a = e \textit{, where e is identity element.}$$

$\textit{We say G is abelian group if}$

$$\forall a,b \in G, a*b = b*a$$

以上是群的數學定義。最簡單的例子便是整數集合$(Z, +)$配上加法運算，其中加法具有交換率，也有identity 0元素，反元素更是明顯的。甚至$(Z, +)$還是Abelian group ! 注意交換率並不是一定會有的，例如矩陣的乘法不能交換。

---

## Ring (環)
$\textit{A ring is a set R equipped with two binary operations "+" , (addition) and "⋅"}$ $\textit{(multiplication) satisfying,}$

$1.$ $\textit{R is an abelian group under addition}$

$2.$

$$\forall a,b,c\in R, (a⋅b)⋅c = a⋅(b⋅c)$$

$3.$

$$\exists e \ni \forall a\in R, e*a = a*e = a$$

$4.$

$$\forall a,b,c\in R, (a+b)⋅c = a⋅c + b⋅c$$

$5.$

$$\forall a,b,c\in R, a⋅(b+c) = a⋅c + b⋅c$$

簡單來說Ring附帶兩個運算，加法底下成abelin group，在乘法下滿足乘法交換率、分配律、單位元素等，最簡單的例子依然是$(Z, +,⋅)$，有興趣的人可以嘗試驗證看看，非常簡單。

---

## Field (體)
$\textit{A commutative ring such that the subset of
nonzero elements form a }$ $\textit{group under multiplication is called a field.}$

簡單來說體可以說是環的進階版本，首先它是一個交換環乘法運算可以交換，所有非零元素都存在著反元素，這邊可以注意到$(Z, +,⋅)$現在就不會滿足field的數學結構了(反元素是分數不落在整數集合)，但$(R, +,⋅)$就會是一個field的例子。

往後我們有機會的話將會介紹 Galois Field，跟AES 有著很大的關係，或者是ECC、Shortest vector problem、closet vector problem、lattice 、NTRU，都跟代數有很大的關係。

群、環、體，是代數最基本的基礎。代數學的領域非常廣泛，課程就有大學部代數、研究所近世代數、李代數、代數幾何、微分幾何....等等。

---

## Modulo Operation

$$Let \quad a,r,m\in Z \textit{(where Z is a set of all integers) } and \quad m > 0. \textit{We write}$$
$$a\equiv r \textit{ mod m}$$
$\textit{if m divides a-r. m is called the modulus and r is called the remainder}$

數學的符號看起來可能很複雜，但簡單來說 $x$ $mod$ $m$，就是把 $x$ 拿去除以 $m$，並取剩下的餘數。例如 $15$ $mod$ $7$ $=$ $1$，因為 $15$ 除 $7$ 餘 $1$。

接下來我們得介紹一個特殊的Ring

---

## Integer ring

$\textit{The integer ring}$ $Z_m$ $\textit{consists of}$

$1.$

$$ Z_m = \{0,1,\dots,m-1\}$$

$2.$ $\textit{Two operations “+” and “×” for all a,b ∈}$ $Z_m$ $\textit{such that:}$

$$a+b \equiv c \textit{ mod m, } (c ∈ Zm)$$

$$a×b \equiv c \textit{ mod m, } (c ∈ Zm)$$

基本的介紹到這邊，補充一個小定理，有興趣的人可以自己驗證(Hint: Euclidean Algorithm)。

> $Z_p$ $\textit{is a field}$ $\iff$ $\textit{p is a prime}$

## 代數書籍(簡單列舉兩本)

* [1] Undergraduate Algebra, Serge Lang
* [2]Abstract Algebra, 3rd Edition, David S. Dummit (Author), Richard M. Foote

---
###### tags: `Cryptography` `密碼學` `Algebra` `代數` `Group` `Ring` `Field`