# Finite Fields

## Groups, Rings, and Fields

- Fields are a subset of rings, which are a subset of the groups.
- Groups are defined by a simple set of properties. Each successive subset adds additional properties and is thus more complex.
- 同一集合中的兩個元素以多種方式組合後得到的元素，仍在同一個集合內
- 這些特殊的運算規則定義了集合的性質


## Group

A group $G$, sometimes denoted by $\{G, \cdot\}$, is a set of elements with a **binary operation** denoted by $\cdot$ that associates to each ordered pair (a, b) of elements in G an element $(a \cdot b)$ in $G \times G$, such that the following axioms are obeyed:

> The operator $\cdot$ is generic and can refer to **addition, multiplication, or some other mathematical operation**.

- **(A1)** Closure: If $a$ and $b$ belong to $G$, then $a \cdot b$ is also in $G$.
- **(A2)** Associative: $a \cdot (b \cdot c) = (a \cdot b) \cdot c$ for all $a, b, c$ in $G$.
- **(A3) Identity element**: There is an element $e$ in $G$ such that $a \cdot e = e \cdot a = a$ for all $a$ in $G$.
- **(A4)** Inverse element: For each $a$ in $G$, there is an element $a^\prime$ in $G$ such that $a \cdot a^\prime = a^\prime \cdot a = e$.

<!--  -->

### Abelian Group

A group is said to be **abelian** (also called commutative) if it satisfies the following additional condition:

- **(A5)** Commutitive: $a \cdot b = b \cdot a$ for all $a, b$ in $G$.

Example:

- The set of **integers** (positive, negative, and 0) under **addition** is an abelian group.
- The set of **nonzero real numbers** under **multiplication** is an abelian group.

<!--  -->

### Cyclic Group

- Define exponentiation within a group as **repeated application** of operator
- Example: $a^3 = a \cdot a \cdot a$
- Define $a^0 = e$ as the identity element.
- A group $G$ is cyclic if every element in $G$ is a power $a^k$ ($k$ is integer) of some fixed element $a \in G$.

## Ring

https://math.ntnu.edu.tw/~li/algebra-html/chap5.pdf

A ring $R$, sometimes denoted by $\{R, +, \times\}$, is a set of elements with **two** binary operations, called **addition** and **multiplication**, such that for all $a, b, c$ in $R$ the following axioms are obeyed.

- **(A1 - A5)** R is an **abelian group** with respect to **addition**; that is, R satisfies axioms A1 through A5. For the case of an additive group, we denote the identity element as 0 and the inverse of a as -a.
- 在加法運算下是一個 abelian group
- 乘法僅要求封閉性和結合律
- **(M1) Closure under multiplication**: If $a$ and $b$ belong to $R$, then $ab$ is also in $R$.
- **(M2) Associativity of multiplication**: $a(b + c) = ab + ac$ for all $a, b, c$ in $R$.
- **(M3) Distributive laws**:
$a(b + c) = ab + ac$ for all $a, b, c$ in $R$.
$(a + b)c = ac + bc$ for all $a, b, c$ in $R$.

本質上 ring 是一個可以在其中進行加法、減法 [$a - b = a + (-b)$] 與乘法的集合（運算後結果仍在集合中）。

<!--  -->

### Commutative Ring

A ring is said to be **commutative** if it satisfies the following additional condition:

- **(M4) Commutativity of multiplication**: $ab = ba$ for all $a, b$ in $R$.

<!--  -->

### Integral Domain

Define an integral domain, which is a **commutative ring** that obeys the following axioms.

- **(M5) Multiplicative identity**: There is an element 1 in $R$ such that $a1 = 1a = a$ for all $a$ in $R$.
- **(M6) No zero divisors**: If $a, b$ in $R$ and $ab = 0$, then either $a = 0$ or $b = 0$.

## Field

https://ccckmit.gitbooks.io/rlab/content/field.html

A field F, sometimes denoted by $\{F, +, \times\}$, is a set of elements with **two** binary operations, called **addition** and **multiplication**, such that for all $a, b, c$ in $F$ the following
axioms are obeyed.

- **(A1 - M6)** $F$ is an **integral domain**; that is, $F$ satisfies axioms A1 through A5 and M1 through M6.
- **(M7) Multiplicative inverse**: For each $a$ in $F$, except 0, there is an element $a^{-1}$ in $F$ such that $aa^{-1} = (a^{-1})a = 1$.

本質上 field 是一個可以在其中進行加法、減法、乘法與除法的集合。除法定義為 $a / b = a(b^{-1})$。

Field 範例：

- **有理數**：$\{\mathbb{Q}, +, \times\}$
- **實數**：$\{\mathbb{R}, +, \times\}$
- **複數**：$\{\mathbb{C}, +, \times\}$
- 由於整數中只有 1 與 -1 有乘法反元素，因此**整數不是一個 field**。

<!--  -->

### Properties of Groups, Rings, and Fields


## Finite Fields

- $\equiv$ ==Galois Fields==
- Finite fields are of increasing importance in Cryptography
- The finite field of **order**（[階](https://zh.wikipedia.org/wiki/階_(群論))，元素的個數）$p^n$, where p is a prime, is generally written $GF(p^n)$
- Special Finite Fields
- $GF(p)$: Prime Field
- The set of integers $\{0, 1, \dots, p − 1\}$ with arithmetic operations modulo prime $p$.
- $GF(2^n)$: Binary Field


:::info
Example: $GF(2)$ is the simplest finite field.

**Addition** is equivalent to the **XOR** operation, and **Multiplication** is equivalent to the logical **AND** operation.

:::

### Generator of Finite Field

- A generator $g$ of a finite field $F$ of order $q$ (contains q elements) is an element whose first $q − 1$ powers generate all the nonzero elements of $F$
- The $q$ element of $F$
- $0, g^0, g^1, g^2, ..., g^{q-2}$

## Prime Field GF\(p\)

- The set of integers $\{0, 1, \dots, p−1\}$ with arithmetic operations modulo prime $p$.
- Example
-

### Finding the Multiplicative Inverse in GF\(p\)


## Polynomial Arithmetic

$$
f(x) = a_nx^n + a_{n - 1}x^{n - 1} + \cdots + a_1x + a_0 = \sum^n_{i = 0} a_ix^i
$$

Degree: n

### Treatment of Polynomials


- Three Classes of Polynomial Arithmetic
- **Ordinary polynomial arithmetic**, using the basic rules of algebra.
- **Polynomial arithmetic** in which the **coefficients are in** $GF(p)$.
- Polynomial arithmetic in which the coefficients are in $GF(p)$, and the **polynomials are defined modulo a polynomial** $m(x)$ whose highest power is some integer $n$.

### Ordinary Polynomial Arithmetic

- add or subtract corresponding coefficients
- multiply all terms by each other
- Example
$$
\text{let } f(x) = x^3 + x^2 + 2 \text{ and } g(x) = x^2 - x + 1 \\
\begin{aligned}
f(x) + g(x) &= x^3 + 2x^2 - x + 3 \\
f(x) - g(x) &= x^3 + x + 1 \\
f(x) \times g(x) &= x^5 + 3x^2 - 2x + 2
\end{aligned}
$$

## Polynomial Arithmetic with Modulo Coefficeients

- **when computing value of each coefficient do calculation modulo some value**
- forms a polynomial ring
- could be modulo any prime
- most interested in **mod 2**
- i.e., all coefficients are **0 or 1**
- Example
- 
- Polynomial Division
- $f(x) = q(x) \times g(x) + r(x)$
- $r(x) = f(x)\ mod\ g(x)$
- if r(x) = 0, g(x) divides f(x)
- if g(x) has no divisors other than itself & 1, then it is an **irreducible polynomial** ($\equiv$ prime polynomial)
- arithmetic modulo an irreducible polynomial forms a **field**
- Examples: Polynomial Arithmetic over $GF(2)$
（減法與加法都是 XOR 運算）

## Binary Field $GF(2^n)$

### Computation in $GF(2^n)$

- polynomials with **coefficients modulo 2**
- **degree < n**
- hence must **reduce modulo an irreducible poly of degree n** (**for multiplication only**)
- Multiplicative Inverse
- by using the **Extended Euclidean Algorithm**

### Elements of $GF(2^n)$

- Example: 8 Elements of $GF(2^3)$
- Polynomial Representation (form: $\Box x^2 + \Box x + \Box 1$)
$\Rightarrow 0, 1, x, x + 1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1$
- Binary Representation (form: $\Box\Box\Box$)
- 000, 001, 010, 011, 100, 101, 110, 111

### Addition in $GF(2^n)$

- Example: Addition in $GF(2^3)$
- Polynomial Representation
- Binary Representation
- bitwise $\oplus$

### Multiplication in $GF(2^n)$

- Example: Multiplication in $GF(2^3)$
- Polynomial Representation
- using the irreducible poly of degree 3: $x^3 + x + 1$
- 要標明是使用什麼 irreducible poly，若有其他符合的 irreducible poly 也可以使用
- Binary Representation

### Additive and Multiplicative Inverses in $GF(2^n)$

- Example: Additive and Multiplicative Inverses in $GF(2^3)$
- Calculate the Multiplicative Inverse in $GF(2^n)$
- Calculate $a^{−1}(x) \bmod m(x)$ by using the **Extended Euclidean Algorithm**
- $\gcd(m(x), a(x)) = 1$
- degree of $a(x)$ < the degree of $m(x)$
- Example: Compute $(x^7 + x + 1)^{−1} \bmod x^8 + x^4 + x^3 + x + 1$
- $(x^7 + x + 1)^{−1} \bmod x^8 + x^4 + x^3 + x + 1 = x^7$

### Computational Considerations for $GF(2^n)$

- Represent polynomials as **bit strings**
- **Addition** $\Rightarrow$ ==XOR==
- $(x^2 + 1) + (x^2 + x + 1) = x \Rightarrow 101 \oplus 111 = 010$
- **Multiplication** $\Rightarrow$ ==shift & XOR==
- $(x + 1) \cdot (x^2 + 1) = x \cdot (x^2 + 1) + 1 ·(x^2 + 1) = x^3 + x^2 + x + 1$
$\Rightarrow 011 \cdot 101 = ((101) \ll 1) \oplus ((101) \ll 0) = 1010 \oplus 101 = 1111$
- **Polynomial Modulo Reduction** $\Rightarrow$ ==shift & XOR==
- $(x^3 + x^2 + x + 1) \bmod (x^3 + x + 1) = 1 \cdot (x3 + x + 1) + (x^2) = x^2$
$\Rightarrow 1111 \bmod 1011 = 1111 \oplus 1011 = 0100$