<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$.
## 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
- 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
### Set of Residues
$Z_n = \{0, 1, ..., n-1\}$ is the $\text{Set of Residues}\pmod n$
- also called Residue Classes (mod n)
### Properties of Modular Arithmetic
#### 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$
:::
## 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$ 為結果。
#### 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$ 為結果。
### Montgomery's Method
Based on **Left-to-Right binary method** and **Extended Euclidean algorithm**.
（常在計算大數時使用）
## 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$
:::
### 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
試證：
  設 $x$ 是 $1\ \bmod\ p$ 的平方根之一
  有下列推導
\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}
  1式指出$(x+1)$ 或 $(x-1)$ **可以整除質數 p**
  則 $x = 1\ or\ -1$
  即 $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}
:::
  $\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
- **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?
$$
### Discrete Logarithm Problem (DLP)
Given a, b, and n, find $x$ (if exists) $\backepsilon a^x \pmod n = b$.
Sign in with Wallet
Connect another wallet