---
# System prepended metadata

title: 'Ch02: Introduction to Number Theory'
tags: [密碼學]

---

<style>
  .red {
    color: red;
    font-weight: bold;
  }
</style>


# Introduction to Number Theory

::: danger
數論探討的皆為**整數**。
:::

## Divisibility 整除

A non-zero number $b$ divides $a$ if for some $m$ have 
$$
a = mb\Rightarrow b\mid a
$$

- $-5\mid 30$
- $17\mid 0 \quad (0 = 0 \times 17)$

Simple properties of divisibility:

- If $a\mid 1$, then $a = \pm 1$
- If $a\mid b$ and $b\mid a$, then $a = \pm b$.
- Any $b \ne 0$ divides 0.
- If $a\mid b$ and $b\mid c$, then $a\mid c$.
- If $b\mid g$ and $b\mid h$, then $b\mid (mg + nh)$ for arbitrary integers $m$ and $n$.

![](https://hackmd.io/_uploads/B17jaiwxa.png =500x)


## Greatest Commom Divisor (GCD)

最大公因數

$\gcd(a, b) = \max[k$, such that $k | a$ and $k | b]$

GCD 不會是負的，$\gcd(a, b) = \gcd(|a|, |b|)$


## Euclidean Algorithm

![](https://hackmd.io/_uploads/Byu4CUrlp.png =500x)

- Based on $\gcd(a, b) = \gcd(b, a\bmod b)$ 

## Modular Arithmetic

模運算

$a = qn + r\quad 0\le r\lt n; q = \lfloor a/n \rfloor$

### Congruence（同餘）

If $(a\bmod n) = (b\bmod n)$, this is written as ==$a\equiv b\pmod n$==.

:::info
If $a\equiv 0\pmod n$, then $n\mid a$.
:::

#### Properties

- $a\equiv b\pmod n$ if $n\mid (a - b)$.
- $a\equiv b\pmod n$ implies $b\equiv a\pmod n$.
- $a\equiv b\pmod n$ and $b\equiv c\pmod n$ imply $a\equiv c\pmod n$.
  - ex. $23\equiv 8\pmod 5$ because $23 - 8 = 15 = 5 \times 3$

### Modular Arithmetic Operation

$\pmod n$ 運算的結果都會在 $\{0, 1,\dots, (n - 1)\}$

1. $[(a\bmod n) + (b\bmod n)]\bmod n = (a + b)\bmod n$
2. $[(a\bmod n) - (b\bmod n)]\bmod n = (a - b)\bmod n$
3. $[(a\bmod n) \times (b\bmod n)]\bmod n = (a \times b)\bmod n$

#### Modular Division

$a / b \bmod n = a \times b^{-1} \bmod n$

:::danger
只有在 $b$ 與 $n$ 互質時，$b^{-1} \bmod n$ 才會存在。
:::

- $(x \bmod n / y \bmod n) \bmod n = (x / y) \bmod n$
- $(4 / 3) \bmod 5 = 4 \times 3^{-1} \bmod 5 = 4\times 2 \bmod 5 = 3$
  - $3\times 2 \bmod 5 = 1, 3^{-1} \bmod 5 = 2$

---

- Additive Identity: 0
- Multiplicative Identity: 1

![](https://hackmd.io/_uploads/Hk7_Whwgp.png)

### Set of Residues

$Z_n = \{0, 1, ..., n-1\}$ is the $\text{Set of Residues}\pmod n$
- also called Residue Classes (mod n)

  ![](https://hackmd.io/_uploads/SkmN0nvgp.png =500x)


### Properties of Modular Arithmetic

![](https://hackmd.io/_uploads/Byw9C2we6.png =800x)

#### Property of Modular Addition in Congruence

:::success
**if** $(a + b)\equiv (a+c)\pmod n$ **then** $b\equiv c\pmod n$
$\Rightarrow ((-a) + a + b)\equiv ((-a) + a + c)\pmod n$
$\Rightarrow b\equiv c\pmod n$
:::

#### Property of Modular Multiplication in Congruence

:::success
**if** $(a \times b)\equiv (a \times c)\pmod n$ **then** $b\equiv c\pmod n$ **if** ***a is relatively prime to n***
$\Rightarrow ((a^{-1})ab)\equiv ((a^{-1})ac)\pmod n$
$\Rightarrow b\equiv c\pmod n$
:::

![](https://hackmd.io/_uploads/Sk9Bp4Kka.png =800x)

## Extended Euclidean Algorithm

:::danger
要記怎麼算，考試不會給算式。
:::

- Can caculate not only $\gcd(a, b)$ but also x and y:

  :::success
  $ax + by = d = \gcd(a, b)$
  
  Suppose that $ax + by = \gcd(a, b) = d = 1$
  $\Rightarrow (ax + by) \text{ mod a} = 1 \text{ mod a}= 1$
  $\Rightarrow (b)(y) \text{ mod a} = 1 \Rightarrow y = b^{-1} \text{ mod a}$
  :::

Calculating Modular Inverse $b^{-1}\bmod a$:

1. $(A1, A2, A3) = (1, 0, a)$  
   $(B1, B2, B3) = (0, 1, b)$
2. If $B3 = 0$, return "no inverse"
3. If $B3 = 1$, return $B2 \bmod a$
4. $Q = A3 / B3$
5. $(T1, T2, T3) = (A1 - Q\times B1, A2 - Q\times B2, A3 - Q\times B3)$
6. $(A1, A2, A3) = (B1, B2, B3)$
7. $(B1, B2, B3) = (T1, T2, T3)$
8. goto 2.

Ex. $314^{-1}\bmod 1753$

| Q | A2 | A3 | B2 | B3 |
|:---:|:---:|:---:|:---:|:---:|
| - | 0 | 1753 | 1 | 314 |
| 5 | 1 | 314 | -5 | 183 |
| 1 | -5 | 183 | 6 | 131 |
| 1 | 6 | 131 | -11 | 52 |
| 2 | -11 | 52 | 28 | 27 |
| 1 | 28 | 27 | -39 | 25 |
| 1 | -39 | 25 | 67 | 2 |
| 12 | 67 | 2 | **-843** | 1 |

Inverse = B2 mod a = -843 mod 1753 = ==910==

## Prime Numbers

大質數：至少 1000 bits (1024)

- An integer $p > 1$ is a **prime number** if and only if its only divisors are $\pm 1$ and $\pm p$.
- Features
  - infinite number of prime numbers
  - many public-key algorithms use **large prime numbers**
  - prime numbers are central to number theory
- Prime Factorization
  - the **prime factorization** of a number n is to write it as a product of prime numbers
  - Examples
    - $91 = 7 \times 13$
    - $3600 = 2^4 \times 3^2 \times 5^2$
  - **factoring a number is relatively hard** compared to multiplying the factors together to generate the number

## Modular Exponentiation Methods

==$x^e \bmod n$==

- Example: compute $x^3 \bmod n$
  - Direct calculation:  
    $x^3 \bmod n = x \times x \times x \bmod n$
  - Mod the intermediate values:  
    $x^3 \bmod n = (x \times x \bmod n) \times x \bmod n$
- Example:
  - Direct calculation:  
    $x^{1000} \bmod n = x \times\dots\times x \times x \bmod n$
    - ❌數字太大
  - Mod the intermediate values:  
    $x^{1000} \bmod n = (\dots((x \times x \bmod n)\times\dots)\times\dots)\times x \bmod n$
    - ❌999 modular multiplication operations

### Binary Method

- Simple
- Types
  - **Right-to-Left** binary method
  - **Left-to-Right** binary method
- Computing $x^e \bmod n$
  $$
  r = \lfloor\log_2e\rfloor + 1 \\
  e = \sum^{r - 1}_{j = 0}(e_j\times 2^j)\ \text{where}\ e_j\in \{0, 1\}
  $$
  （把 $e$ 以二進位表示）

#### Right-to-Left Binary Method

1. $M = 1, T = x$.
2. 由**右到左**取出 $e$ 的每一位 (j = 0 ~ r - 1) $e_j$，若 $e_j = 1, M = M\times T \bmod n$。
3. $T = T^2 \bmod n$.
4. 重複 2. ~ 3. 直到遍歷 $e$ 的每一位。
5. $M$ 為結果。

![](https://hackmd.io/_uploads/ry1bQePlp.png =500x)

#### Left-to-Right Binary Method

- 不需要 $T$ 作為 buffer。

1. $M = 1$.
2. 由**左到右**取出 $e$ 的每一位 (j = r - 1 ~ 0) $e_j$。
3. $M = M^2 \bmod n$.
4. 若 $e_j = 1, M = M\times x \bmod n$。
5. 重複 2. ~ 4. 直到遍歷 $e$ 的每一位。
6. $M$ 為結果。

![](https://hackmd.io/_uploads/ry0BNgDea.png =500x)

### Montgomery's Method

Based on **Left-to-Right binary method** and **Extended Euclidean algorithm**.

（常在計算大數時使用）

![](https://hackmd.io/_uploads/HkzvobDgp.png =500x)
![](https://hackmd.io/_uploads/SJISobDl6.png =800x)

## Fermat’s Theorem

If $p$ is prime and $a \in \mathbb{Z}^+$ such that $\gcd(a, p) = 1$, then $a^{p - 1} \equiv 1 \pmod p$.

:::info
Proof:

考慮有一個小於 $p$ 的正整數集合 $\{1, 2, \dots, p - 1\}$，將所有元素乘 $a$ 並模 $p$，得到集合 $X = \{a \bmod p, 2a \bmod p, \dots, (p - 1)a \bmod p\}$。

由於 $p$ 不整除 $a$，$X$ 的元素皆不為 0，且 $X$ 中任兩個整數皆不相同。要證明這點可以假設 $ja \equiv ka \pmod p, 1 \le j < k \le p - 1$，由於 $a$ 與 $p$ 互質，可以消掉等式兩邊的 $a$，得到 $j \equiv k \pmod p$，但根據一開始的條件，此等式不成立。因此可以得知 $X$ 內的 $(p - 1)$ 個元素皆為正整數且互不相等。

我們可以得出 $X$ 包含某種排列的整數集合 $\{1, 2, \dots, p - 1\}$，將這兩個集合內的數字各自乘起來並將結果模 $p$ 可以得到

$$
\begin{align}
a \times 2a \times \cdots \times (p - 1)a &\equiv [1 \times 2 \times \cdots \times (p - 1)] \pmod p \\
a^{p - 1}(p - 1)! &\equiv (p - 1)! \pmod p
\end{align}
$$

由於 $(p - 1)!$ 與 $p$ 互質，可以將其從等式兩邊消去，得到以下等式

$$
a^{p - 1} \equiv 1 \pmod p
$$

得證。
:::

<https://oi-wiki.org/math/number-theory/fermat/>

## Euler's Theorem

### Euler Totient Function $\phi(n)$ (唸 phi)

The **number of elements** in the reduced set of residues（餘數）of $n$.

- Complete set of residues of $n: \{0, 1, 2, \dots, n - 1\}$
- Reduced set of residues of $n$
  - The set of all residues are relatively prime（互質）to $n$.
- If n is a prime, $\phi(n) = n - 1$

:::success
**Example**

Suppose that n=10

the **complete set of residues** of $n: \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
the **reduced set of residues** of $n: \{1, 3, 7, 9\}$
Therefore, $\phi(10) = 4$
:::

### Formula for Computing $\phi(n)$

If $n = p_1^{E_1} \times p_2^{E_2} \times ... \times p_k^{E_k}$, then

$\phi(n) = p_1^{E_1} \times p_2^{E_2} \times ... \times p_k^{E_k} \times (1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) ... (1 - \frac{1}{p_k})$

$= n \times (1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) ... (1 - \frac{1}{p_k})$

where $p_1, p_2, ..., p_k$ are distinct primes.

:::success
**Example**

- $7 = 7^1$
  $\phi(7) = 7^1 \times (1 - \frac{1}{7}) = 7 \times \frac{6}{7} = 6$
- $10 = 2^1 \times 5^1$
  $\phi(10) = 2^1 \times 5^1 \times (1 - \frac{1}{2})(1 - \frac{1}{5}) = 2 \times 5 \times (\frac{1}{2})(\frac{4}{5}) = 4$

![](https://hackmd.io/_uploads/H12Kqg_xp.png =800x)

:::

### Description of Euler's Theorem

$$
\text{If } \gcd(a, n) = 1, \text{ then } a^{\phi(n)} \equiv 1 \pmod n
$$

- Note that **Fermat’s Theorem** is a ==special case== of Euler’s Theorem
  - If $n$ is a prime, we have $\phi(n) = n − 1$.
- Example 1
  - If $n = 10$, then $\phi(10) = 4$
  - Verify
    - When $a = 1, \gcd(1, 10) = 1 \rightarrow a^{\phi(n)} \equiv 1^4 \equiv 1 \pmod {10}$
    - When $a = 3, \gcd(3, 10) = 1 \rightarrow a^{\phi(n)} \equiv 3^4 \equiv 1 \pmod {10}$
    - When $a = 7, \gcd(7, 10) = 1 \rightarrow a^{\phi(n)} \equiv 7^4 \equiv 1 \pmod {10}$
    - When $a = 9, \gcd(9, 10) = 1 \rightarrow a^{\phi(n)} \equiv 9^4 \equiv 1 \pmod {10}$
- Example 2
  - > Q: Compute $5^{1202} \pmod {13}$
  1. $\gcd(5, 13) = 1 \Rightarrow 5^{\phi(13)} = 5^{12} \equiv 1 \pmod {13}$
  2. $5^{1202} = 5^{12^{100}} \times 5^2$
  3. $5^{1202} \equiv 5^{12^{100}} \times 5^2 \equiv 25 \equiv 12 \pmod {13}$


### Euler’s Theorem can be use to compute Modular Inverse

:::info
Compute $b^{-1} \pmod a$

Base on Euler's Theorem, we have $b^{\phi(a)} \equiv 1 \pmod a$
$\Rightarrow b \times b^{\phi(a)-1} \equiv 1 \pmod a$
$\Rightarrow b^{-1}\ mod\ a = b^{\phi(a)-1}\ mod\ a$

If $\phi(a)$ is known, we can obtain $b^{−1} \pmod a$ by computing $b^{\phi(a) − 1} \pmod a$.


However, **Extended Euclidean Algorithm** is far **more efficient**
than this method.
:::

## Primality Test

Random Prime Generation 

- generate a Random Number R
- test if R is prime or not by a **Primality Test** method

Primality Test Methods:

- **Probabilistic** Primality Test Methods
  - Fermat Primality Test
  - Jacobi Primality Test
  - **Miller-Rabin Primality Test** (most popular)
- **Deterministic** Primality Test Methods
  - **Agrawal-Kayal-Saxena’s (AKS) Primality Test**

### Miller-Rabin Primality Test

- 前置：
  1. $1^2 \bmod\ p \equiv {(-1)}^2 \bmod\ p \equiv 1 \bmod\ p\ \to\ 1, -1\ 都是\ 1 \bmod\ p\ 的「平凡平方根」$ 
  2. $p$ 是質數且 $p > 2$, 不存在 $1 \bmod\ p$ 的「非平凡平方根」
    :::info
    試證：
        &emsp;&emsp;設 $x$ 是 $1\ \bmod\ p$ 的平方根之一
        &emsp;&emsp;有下列推導
        \begin{aligned}
            x^2\ &\equiv\ 1\ \bmod\ p \\
            x^2 - 1\ &\equiv\ 0\ \bmod\ p \\
            (x+1)(x-1)\ &\equiv\ 0\ \bmod\ p \ &— 1式
        \end{aligned}
        &emsp;&emsp;1式指出$(x+1)$ 或 $(x-1)$ **可以整除質數 p**
        &emsp;&emsp;則 $x = 1\ or\ -1$
        &emsp;&emsp;即 $x$ 是 $1\ \bmod\ p$ 的「平凡平方根」
    透過反證法證畢
    :::
- 概念：
    設 $n$ 是質數且 $n > 2$
    則 $n - 1$ 是可表達成 $2^{s} \cdot d$ 的偶數, 其中 **s 是偶數**, **d 是奇數**
    對 在 [$\mathbb{Z}/n\mathbb{Z}$](https://en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n) 範圍內的偶數, 必須滿足***其中一種***形式：

    \begin{aligned}
        a^{d}\ &\equiv\ 1\ \bmod\ n \ &— 2式\\
        a^{2^{r}d}\ &\equiv\ -1\ mod\ p ,\ r\ \in\ \{\mathbb{N \mid 0\le r\le s-1}\}\ &— 3式\\
    \end{aligned}

    因 費馬小定理 ($a^{n-1}\ \equiv\ 1\ mod\ n$)
    又因 前置引理, 不斷對 $a^{n-1}$ 取平方根, 只會得到 $1$ 或 $-1$
    :::spoiler  算式
    \begin{aligned}
        a^{n-1}\ &\equiv\ 1\ \bmod\ n \\
        a^{2^{s}d}\ &\equiv\ 1\ \bmod\ n \\
        a^{2^{s}d} - 1\ &\equiv\ 0\ \bmod\ n \\
        (a^{2^{s-1}d} + 1)(a^{2^{s-1}d} - 1)\ &\equiv\ 0\ \bmod\ n \\
        (a^{2^{s-1}d} + 1)(a^{2^{s-2}d} + 1)(a^{2^{s-2}d} - 1)\ &\equiv\ 0\ mod\ n \\
        \vdots \\
        (a^{2^{s-1}d} + 1)(a^{2^{s-2}d} + 1)\dots(a^d + 1)(a^d - 1)\ &\equiv\ 0\ \bmod\ n \\
    \end{aligned}
    :::
    &emsp;&emsp;$\left\{
    \begin{array}{r}
       如果得到 -1, 則 3式 成立 \\
       如果都沒 -1, 則 2式 成立
    \end{array} \to n\ 是質數
    \right.$
- 測試：
    找到 $a$ 使得 2式、3式 ***皆不合***，那麼 **$n$ 不是質數**

### Agrawal-Kayal-Saxena’s (AKS) Primality Test

## CRT

- Chinese Remainder Theorem（中國餘數定理）
- Description of CRT
  - 假設 $n = p_1 \times p_2 \times p_3 \times\dots\times p_t$，這些數兩兩**互質**
  - 有 $x \bmod p_i = a_i$
  - 因為 $p_1, p_2 ... p_t$ 兩兩**互質**，可以確保 $gcd(p_i,n/p_i)= 1$
  - 找到 $u_i \backepsilon (n/p_i)\cdot u_i \bmod p_i = 1$(模法反元素)
  - $x \bmod n = (n/p_1) u_1 \cdot a_1 + (n/p_2) u_2 \cdot a_2 + \dots + (n/p_t) u_t \cdot a_t \bmod n$

:::danger
$\backepsilon$ 或 $\ni$ 符號通常表示 "**such that**"。

[notation - Backwards epsilon - Mathematics Stack Exchange](https://math.stackexchange.com/questions/15455/backwards-epsilon)
:::

:::info
$x \equiv 2\ mod\ 3,\ x \equiv 3\ mod\ 5,\ x \equiv 2\ mod\ 7$
find $x\ mod\ 105$ = ?

$$
\begin{aligned}
105 &= 3 \times 5 \times 7 \to \\
p_1 &= 3,\ a_1 = 2 \\
p_2 &= 5,\ a_2 = 3 \\
p_3 &= 7,\ a_3 = 2
\end{aligned}
$$

$(n/p_1) \times u_1 \bmod p_1=105/3 \times u_1 \bmod 3=35 \times u_1 \bmod 3=2 \times u_1 \bmod 3=1 \to u_1 = 2$

$(n/p_2) \times u_2 \bmod p_2=105/5 \times u_2 \bmod 5=21 \times u_2 \bmod 5=1 \times u_2 \bmod 5=1 \to u_2=1$

$(n/p_3) \times u_3 \bmod p_3 = 105/7 \times u_3 \bmod 7=15 \times u_3 \bmod 7=1 \times u_3 \bmod 7=1 \to u_3=1$

$$
\begin{aligned}
&x \bmod 105 \\
=& \Sigma(n/p_i) \times u_i \times a_i \bmod 105 \\
=& 35 \times 2 \times 2 + 21 \times 1 \times 3 + 15 \times 1 \times 2 \bmod 105 \\
=& 233 \bmod 105 \\
=& 23
\end{aligned}
$$
:::

## Discrete Logarithms

### The Powers of an Integer, Modulo n

- Recall from **Euler’s Theorem** that If gcd(a, n) = 1, then $a^{\phi(n)} \equiv 1 (mod\ n)$
- Given $\gcd(a, n) = 1$, there is at least one integer $m$ satisfying $a^m \equiv 1 (mod\ n)$
  - The least $m$ satisfying this Equation is the **order** of $a \bmod n$.
  - $m$ also denotes the **length of the period** generated by $a$
  - If (the least $m = \phi(n)$), $a$ is a ==**primitive root**== (generator) of $n$.
- Example: Powers of Integers, modulo 19  
  ![image.png](https://hackmd.io/_uploads/rklbjJrm6.png)
  - **primitive roots** of 19: 2, 3, 10, 13, 14, and 15.

### More on Primitive Root

- If $a$ is a primitive root of $n$, then its powers
  $$
  a, a^2, \dots, a^{\phi(n)} \pmod n
  $$
  are **distinct** and all are **relatively prime** to $n$.
- In particular, if $a$ is a primitive root of **prime** $p$, then its powers
  $$
  a, a^2, \dots, a^{p - 1} \pmod p
  $$
  are **distinct** and all are **relatively prime** to $p$.
- Suppose that $a$ is a primitive root of prime $p$
  - For each $x \in [1, (p−1)]$, there exists $y \backepsilon a^y \equiv x \pmod p$
- Testing Method for Primitive Root
  - Given $a \in [1, (p−1)]$, where $p$ is prime, test whether $a$ is a primitive root of $p$:
    - find all the **distinct prime factors** of $(p − 1)$:
      $$
      q_1, q_2, \dots, q_t
      $$
    - $a$ is a **primitive root** iff $a^{(p−1) / q_i} \bmod p \ne 1$ for all $i = 1, 2, \dots, t$
      - Note that $\gcd(a, p) = 1$.
- Example 1: If $p = 11$, test whether 2 and 3 are generators.
  1. Since $p − 1 = 10 = 2 \times 5$, we have $q_1 = 2$ and $q_2 = 5$.
  2. Test for 2:
     $$
     2^{(10)/2} \bmod 11 = 10 \ne 1 \\
     2^{(10)/5} \bmod 11 = 4 \ne 1
     $$
     $\Rightarrow$ **2 is a generator mod 11**
  3. Test for 3:  
     $3^{(10)/2} \bmod 11 = 1$ (**failure**)  
     $\Rightarrow$ 3 is ==NOT== a generator mod 11
- Exmaple 2: If $p = 19$, test whether $a$ is a generator.
  1. Since $p − 1 = 18 = 2 \times 3^2$, we have $q_1 = 2$ and $q_2 = 3$.
  2. Test for a:
     $$
     a^{(18)/2} \bmod 19 = a^9 \mod 19 \ne 1? \\
     a^{(18)/3} \bmod 19 = a^6 \mod 19 \ne 1?
     $$
  ![image.png](https://hackmd.io/_uploads/SylqMMSXT.png)

### Discrete Logarithm Problem (DLP)

Given a, b, and n, find $x$ (if exists) $\backepsilon a^x \pmod n = b$.

