密碼學簡介(二)_Cryptography

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

---

Group (群)

$\mathit{\text{A group G is a set together with a binary operation, denoted "*" having the}}$

$\mathit{\text{following properties,}}$

$1.$

$Associativity$

$$\mathrm{\forall }a,b,c\in G,(a\ast b)\ast c=a\ast (b\ast c)$$

$2.$

$Identity$

$$\mathrm{\exists }e\ni \mathrm{\forall }a\in G,e\ast a=a\ast e=a$$

$3.$

$Inverse$

$$\mathrm{\forall }a\in G,\mathrm{\exists }b\ni a\ast b=b\ast a=e\mathit{\text{, where e is identity element.}}$$

$\mathit{\text{We say G is abelian group if}}$

$$\mathrm{\forall }a,b\in G,a\ast b=b\ast a$$

以上是群的數學定義。最簡單的例子便是整數集合

$(Z,+)$配上加法運算，其中加法具有交換率，也有identity 0元素，反元素更是明顯的。甚至

$(Z,+)$還是Abelian group ! 注意交換率並不是一定會有的，例如矩陣的乘法不能交換。

---

Ring (環)

$\mathit{\text{A ring is a set R equipped with two binary operations "+" , (addition) and "⋅"}}$

$\mathit{\text{(multiplication) satisfying,}}$

$1.$

$\mathit{\text{R is an abelian group under addition}}$

$2.$

$$\mathrm{\forall }a,b,c\in R,(a\cdot b)\cdot c=a\cdot (b\cdot c)$$

$3.$

$$\mathrm{\exists }e\ni \mathrm{\forall }a\in R,e\ast a=a\ast e=a$$

$4.$

$$\mathrm{\forall }a,b,c\in R,(a+b)\cdot c=a\cdot c+b\cdot c$$

$5.$

$$\mathrm{\forall }a,b,c\in R,a\cdot (b+c)=a\cdot c+b\cdot c$$

簡單來說Ring附帶兩個運算，加法底下成abelin group，在乘法下滿足乘法交換率、分配律、單位元素等，最簡單的例子依然是

$(Z,+,\cdot )$，有興趣的人可以嘗試驗證看看，非常簡單。

---

Field (體)

$\mathit{\text{A commutative ring such that the subset ofnonzero elements form a }}$

$\mathit{\text{group under multiplication is called a field.}}$

簡單來說體可以說是環的進階版本，首先它是一個交換環乘法運算可以交換，所有非零元素都存在著反元素，這邊可以注意到

$(Z,+,\cdot )$現在就不會滿足field的數學結構了(反元素是分數不落在整數集合)，但

$(R,+,\cdot )$就會是一個field的例子。

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

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

---

Modulo Operation

$$Leta,r,m\in Z\mathit{\text{(where Z is a set of all integers) }}andm>0.\mathit{\text{We write}}$$

$$a\equiv r\mathit{\text{ mod m}}$$

$\mathit{\text{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

$\mathit{\text{The integer ring}}$

$Z_m$

$\mathit{\text{consists of}}$

$1.$

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

$2.$

$\mathit{\text{Two operations “+” and “×” for all a,b ∈}}$

$Z_m$

$\mathit{\text{such that:}}$

$$a+b\equiv c\mathit{\text{ mod m, }}(c\in Zm)$$

$$a\times b\equiv c\mathit{\text{ mod m, }}(c\in Zm)$$

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

$Z_p$

$\mathit{\text{is a field}}$

$⟺$

$\mathit{\text{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