# I. The Mathematical Foundations of Cryptography: Abstract Algebra

[TOC]

## Introduction
This is the first chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. This chapter teaches the elementary abstract algebra, such as Ring and Field that form the indispensable bedrock of all modern cryptosystems. These concepts are prerequisite for understanding schemes ranging from classical RSA and ECDSA to the more complex, post-quantum crpytography.

I have attempted to keep the presentation as accessible as possible, but it is common to feel confused when first encountering abstract algebra. We encourage readers to revisit this chapter multiple times or consult supplementary resources for clarity. The assumed background is roughly that of a high-school graduate.

## What is Abstract Algebra?
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of **algebraic structures**, which are sets with specific operations acting on their elements. Abstract Algebra generalizes the arithmetic we know (integers, real numbers) to more abstract structures. Instead of dealing with specific numbers, we define sets with operations (like $+$ or $\cdot$) and study the rules they follow.

## Abstract Algebra
### Group

A set $G$ equipped with a binary operation $\cdot : G \times G \to G$. The binary operation can be $+, -, \cdot , \odot, \oplus, \times, \cdots$

#### Properties:
1. **Closure:** For all $a, b \in G$, $a \cdot b \in G$.
2. **Associativity:** $(a \cdot b) \cdot c = a \cdot (b \cdot c)$
3. **Identity:** There exists $e \in G$ such that $a \cdot e = e \cdot a = a$.
4. **Inverse:** For every $a \in G$, there exists $a^{-1}$ such that $a \cdot a^{-1} = e$.

#### Example:
- The integers: $(\mathbb{Z}, +)$
- The operation on any two integers results in a integer.
- Identity is $0$. Inverse of $a$ is $-a$
- **Commutative (Abeliean): $(\mathbb{Z}, +)$**
- $a+b = b+a = c$

-----
### Ring

A set $R$ with two operations $(+, \cdot)$, we can represent a ring $(R, +, \cdot)$.

#### Properties:
1. $(R, +)$ is an abelian group.
2. $(R, \cdot)$ has multiplicative identity $e$ sometimes we just write $e$ as $1$.
3. $(R, \cdot)$ is associative. i.e., $a \cdot (b \cdot c) = (a \cdot b) \cdot c$
4. $(R, +, \cdot)$ is distributive, i.e., $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$.

#### Zero Divisors
- an element $a$ of a ring $R$ is called a left zero divisor if there exists a nonzero $x$ in $R$ such that $ax = 0$
- Zero divisors are non-zero, so $zero$ is not a zero divisors.
- Note that $(R, \cdot)$ may have zero divisors.

#### Example:
- $\mathbb{Z}$ is a ring, let's see why:
1. $\mathbb{Z}$ is an abelian group. (see the example in *Group*)
2. $\mathbb{Z}$ has multiplicative identity $e$ which is usually 1,
- i.e., $a\cdot e=e\cdot a=a$ for $a\in \mathbb{Z}$
4. $\mathbb{Z}$ is associative, e.g., $3\cdot(2\cdot4)=(3\cdot2)\cdot4$
5. $\mathbb{Z}$ is distributive. e.g., $3\cdot(2+4)=3\cdot2+3\cdot4$
- $\mathbb{Z}_6$ is also a ring.
- $\mathbb{Z}_6=\{0,1,2,3,4,5\}$, which is $\mathbb{Z}\pmod 6$, and $zero$ is $0$
- Note that in $\mathbb{Z}_6$, $2 \cdot 3 = 0$ shows the existence of zero divisors.

-----
### Ideal

A subset $I \subseteq R$ that "absorbs" multiplication from elements in $R$. This is crucial for constructing Quotient Rings ($R/I$).

#### Properties:
1. $(I, +)$ is a subgroup of $(R, +)$.
2. For any $r \in R$ and $x \in I$:
- Left Ideal: $r \cdot x \in I$.
- Right Ideal: $x \cdot r \in I$.
- Two-sided Ideal: $r \cdot x \in I$, and $x \cdot r \in I$

#### Example:
- In $\mathbb{Z}$, the set of even integers $2\mathbb{Z} = \{ \dots, -2, 0, 2, 4, \dots \}$ is an ideal.
- Even + Even = Even.
- Any Integer $\times$ Even = Even.

-----
### Finite Field
A finite field is a field $F$ with a finite number of elements, denoted $\mathbb{F}_q$ or $GF(q)$. $F^+$ is $F/\{0\}$. A field is a also a ring.
#### Properties:
1. $(F, +, \cdot)$ is a commutative ring (multiplication is commutative).
2. Multiplicative identity $e$ exists and $e \neq zero$, usually $e=1$ and $zero=0$
3. $(F^+, \cdot)$ is an abelian group.
- i.e., For every $a \neq 0$, there exists an inverse $a^{-1}$ such that $a \cdot a^{-1} = e$.
4. No zero divisors. i.e., if $a \cdot b = 0$, then $a=0$ or $b=0$.

#### Example:
- $\mathbb{Q}$ (Rational Numbers) is a field, let's see why:
1. $\mathbb{Q}$ is a commutative ring.
2. Identity is $1$.
3. Non-zero elements have inverses. e.g., for $\frac{2}{3} \in \mathbb{Q}$, the inverse is $\frac{3}{2}$ because $\frac{2}{3} \cdot \frac{3}{2} = 1$.
- $\mathbb{Z}_5$ is a finite field (integers modulo a prime $p$).
- $\mathbb{Z}_5=\{0,1,2,3,4\}$.
- Every non-zero element has an inverse. e.g., $2 \cdot 3 = 6 \equiv 1 \pmod 5$. Thus $2^{-1} = 3$.

-----
### Polynomial Ring
A polynomial ring is a set $R[x]$ of polynomials with coefficients in ring $R$.
#### Properties:
1. $R[x]$ is the set of polynomials with coefficients from a ring $R$.
2. $(R[x], +, \cdot)$ is a ring.
3. Addition is component-wise on coefficients.
4. Multiplication is determined by distributivity and $x^i \cdot x^j = x^{i+j}$.
5. If $R$ is a field, $\deg(f \cdot g) = \deg(f) + \deg(g)$.

#### Example:
- $\mathbb{Z}[x]$ is a polynomial ring, let's see why:
1. Coefficients are integers. e.g., $f(x) = 2x + 3$, $g(x) = x^2 - 1$.
2. Addition: $(2x + 3) + (x^2 - 1) = x^2 + 2x + 2$.
3. Multiplication: $3 \cdot (2x + 1) = 6x + 3$.
- $\mathbb{F}_2[x]$ is a polynomial ring over a finite field.
- Coefficients are in $\mathbb{Z}_2=\{0, 1\}$.
- Note that $(x+1)^2 = x^2 + 2x + 1 = x^2 + 1$ because $2 \equiv 0$ in $\mathbb{F}_2$.

-----
### Irreducibility of Polynomial Ring
A polynomial over a ring or field is an irreducible polynomial if it cannot be factored over that ring or field.
#### Properties:
1. A non-constant polynomial $f(x) \in R[x]$ is irreducible if it cannot be factored into $g(x)h(x)$ where both $g(x)$ and $h(x)$ have lower degree than $f(x)$.
2. Irreducibility depends entirely on the coefficient ring $R$. A polynomial can be irreducible over one ring but reducible over another.

#### Example:
- Consider $f(x) = x^2 + 1$, let's see how the ring changes irreducibility:
- **Over $\mathbb{R}$:** Irreducible.
- $x^2 = -1$ has no solution in Real numbers.
- Degree is 2 and no roots implies irreducible.
- **Over $\mathbb{C}$:** Reducible.
- Roots exist ($\pm i$).
- Factors as $(x - i)(x + i)$.
- **Over $\mathbb{Z}_2$:** Reducible.
- $f(1) = 1^2 + 1 = 2 \equiv 0$. It has a root ($1$).
- Factors as $(x+1)(x+1) = x^2 + 2x + 1 = x^2 + 1$ (since $2x \equiv 0$).

- Consider $f(x) = x^2 - 2$, let's see why it is irreducible over $\mathbb{Q}$:
- Roots are $\pm \sqrt{2}$, but $\pm\sqrt{2} \notin \mathbb{Q}$.
- Since degree is 2 and roots are not in the field, it is irreducible over $\mathbb{Q}$.

-----
### Quotient Rings of Polynomial Rings
This construction allows us to "invent" new elements (roots) that didn't exist in the original ring by "forcing" a polynomial to equal zero. It effectively extends a smaller field into a larger one.

#### Properties:
1. The quotient ring $R[x]/I$ is the set of equivalence classes defined by the Ideal $I$. Let $I=\langle p(x) \rangle$, the quotient ring is constructed as $F[x] / \langle p(x) \rangle$, consisting of the equivalence classes modulo $p(x)$.
2. Elements are represented by all polynomials in $F[x]$ with degree less than $\deg(p(x))$.
3. Addition is standard polynomial addition.
4. Multiplication is polynomial multiplication followed by modulo $p(x)$.
- i.e., $a(x) \cdot b(x) \pmod{p(x)}$.
5. If $p(x)$ is irreducible over $F$, the quotient ring is a Field.

#### Example:
- $\mathbb{R}[x] / \langle x^2 + 1 \rangle$ is the Complex Numbers $\mathbb{C}$, let's see why:
1. $p(x) = x^2 + 1$ is irreducible in $\mathbb{R}$ (no real number squares to -1).
2. Elements look like $a + bx$ (degree < 2), which matches $a + bi$.
3. In this ring, $x^2 + 1 \equiv 0 \implies x^2 \equiv -1$.
4. Multiplication: $(1+x)(1-x) = 1 - x^2 = 1 - (-1) = 2$.
- $\mathbb{Z}_2[x] / \langle x^2 + x + 1 \rangle$ is the Finite Field $GF(4)$.
- Coefficients are in $\mathbb{Z}_2=\{0, 1\}$.
- Elements are $\{0, 1, x, x+1\}$.
- $x^2 \equiv x + 1$. (Since $x^2 + x + 1 = 0 \implies x^2 = -x - 1$, and in $\mathbb{Z}_2$, $-1 = 1$).
- Multiplication example: $x \cdot x = x^2 = x + 1$.

-----
### The n-th Root of Unity

A complex number $z$ satisfying the equation $z^n = 1$. We usually denote the set of these solutions as $U_n$.

#### Properties:
1. $(U_n, \cdot)$ is a cyclic group of order $n$.
2. The modulus of every root is 1. i.e., $|z| = 1$. They lie on the unit circle in the complex plane.
3. The solutions are given by de Moivre's formula, for $k = 0, 1, \dots, n-1$: $$z_k = e^{i \frac{2\pi k}{n}}= \cos(\frac{2\pi k}{n}) + i \sin(\frac{2\pi k}{n}) $$
4. The sum of all $n$-th roots of unity is 0 (for $n > 1$). i.e., $\sum_{k=0}^{n-1} z_k = 0$
5. Visualization of root of unity in a unit circle centering at (0,0).

#### Primitive Root of Unity
- An element $\zeta$ in $U_n$ is called a **primitive root** if it generates the entire group $U_n$.
- i.e., the powers $\{\zeta^1, \zeta^2, \dots, \zeta^n\}$ are distinct and cover all roots.
- There are exactly $\phi(n)$ primitive roots, where $\phi$ is Euler's totient function.
- Note that if $\zeta$ is a primitive root, then $\zeta^k$ is primitive if and only if $$\gcd(k, n) = 1$$

#### Example:
- $U_4$ (The 4th roots of unity) consists of $\{1, i, -1, -i\}$, let's see why:
1. **Verification:** Every element $z \in U_4$ satisfies $z^4 = 1$.
- $1^4 = 1$
- $i^4 = (i^2)^2 = (-1)^2 = 1$
- $(-1)^4 = ((-1)^2)^2 = 1^2 = 1$
- $(-i)^4 = (-1)^4 \cdot i^4 = 1 \cdot 1 = 1$
2. **Geometric Spacing:** The roots divide the unit circle into $n=4$ equal parts. (Angles are $0^\circ, 90^\circ, 180^\circ, 270^\circ$).
3. **Sum Property:** $1 + i + (-1) + (-i) = (1 - 1) + (i - i) = 0$.
- Let's check which roots are **Primitive** in $U_4$:
- Consider $i\rightarrow (i^1,i^2, i^3, i^4) = (i, -1, -i, 1)$
- $i$ generated all 4 distinct elements $\{i, -1, -i, 1\}$. Thus, $i$ is a primitive root.
- Consider $-1\rightarrow\left((-1)^1, (-1)^2, (-1)^3\right) = (-1, 1, -1)$
- $-1$ only generated $\{-1, 1\}$, so $-1$ is not a primitive root.
- **GCD Check:**
- For $i$, which is $\zeta^1$, the $\gcd(1, 4) = 1$, so $i$ is primitive.
- For $-1$, which is $\zeta^2$, the $\gcd(2, 4) = 2 \neq 1$, so $-1$ is not primitive.

-----
### Cyclotomic Polynomial

For a positive integer $n$, the $n$-th cyclotomic polynomial, denoted $\Phi_n(x)$, is the polynomial whose roots are exactly the **primitive** $n$-th roots of unity. Cyclotomic Polynomial is widely used in Lattice based Cryptography. We will introduce FFT in following chapters, which is important building block in it and uses the properties of the n-th root of unity.

#### Properties:
1. **Definition by Roots:** $\Phi_n(x) = \prod_{\substack{1 \le k < n, \\ \gcd(k, n)=1}} (x - \zeta^k)$, where $\zeta = e^{\frac{2\pi i}{n}}$
2. **Integer Coefficients:** $\Phi_n(x)$ always has integer coefficients, even though the roots are complex numbers.
3. **Irreducibility:** $\Phi_n(x)$ is irreducible over $\mathbb{Q}$.
4. **Degree:** The degree of $\Phi_n(x)$ is $\phi(n)$ (Euler's totient function).
5. **Fundamental Identity:** $x^n - 1 = \prod_{d | n} \Phi_d(x)$. This property is the standard way to compute them recursively.

#### $2^k$-Cyclotomic Polynomial
We often use cyclotomic polynomial $\Phi_{2^k}(x)$ as the quotient of polynomial rings since they have special properties with their roots of unity. We will see the feature in [Chapter VI](https://hackmd.io/@spockwall/BJclme13yg).

#### Example:
- see [Cyclotomic polynomial (wiki)](https://en.wikipedia.org/wiki/Cyclotomic_polynomial)

---
### Chinese Remainder Theorem (CRT)

Chinese Remainder Theorem (CRT) is an important algorithm that used in **Residue Number System**. By leveraging the properties of it, a cryptographic scheme over large numbers can be incredibly accelerated.

#### Properties:
1. **Pairwise Coprime Condition:** The moduli $n_1, n_2, \dots, n_k$ must satisfy $\gcd(n_i, n_j) = 1$ for all $i \neq j$.
2. **Uniqueness:** There exists a unique solution for $x$ modulo $N$, where $N = n_1 \cdot n_2 \cdot \dots \cdot n_k$.
3. **Existence:** The solution can be explicitly constructed using modular inverses.
4. **Ring Isomorphism:** The ring $\mathbb{Z}_N$ is isomorphic to the product ring $\mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \dots \times \mathbb{Z}_{n_k}$.
- i.e., Operations in the large ring $\mathbb{Z}_N$ can be performed independently in the smaller components.

#### Example:
This CRT example demonstrate the Ring Isomorphism property $\mathbb{Z}_{15} \cong \mathbb{Z}_3 \times \mathbb{Z}_5$
#### Example:
- **Step 1:**
- Map an integer $n \in \mathbb{Z}_{15}$ to a pair $(a, b)$ where $a = n \pmod 3$ and $b = n \pmod 5$. Donoted the mapping as $\mathcal{C}(X): \mathbb{Z}_{15}\rightarrow\mathbb{Z}_{3}\times\mathbb{Z}_{5}$
- **Step 2: Addition**
- Add $7$ and $13$ in $\mathbb{Z}_{15}$:
- $7 + 13 = 20 \equiv 5 \pmod{15}$.
- Now, let's add them in the product ring $\mathbb{Z}_3 \times \mathbb{Z}_5$:
- $\mathcal{C}(7) = (1, 2)$.
- $\mathcal{C}(13) = (1, 3)$.
- $\mathcal{C}(7)+\mathcal{C}(13)=(1+1, 2+3) = (2, 5) \equiv (2, 0)$
- **Verificaiton:** Does $(2, 0)$ correspond to $5$? **Yes**
- $5 \pmod 3 = 2$.
- $5 \pmod 5 = 0$.
- **Step 3: Multiplication:**
- Multiply $7$ and $13$ in $\mathbb{Z}_{15}$:
- $7 \cdot 13 = 91\equiv 1 \pmod{15}$
- Now, let's multiply them in the product ring $\mathbb{Z}_3 \times \mathbb{Z}_5$:
- $\mathcal{C}(7)\,\odot\,\mathcal{C}(13)=(1 \cdot 1, 2 \cdot 3) = (1, 6)\equiv(1, 1)$
- **Result:** Does $(1, 1)$ correspond to $1$? **Yes**
- $1 \pmod 3 = 1$.
- $1 \pmod 5 = 1$.

## Reference
- https://www.youtube.com/watch?v=h7apO7q16V0