# Logarit rời rạc
**Định nghĩa** Với $g$ là một căn nguyên thủy của $\mathbb{F_p}$ và $h$ là một phần tử khác không thuộc $\mathbb{F_p}$. Bài toán logarit rời rạc (DLP) là tìm một mũ $x$ sao cho
>$g^x \equiv h \pmod p$

Số $x$ được gọi là logarit rời rạc của $h$ với cơ số $g$ và được kí hiệu $\log_g(h)$

# Trao đổi khóa Diffie-Hellman
Ta có 2 người là $Alice$ và $Bob$ muốn trao đổi khóa.
1. Đầu tiên 2 người sẽ thống nhất chọn một số nguyên tố $p$ và một số $g \ne 0$ trong modulo $p$ . $g$ và $p$ được công khai.
2. Tiếp theo $Alice$ sẽ chọn một số tự nhiên $a$ , $Bob$ cũng sẽ chọn một số tự nhiên $b$ và $a$ , $b$ sẽ không được công khai ra ngoài.Lúc này $Alice$ và $Bob$ sẽ tính
>$A \equiv g^a \pmod p$ và $B \equiv g^b \pmod p$

3.Sau đó 2 người sẽ trao đổi $A$ và $B$ cho nhau
4.Cuối cùng thì $Bob$ và $Alice$ tiếp tục sử dụng các số nguyên bí mật của họ để tính
>$A^{'} \equiv B^a \pmod p$ và $B^{'} \equiv A^b \pmod p$

$A^{'}$ và $B^{'}$ là tương đương nhau bởi
> $A^{'} \equiv B^a \equiv (g^b)^a \equiv g^{ab} \equiv (g^a)^b \equiv A^b \equiv B{'} \pmod p$

Giá trị chung này là khóa trao đổi của $Alice$ và $Bob$.

**Định nghĩa** Với $p$ là một số nguyên tố và $g$ là một số nguyên. Bài toán Diffie–Hellman là bài toán tính toán giá trị $g^{ab} \pmod p$ từ những giá trị đã biết $g^a \pmod p$ và $g^b \pmod p$

# Hệ thống mã hóa công khai egamal
**Khởi tạo khóa**
Alice chọn một số nguyên tố $p$, một số nguyên $g$, số $a\in \{1,2,3,...,p-2\}$ .
Tính khóa công khai $A\equiv g^a\pmod p$
$a$ là khóa bí mật.
$(p,g,A)$ là khóa công khai
**Mã hóa bản rõ**
Bản rõ $m \in \mathbb{F_p}$
chọn ngẫu nhiên một số $k\in \{1,2,3,...,p-2\}$. Tính
>$c_1 \equiv g^k \pmod p$ và $c_2 \equiv mA^k \pmod p$

**Giải mã**
Ta có $c_2 \equiv mA^k \equiv m(g^a)^k \equiv m(g^k)^a \equiv mc_{1}^a \pmod p$. Vậy $m \equiv c_2c_{1}^{-a}$

# Tổng quan về lý thuyết nhóm
**Định nghĩa**. Một nhóm bao gồm một tập hợp $G$ và một quy tắc kí hiệu bằng $\star$ ( $\star$ biểu diễn cho các phép $+$, $*$, **hợp hàm**, **hân ma trận**, **quay**), kết hợp với 2 phần tử $a,b \in G$ sẽ thu được một phần tử $a\star b \in G$ thỏa mãn các tính chất :
* Phần tử đơn vị : Tồn tại một số $e\in G$ sao cho $e\star a = a\star e=a$ với mọi $a \in G$
**Ví dụ:**
- Với phép nhân, thì $e=1$: vì $1$ nhân với số nào kết quả cũng không thay đổi
- Với phép cộng, $e=0$: vì khi cộng với $0$ thì kết
**$\Rightarrow$ Tồn tại e sao cho áp dụng phép $*$ và $+$ thì kết quả không đổi**
* Phần tử nghịch đảo: Với mọi $a\in G$ có một phần tử $a^{-1} \in G$ thỏa $a\star a^{-1} = a^{-1}\star a=e$
* Tính giao hoán : $a\star b = b\star a$ với tất cả các $a,b\in G$

Nếu nhóm nào thỏa mãn tính giao hoán thì được gọi là nhóm giao hoán hay nhóm Abel.
Nếu $G$ có hữu hạn phần tử thì $G$ được gọi là nhóm hữu hạn.Bậc của $G$ là số phần tử của $G$ được kí hiệu $|G|$ hoặc $\#G$

* **Cấp của phần tử**: cho $G$ là một nhóm, $a \in G$, nếu tồn tại $1$ số $d$ nhỏ nhất thỏa mãn: $a^d = e$ thì $d$ được gọi là cấp của phần tử $a$, nếu không có $d$ thỏa mãn $\Rightarrow$ $a$ có cấp **vô hạn**
* **MĐ 2.12**: cho $G$ là nhóm hữu hạn $\Rightarrow$ cấp của mọi phần tử thuộc G đều hữu hạn, nếu $a \in G$ và cấp của $a$ là $d$, mà có 1 số nguyên $k$ thỏa mãn $a^k = e$ $\Rightarrow$ $d$ là ước của $k$ ($d|k$)
**Chứng minh**:
- Vì $G$ là trường hữu hạn $\Rightarrow$ mọi phép toán(*) trong trường đều được **mod** cho $G$ $\Rightarrow$ kết quả chỉ nằm trong tập $G-1$([định lí chuồng bồ câu](https://vi.wikipedia.org/wiki/Nguy%C3%AAn_l%C3%BD_ng%C4%83n_k%C3%A9o_Dirichlet)), ta có:
$$ a, a^1, a^2, ...$$
$\Rightarrow$ tồn tại $i, j$ sao cho $i<j$, $a^i = a^j$, nhân cả 2 vế với $a^{-i}$(*Luật nghịch đảo*)
>$$a^j \cdot a^{-i} = a^i \cdot a^{-1}$$$$a^{j-i} = e$$

$\Rightarrow$> mọi phần tử đều có cấp hữu hạn
- Giả sử $a^d = e$ với $d$ là cấp của $a$
$\Rightarrow k$ được biểu diễn: $$k = n*d + r$$
$\Rightarrow$ Mà có $a^d = a^k = e$:
$e = a^k = a^{(n*d)+r} = (a^{d})^n * a^r = e^n + a^r = a^r$ (vì $e$ là phần tử **đơn vị**)
$\Rightarrow$ vì $d$ là số mũ nguyên dương nhỏ nhât $\Rightarrow$ $r=0$ $\Rightarrow$ $k=n*d$
$\Rightarrow$ $d$ ước của $k$
* **MĐ 2.13 (Định lý Lagrange)**: Cho $G$ là một nhóm hữu hạn và $a \in G$
Cụ thể hơn: Gọi $n = |G|$ là cấp nhóm $G$ và $d$ là cấp của $a$
$\Rightarrow$ $a^d$ là lũy thừa dương **min** của $a$ mà bằng $e$
Ta có: $a^n = e$ và $d|n$
**Chứng minh**:
-- Ta sẽ chứng minh trường hợp đơn giản khi $G$ là nhóm giao hoán
-- Vì $G$ là nhóm hữu hạn, nên ta liệt kê các phần tử: $$G = \{ g_1, g_2, \ldots, g_n \}.$$
-- Ta nhân mỗi phần từ của $G$ với $a$ tạo ra tập mới $S_a$: $$S_a = \{ a \star g_1,a \star g_2, \ldots,a \star g_n \}.$$
-- Ta khẳng định rằng các phần tử của tập hợp $S_a$ khác nhau, ta sẽ dễ thấy: $$a \star g_i = a \star g_j$$ với $i$, $j$ là các số ngẫu nhiên
-- Nhân cả 2 vế với $a^{-1}$: $$g_i = g_j$$
$\Rightarrow$ $S_a = G$
-- Nếu ta nhân tất cả các phần tử trong $S_a$ với nhau thì ta sẽ thu được kết quả tương tự khi nhân các phần tử trong $G$ : $$(a \star g_1) \star (a\star g_2) \star \ldots \star (a\star g_n) = g_1 \star g_2 \star \ldots \star g_n$$
Dễ thấy:
$\Rightarrow$ $a^n \star g_1 \star g_2 \star \cdots \star g_n = g_1 \star g_2 \star \cdots \star g_n.$
-- Bây giờ, nhân cả hai vế với $\left( g_1 \star g_2 \star \cdots \star g_n \right)^{-1}$
Ta thu được $a^n = e$
Tương tự so với lại ```2.12``` việc d là ước của n

# Bài toán Logarit rời rạc khó đến mức nào?
**Nhắc lại định nghĩa Logarit**: Với $g$ là một căn nguyên thủy của $\mathbb{F_p}$ và $h$ là một phần tử khác không thuộc $\mathbb{F_p}$. Bài toán logarit rời rạc (DLP) là tìm một mũ $x$ sao cho
>$g^x \equiv h \pmod p$

Số $x$ được gọi là logarit rời rạc của $h$ với cơ số $g$ và được kí hiệu $\log_g(h)$

**Vậy Logarit rời rạc ở đây nghĩa là gì?**: Cho một nhóm $G$, bài toán logarit rời rạc (Discrete Logarithm Problem - DLP) yêu cầu tìm một số mũ $x$ sao cho: $$g^x = h$$
**Độ khó của bài toán**: Hiểu đơn giản chỉ là số lượng phép tính cần thực hiện rất lớn, vượt quá khả năng tính toán thực tế. Ta đo độ khó bằng số phép tính cần thiết của thuật toán tốt nhất.

- Dùng ký hiệu $\mathcal{O}$ lớn ```(Big-O notation)``` lớn để đơn giản hóa và dễ dàng đánh giá độ lớn của các số lượng khi số bit rất lớn

**Định nghĩa: Ký hiệu $\mathcal{O}$ lớn (Order Notation)**

* Ta có $f(x)$ và $g(x)$ hàm số dương. Ta nói rằng $f(x)$ là $O$ của $g(x)$ kí hiệu: $$f(x) = \mathcal{O}(g(x))$$
Nếu tồn tại các hằng số dương $c$ và $C$ sao cho:
$f(x) \leq c \cdot g(x) \text{ với mọi } x \geq C$

* Chú ý: $f(x) = \mathcal{O}(1)$ nếu $f(x)$ bị giới hạn khi $x \geq C$

* **MĐ 2.14**: Nếu giới hạn sau đây tồn tại (và hữu hạn):

$$
\lim_{x \to \infty} \frac{f(x)}{g(x)}
$$
thì ta có:
$$
f(x) = \mathcal{O}(g(x))
$$
**Chứng minh**:
* Gọi giới hạn đó là $L$ ta sẽ dựa vào [định lí giới hạn](https://vi.wikipedia.org/wiki/Gi%E1%BB%9Bi_h%E1%BA%A1n_c%E1%BB%A7a_m%E1%BB%99t_d%C3%A3y), với mỗi số $\varepsilon > 0$ bất kỳ sẽ tồn tại một hằng số $C$ sao cho:$$
\left| \frac{f(x)}{g(x)} - L \right| < \varepsilon \quad \text{với mọi } x > C.
$$
* Cụ thể, ta chọn $\varepsilon = 1$, khi đó:
$$
\frac{f(x)}{g(x)} < L + 1 \quad \text{với mọi } x > C_1.
$$
* Do đó, theo định nghĩa của ký hiệu O lớn, ta suy ra:
$$
f(x) = \mathcal{O}(g(x))
$$
với các hằng số $c = L + 1$ và $C = C_1$.

* **MĐ 2.16 (a)**: $x^2 + \sqrt{x} = O(x^2)$
**Bài làm**: Xét giới hạn hàm số sau:
$$
\lim_{x \to \infty} \frac{x^2 + \sqrt{x}}{x^2}
$$
-- Tính giới hạn: $$
\lim_{x \to \infty} \left( 1 + \frac{1}{x^{3/2}} \right) = 1
$$
--> Giới hạn này tồn tại và hữu hạn (bằng 1)
-- Kết luận: giới hạn tồn tại và hữu hạn, theo ```Mệnh đề 2.14```, ta suy ra ngay: $x^2 + \sqrt{x} = \mathcal{O}(x^2)$

**Tóm lại**: "Độ lớn đầu vào" của một bài toán thường được đo bằng số bit cần dùng để lưu số liệu đầu vào đó. Khi đánh giá thời gian tính toán, ta xét theo số bit này để biết bài toán trở nên phức tạp như thế nào khi số đầu vào lớn dần.

# Thuật toán va chạm cho logarit rời rạc (DLP)

* Chúng ta mô tả một thuật toán để giải bài toán logarit rời rạc do `Shanks` đưa ra

-- Có thuật toán cần chú ý ```thuật toán va chạm (collision algorithm)```

**Thuật toán của Shanks**
-- Hoạt động được trên mọi nhóm (any group) không chỉ riêng nhóm $F_p^{*}$
-- Phần này sẽ giới thiệu một thuật toán hiệu quả hơn thuật toán vét cạn, sử dụng kỹ thuật chia nhỏ và gặp nhau ở giữa, nhằm giải bài toán logarit rời rạc cho mọi nhóm, chứ không chỉ $F_p^{*}$

* Thuật toán: **Bước nhỏ – Bước lớn của Shanks**
- Ta có: Giả sử $G$ là một nhóm, và $g \in G$ là một phần tử có bậc $N \geq 2$. Thuật toán sau đây giải bài toán logarit rời rạc $g^x = h$ trong $O(\sqrt{N} \cdot \log N)$ bước, sử dụng bộ nhớ $O(\sqrt{N})$.

- **Chứng minh**:
1. Giả sử $g^x = h$, ta viết lại:
Ta phân tích số mũ $x$ dưới dạng $x = i + jn$, khi đó:
$$
g^x = g^{i+jn} = g^i \cdot g^{jn}
$$
Do đó:
$$
h = g^x = g^i \cdot (g^n)^j
$$
Từ đây, ta có thể suy ra:
$$
g^i = h \cdot (g^n)^{-j}
$$
2. Duyệt các giá trị có thể:
- Với mỗi $i$ từ $0$ đến $n - 1$: Tính và lưu trữ $g^i$ (danh sách bước nhỏ – *baby steps*)
- Với mỗi $j$ từ $0$ đến $n - 1$: Tính $h \cdot g^{-jn}$ và kiểm tra xem có khớp phần tử nào từ danh sách $g^i$ không
(danh sách bước lớn – *giant steps*)
Khi tìm được $g^i = h \cdot g^{-jn}$, thì:

$$
g^{i + jn} = h \Rightarrow x = i + jn
$$

from math import isqrt

def baby_step_giant_step(g, h, p):
    
    n = isqrt(p - 1) + 1  
    baby_steps = {}
    for i in range(n):
        baby = pow(g, i, p)
        baby_steps[baby] = i

 
    g_inv_n = pow(g, -n, p)

   
    current = h
    for j in range(n):
        if current in baby_steps:
            i = baby_steps[current]
            return i + j * n  # tìm được x = i + jn
        current = (current * g_inv_n) % p

    return None  # Không tìm thấy nghiệm

* Trước tiên chúng ta sẽ nhắc lại thời gian chạy của ```thuật toán vét cạn đơn giản nhất (trivial brute-force algorithm)``` để giải bài toán logarit rời rạc.

**MĐ 2.19** :Cận trên đơn giản cho bài toán logarit
rời rạc
* Giả sử $G$ là một nhóm và $g \in G$ là một phần tử cấp là $N$. (Nhớ rằng điều này nghĩa là $g^N = e$ và không có số mũ dương nào nhỏ hơn $N$ mà khi nâng $g$ lên lại thu được phần tử đơn vị $e$.) Khi đó, bài toán logarit rời rạc:
$$
g^x = h
$$
có thể được giải bằng $O(N)$ bước tính toán và dung lượng lưu trữ $O(1)$, trong đó mỗi bước tính toán bao gồm việc nhân với phần tử $g$.

**Chứng minh**:

- Mỗi giá trị tiếp theo được tính bằng cách nhân giá trị trước đó với $g$, do vậy tại mỗi bước, ta chỉ cần lưu giữ hai giá trị mà thôi.
- Nếu phương trình $g^x = h$ có nghiệm, thì chắc chắn giá trị $h$ sẽ xuất hiện trước khi ta tính đến $g^N$, vì theo định nghĩa, **cấp** của $g$ là $N$, nên chuỗi này phải lặp lại phần tử đơn vị $e$ tại đúng giá trị $g^N$.

**Nhận xét**:
- Khi ta làm việc trong nhóm $F_p^*$ (nhóm các số nguyên modulo $p$), mỗi lần tính toán biểu thức dạng $g^x \bmod p$ sẽ mất một số bước tính toán nhất định, phụ thuộc vào độ dài (số bit) của số $p$. Cụ thể hơn, số bước tính toán này tỷ lệ thuận với một hàm logarit của $p$:
$$
O\left((\log p)^k\right)
$$
với $k$ là một hằng số phụ thuộc vào loại máy tính và thuật toán nhân modulo được sử dụng.

- Tổng thời gian chạy của thuật toán giải bài toán logarit rời rạc, vì vậy, thực chất là:

$$
O\left(N(\log p)^k\right)
$$

- Tuy nhiên, trong thực tế, phần phụ thuộc vào $(\log p)^k$ này thường rất nhỏ so với $N$, nên để đơn giản và dễ hiểu hơn, ta bỏ qua nó. Do đó, ta nói gọn rằng: --> Thời gian chạy $O(N)$.

**Về thuật toán** : Với cách làm này, thay vì phải thử từng trường hợp một mất khoảng $O(N)$ bước, ta chỉ cần khoảng $O(\sqrt{N})$ bước mà thôi, nhanh hơn rất nhiều nếu $N$ lớn.

# Định lý số dư Trung Hoa

**Định lý**: mô tả các nghiệm của một hệ các phương trình đồng dư tuyến tính đồng thời

* Trường hợp đơn giản nhất của định lý này là hệ gồm hai phương trình đồng dư:$$
x \equiv a \pmod{m} \quad \text{và} \quad x \equiv b \pmod{n},
$$
với điều kiện hai modulo $m$ và $n$ nguyên tố cùng nhau, tức là:
$$
\gcd(m, n) = 1.
$$
Trong trường hợp này, **Định lý số dư Trung Hoa** phát biểu rằng tồn tại **duy nhất một nghiệm mod $mn$** (tích của hai mod này).

**Định lý 2.24 (tổng quát)**: Giả sử ta có các số nguyên $m_1, m_2,.., m_k$ đôi một nguyên tố cùng nhau --> $\forall i \ne j$ ta đều có:
$$
\gcd(m_i, m_j) = 1
$$
- Cho các số nguyên bất kỳ $a_1, a_2, \dots, a_k$. Khi đó, hệ các phương trình đồng dư đồng thời dưới đây: $$
\begin{aligned}
x &\equiv a_1 \pmod{m_1},\\
x &\equiv a_2 \pmod{m_2},\\
&\vdots\\
x &\equiv a_k \pmod{m_k},
\end{aligned}
$$
luôn luôn tồn tại **ít nhất một nghiệm** $x = c$.

**Ví dụ 2.25**: Chúng ta sẽ giải hệ ba phương trình đồng dư đồng thời sau đây:

$$
x \equiv 2 \pmod{3}, \quad
x \equiv 3 \pmod{7}, \quad
x \equiv 4 \pmod{16}.
$$

`Định lý số dư Trung Hoa` khẳng định rằng hệ này có duy nhất một nghiệm theo modulo là tích $3 \times 7 \times 16 = 336$.

-- Giải phương trình đầu tiên: $x = 2 + 3y$

-- Thế vào phương trình thứ 2: $2 + 3y \equiv 3 \pmod{7}$
-- Ta rút gọn phương trình này như sau:

- Trừ 2 cả hai vế, được:
$$
3y \equiv 1 \pmod{7}
$$

- Để giải đồng dư này, ta nhân cả hai vế với số nghịch đảo modulo $7$ của $3$.
Số nghịch đảo modulo $7$ của $3$ là $5$, vì $3 \times 5 = 15 \equiv 1 \pmod{7}$.
Ta được:
$$
y \equiv 5 \pmod{7}
$$
Thay giá trị này vào nghiệm tổng quát ban đầu $x = 2 + 3y$, ta thu được một nghiệm cụ thể:
$$
x = 2 + 3 \times 5 = 17
$$

Vậy $x = 17$ là nghiệm của hai phương trình đồng dư đầu tiên.

-- Bây giờ ta có nghiệm tổng quát cho hai phương trình đầu tiên:
$$
x = 17 + 21z
$$
(vì $21 = 3 \times 7$).
Tiếp tục thế vào phương trình đồng dư thứ ba:
$$
17 + 21z \equiv 4 \pmod{16}
$$
Rút gọn phương trình này:
- Trừ $17$ cho hai vế, ta có:
$$
21z \equiv 4 - 17 \pmod{16} \implies 21z \equiv -13 \pmod{16}.
$$

- Vì $21 \equiv 5 \pmod{16}$, nên viết lại phương trình đơn giản hơn:
$$
5z \equiv -13 \pmod{16}.
$$

- Vì $-13 \pmod{16}$ tương đương với $3 \pmod{16}$, ta có:
$$
5z \equiv 3 \pmod{16}.
$$

- Bây giờ ta cần nhân cả hai vế với số nghịch đảo modulo $16$ của $5$.
Số nghịch đảo modulo $16$ của $5$ là $13$, vì $5 \times 13 = 65 \equiv 1 \pmod{16}$.

Vậy ta có:
$$
z \equiv 3 \times 13 = 39 \equiv 7 \pmod{16}.
$$

--> Cuối cùng, thế giá trị $z = 7$ vào phương trình tổng quát trước đó, ta tìm được nghiệm cuối cùng của hệ phương trình:

$$
x = 17 + 21 \times 7 = 17 + 147 = 164
$$

Nghiệm nhỏ nhất của hệ là $x = 164$. Mọi nghiệm khác sẽ nhận được bằng cách cộng hoặc trừ các bội số của modulo tổng $336$.

## Giải phương trình đồng dư với modulo hợp số
**Cách dễ nhất để giải một phương trình đồng dư có modulo là hợp số**:

* Trước tiên, giải nhiều phương trình đồng dư tương ứng với modulo là số nguyên tố (hoặc lũy thừa của số nguyên tố).
* Sau đó, ghép các nghiệm lại bằng cách sử dụng ```Định lý số dư Trung Hoa (Chinese Remainder Theorem)```

**Mệnh đề 2.26**:
Giả sử $p$ là một **số nguyên tố** thỏa mãn điều kiện:
$$
p \equiv 3 \pmod{4}.
$$
Cho $a$ là một số nguyên sao cho phương trình đồng dư:
$$
x^2 \equiv a \pmod{p}
$$
có nghiệm, tức là $a$ có **căn bậc hai modulo $p$**.
Công thức:$$
b \equiv a^{\frac{p+1}{4}} \pmod{p}
$$

là một nghiệm của phương trình $x^2 \equiv a \pmod{p}$, tức là $b$ thoả mãn:

$$
b^2 \equiv a \pmod{p}.
$$

*(Lưu ý quan trọng: Công thức này **chỉ hợp lệ** khi $a$ thực sự có căn bậc hai modulo $p$. Trong mục 3.9, chúng ta sẽ trình bày một phương pháp hiệu quả để kiểm tra xem số nào có căn bậc hai modulo $p$.)*

**Chứng minh**: Giả sử $g$ là một **căn nguyên thủy modulo $p$**. Khi đó, mọi phần tử khác $0$ modulo $p$ đều có thể biểu diễn dưới dạng một lũy thừa của $g$. Do đó, ta có:

$$
a \equiv g^{2k} \pmod{p}
$$

-- Tính $b^{2}$: $$
\begin{aligned}
b^2 &\equiv \left(a^{\frac{p+1}{4}}\right)^2 \pmod{p} \\
&\equiv a^{\frac{p+1}{2}} \pmod{p} \\
&\equiv \left(g^{2k}\right)^{\frac{p+1}{2}} \pmod{p} \\
&\equiv g^{(p+1)k} \pmod{p} \\
&\equiv g^{2k + (p-1)k} \pmod{p} \\
&\equiv g^{2k} \cdot \left(g^{p-1}\right)^k \pmod{p}.
\end{aligned}
$$
$$
b^2 \equiv g^{2k} \cdot 1^k \pmod{p} \equiv g^{2k} \pmod{p}.
$$

Vì $a \equiv g^{2k} \pmod{p}$, ta kết luận:

$$
b^2 \equiv a \pmod{p}(đpcm)
$$

# Thuật toán Pohlig–Hellman
**Điều kiện tiên quyết**: Bài toán logarit rời rạc

**Thuật toán Pohlig–Hellman** được áp dụng trong trường hợp cấp của nhóm, trên đó DLP được định nghĩa, là một số trơn (tức là số có thể phân tích thành các số nguyên tố nhỏ). Trước tiên, hãy định nghĩa DLP của chúng ta trên Nhóm Cyclic $G = \mathbb{Z}_p^*$ có trật tự $n$.

Có nhiều biến thể khác nhau của thuật toán Pohlig–Hellman có thể được áp dụng trong các điều kiện khác nhau:

1. Khi **bậc của một nhóm** chỉ là lũy thừa của 2, tức là $n = 2^e$
2. Khi **cấp của một nhóm** là lũy thừa của một số nguyên tố, tức là $n = p^e$, trong đó $p$ là một số nguyên tố
3. **Thuật toán chung**, tức là:
$$
n = p_1^{e_1} p_2^{e_2} p_3^{e_3} \dots p_r^{e_r}
$$

**Chứng minh**:

-- Tôi sử dụng cùng ký hiệu như trong văn bản gốc: $p$ là số nguyên tố, $\alpha$ là một phần tử nguyên thủy trong $\mathbb{Z}_p$, và $\beta \in \mathbb{Z}_p^*$. Mục tiêu của chúng tôi là tìm $a = \log_{\alpha} \beta$, với điều kiện không mất tính tổng quát, $0 \leq a \leq p - 2$.
Phân tích thừa số nguyên tố của $p - 1$ là:
$$
p - 1 = p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k}
$$
trong đó các $p_i$ là các số nguyên tố khác nhau. Bước chính là tính $a \mod p_i^{c_i}$, với $1 \leq i \leq k$.
Giả sử $q = p_i$ và $c = c_i$ đối với một $i$, $1 \leq i \leq k$. Chúng tôi sẽ chỉ cách tính $x = a \mod q^c$.
-- **Đầu tiên**, biểu diễn $x$ dưới dạng:
$$
x = \sum_{i=0}^{c - 1} a_i q^i
$$
trong đó $0 \leq a_i \leq q - 1$ với $0 \leq i \leq c - 1$. Từ đó, ta có:
$$
a = a_0 + a_1 q + \cdots + a_{c - 1} q^{c - 1} + s q^c
$$
với một số nguyên $s$.
2.**Việc tính $a_0$ dựa trên công thức:**
$\beta^{(p-1)/q} \equiv \alpha^{a_0 (p-1)/q} \mod p$
Dưới đây là chứng minh đơn giản hơn so với trong sách:
$\beta^{(p-1)/q} = (\alpha^a)^{(p-1)/q} \mod p$
$= \left( \alpha^{a_0 + a_1 q + \cdots + a_{c-1} q^{c-1} + s q^c} \right)^{(p-1)/q} \mod p$
$= \alpha^{a_0 (p-1)/q} \cdot \alpha^{K(p-1)} \mod p \quad (\text{với } K \text{ là số nguyên})$
$= \alpha^{a_0 (p-1)/q} \mod p$
→ Từ đó, ta dễ dàng tính được $a_0$.
3. **Tính các $a_1, a_2, \dots$ qua công thức tổng quát:**

- **Đặt:**
$\beta_j = \beta \cdot \alpha^{-(a_0 + a_1 q + \cdots + a_{j-1} q^{j-1})} \mod p$

- **Áp dụng:**
$\beta_j^{(p - 1)/q^{j+1}} \equiv \alpha^{a_j (p - 1)/q} \mod p$

- **Truy hồi:**
$\beta_{j+1} = \beta_j \cdot \alpha^{-a_j q^j} \mod p$

4. **Ghép các phần dư lại để tìm $a \mod (p - 1)$**

from Crypto.Util.number import *

def pohlig_hellman_single(g, y, p, q, e):
    x = 0
    beta = y
    alpha = pow(g, (p - 1) // q, p)
    for j in range(e):
        y_j = pow(beta, (p - 1) // (q ** (j + 1)), p)
        a_j = log_brute_force(alpha, y_j, p)
        x += a_j * (q ** j)
        beta = (beta * inverse(pow(g, a_j * (q ** j), p), p)) % p
    return x

# Thuật toán Pohlig-Hellman
def pohlig_hellman(g, y, p, prime_factors, exponents):
    residues = []
    moduli = []
    for i in range(len(prime_factors)):
        q = prime_factors[i]
        e = exponents[i]
        res = pohlig_hellman_single(g, y, p, q, e)
        residues.append(res)
        moduli.append(q ** e)
    return chinese_remainder_theorem(residues, moduli)


if __name__ == "__main__":
    p = 0xfffffed83c17
    g = 5
    y = 230152795807443
    prime_factors = [2, 3, 7, 13, 47, 103, 107, 151]
    exponents     = [1, 2, 1, 4, 1, 1, 1, 1]

    x = pohlig_hellman(g, y, p, prime_factors, exponents)
    print("x =", x)
    # Kiểm tra lại:
    print("Check:", pow(g, x, p) == y)

# Vành, vành thương, vành đa thức và trường hữu hạn
## Tổng quan về lý thuyết vành

**Định nghĩa**: Một **vành** là một tập hợp $R$ được trang bị **hai phép toán**, thường được ký hiệu là "+" (cộng) và "$\star$" (nhân), thỏa mãn các tính chất sau:
- Tính chất của phép cộng ''+'':

- **[Định luật phần tử đơn vị – _Identity Law_]:** Tồn tại một phần tử đơn vị cộng $0 \in R$ sao cho:
$$
0 + a = a + 0 = a \quad \text{với mọi } a \in R.
$$
- **[Định luật phần tử nghịch đảo – _Inverse Law_]**: Với mọi phần tử $a \in R$, tồn tại một phần tử $b \in R$ sao cho:
$$
a + b = b + a = 0.
$$
- **[Định luật kết hợp – _Associative Law_]**:$$
a + (b + c) = (a + b) + c \quad \text{với mọi } a, b, c \in R.
$$
- **[Định luật giao hoán – _Commutative Law_]**:$$
a + b = b + a \quad \text{với mọi } a, b \in R.
$$
- Tính chất của phép nhân "$\star$":
- **[Định luật phần tử đơn vị – _Identity Law_]**: Tồn tại một phần tử đơn vị nhân $1 \in R$ sao cho:
$$
1 \star a = a \star 1 = a \quad \text{với mọi } a \in R.
$$
- **[Định luật kết hợp – _Associative Law_]**:
$$
a \star (b \star c) = (a \star b) \star c \quad \text{với mọi } a, b, c \in R.
$$
- **[Định luật giao hoán – _Commutative Law_]**: $$
a \star b = b \star a \quad \text{với mọi } a, b \in R.
$$
- Tính chất liên kết giữa $+$ và $\star$:
- **[Định luật phân phối – _Distributive Law_]:**
$$
a \star (b + c) = a \star b + a \star c \quad \text{với mọi } a, b, c \in R.
$$

## Tính chia hết và vành thương
**Định nghĩa**: Giả sử $a$ và $b$ là các phần tử trong một vành $R$ với $b \ne 0$.
Ta nói rằng **$b$ chia hết $a$**, hoặc rằng **$a$ chia hết cho $b$** nếu tồn tại một phần tử $c \in R$ sao cho:

$$
a = b \star c
$$

Giống như trước đây, ta viết:

- $b \mid a$ để chỉ rằng **$b$ chia hết $a$**.
- Nếu **$b$ không chia hết $a$**, ta viết:
$$
b \nmid a
$$

**Định nghĩa các phần tử**:
- **Phần tử khả nghịch (Unit):**
Cho $R$ là một vành.
Một phần tử $u \in R$ được gọi là **phần tử khả nghịch** (_unit_) nếu nó có **nghịch đảo nhân**, tức là tồn tại một phần tử $v \in R$ sao cho:

$$
u \star v = 1
$$

- **Phần tử không phân tích được (Irreducible):**

Một phần tử $a \in R$ được gọi là **không phân tích được** nếu:

- $a$ **không phải là phần tử khả nghịch** (không có nghịch đảo nhân), và
- với mọi phép phân tích $a = b \star c$, thì **hoặc** $b$ là phần tử khả nghịch **hoặc** $c$ là phần tử khả nghịch.

**Định nghĩa: Đồng dư trong vành**
- Giả sử $R$ là một vành, và chọn một phần tử khác $0 \in R$, gọi là $m$.
- Ta nói rằng hai phần tử $a$ và $b$ trong $R$ **đồng dư theo modulo $m$** nếu hiệu của chúng, $a - b$, chia hết cho $m$.
- **Ký hiệu:**

$$
a \equiv b \pmod{m}
$$

có nghĩa là **$a$ đồng dư với $b$ theo modulo $m$**.

**Định nghĩa: Vành thương $R/(m)$**
- Cho $R$ là một vành, và $m \in R$ với $m \ne 0$.

- Với mỗi phần tử $a \in R$, ta ký hiệu:

$$
\overline{a} = \{ a' \in R : a' \equiv a \pmod{m} \}
$$

- Nghĩa là **tập tất cả các phần tử trong $R$ đồng dư với $a$ theo modulo $m$**.
- Tập này được gọi là **lớp đồng dư của $a$**

- Toàn bộ các lớp đồng dư này được ký hiệu là:

$$
R/(m) = R \bmod m = \{ \overline{a} : a \in R \}
$$
- Quy tắc cộng và nhân các lớp đồng dư:$$
\overline{a} + \overline{b} = \overline{a + b} \quad \text{và} \quad \overline{a} \cdot \overline{b} = \overline{a \cdot b}
$$

--> Chúng ta gọi $R/(m)$ là **vành thương** của $R$ theo $m$.

## Vành đa thức và thuật toán Euclid

**Vàng đa thức**:
- Ta thấy rằng nếu $R$ là một vành bất kỳ, thì ta có thể tạo ra **vành đa thức** với các hệ số lấy từ $R$. Vành này được ký hiệu là:

$$
R[x] = \{a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n : n \geq 0 \text{ và } a_0, a_1, \ldots, a_n \in R \}
$$

- Bậc của một đa thức khác $0$ là số mũ lớn nhất của $x$ xuất hiện trong biểu thức. Vì thế, nếu:

$$
a(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n
$$
với $a_n \neq 0$, thì $a(x)$ có **bậc là** $n$, ký hiệu là $\deg(a)$, và gọi $a_n$ là **hệ số đầu** của $a(x)$.

- Một đa thức mà hệ số đầu bằng $1$ được gọi là **đa thức đơn vị** Ví dụ:
- $3 + x^2$ là đa thức đơn vị;
- Nhưng $1 + 3x^2$ thì không.

**Phép chia trong vành đa thức và tính chất Euclid**
- Đặc biệt quan trọng là các **vành đa thức** mà trong đó $R$ là một **trường**; ví dụ: $R$ có thể là $\mathbb{Q}$ (số hữu tỉ), $\mathbb{R}$ (số thực), $\mathbb{C}$ (số phức) hoặc một **trường hữu hạn** $\mathbb{F}_p$.
*(Trong mật mã học, trường hữu hạn là trường hợp quan trọng nhất.)*
- Ví dụ: Chia đa thức
- Hãy xét phép chia:
$$
\frac{x^5 + 2x^4 + 7}{x^3 - 5}
$$
Thực hiện phép chia tương tự như ở bậc phổ thông, ta thu được:
$$
x^5 + 2x^4 + 7 \div (x^3 - 5) = \underline{x^2 + 2x} \quad \text{(thương)}
$$
Vì:
$$
(x^2 + 2x)(x^3 - 5) = x^5 + 2x^4 - 5x^2 - 10x
$$
Phần dư là:
$$
(x^5 + 2x^4 + 7) - (x^5 + 2x^4 - 5x^2 - 10x) = 5x^2 + 10x + 7
$$
Vậy:
$$
x^5 + 2x^4 + 7 = (x^2 + 2x)(x^3 - 5) + (5x^2 + 10x + 7)
$$
> **Lưu ý:** Bậc của phần dư là 2 — nhỏ hơn bậc của mẫu số $x^3 - 5$ (bậc 3), đúng theo nguyên tắc chia có dư.

**Khái niệm vành Euclid**
- Nếu vành $\mathbb{F}$ là trường thì bất kỳ đa thức nào trong $\mathbb{F}[x]$ đều có thể chia được cho nhau theo cách có dư. Các vành như vậy được gọi là **vành Euclid** (*Euclidean rings*).

**Mệnh đề 2.44** *(Vành $\mathbb{F}[x]$ là vành Euclid)*

Giả sử $\mathbb{F}$ là một **trường** và $a, b$ là hai **đa thức** trong $\mathbb{F}[x]$ với $b \ne 0$.

Khi đó, **ta luôn có thể viết**:
$$
a = b \cdot k + r
$$
với $k$ và $r$ là các đa thức, và:

- hoặc $r = 0$,
- hoặc $\deg(r) < \deg(b)$.

--> Ta gọi đây là phép chia $a$ cho $b$ với thương là $k$ và dư là $r$.

**Chứng minh**
Ta bắt đầu với một cặp $k$ và $r$ bất kỳ sao cho $a = b \cdot k + r$.

Ví dụ: bạn có thể bắt đầu với $k = 0$ và $r = a$.

- Nếu bậc của $r$ nhỏ hơn bậc của $b$, ta hoàn tất.
- Nếu không, ta viết:
$$
b = b_0 + b_1x + \cdots + b_d x^d, \quad
r = r_0 + r_1x + \cdots + r_e x^e
$$
với $b_d \ne 0$, $r_e \ne 0$, và $e \ge d$ (tức $r$ có bậc cao hơn hoặc bằng $b$).

Ta trừ đi phần tử bậc cao của $r$ bằng cách viết:

$$
a = b \cdot \left( k + \frac{r_e}{b_d} x^{e-d} \right)
+ \left( r - \frac{r_e}{b_d} x^{e-d} \cdot b \right)
$$

Ký hiệu lại:

$$
a = b \cdot k' + r'
$$

Và ta thấy bậc của $r'$ giảm so với $r$.

Nếu $\deg(r') < \deg(b)$, ta xong. Nếu chưa, tiếp tục lặp lại.
Sau hữu hạn bước, **ta sẽ đạt đến phần dư có bậc nhỏ hơn bậc của $b$. Đây chính là quá trình chia đa thức có dư.**

**Ước chung và Ước chung lớn nhất trong $\mathbb{F}[x]$**:
- Cho hai đa thức $a, b \in \mathbb{F}[x]$, một phần tử $d \in \mathbb{F}[x]$ được gọi là **ước chung** nếu:
$$
d \mid a \quad \text{và} \quad d \mid b
$$
$d$ là **ước chung lớn nhất** của $a$ và $b$ nếu mọi ước chung khác của $a$ và $b$ đều chia hết cho $d$.
- Tính tồn tại: Với mọi cặp đa thức $a, b \in \mathbb{F}[x]$, **luôn tồn tại** một ước chung lớn nhất.
- Tính duy nhất: Ước chung lớn nhất là **duy nhất đến một hằng số nhân thuộc $\mathbb{F}$**.
Nghĩa là, nếu $d$ là một ước chung lớn nhất, thì mọi ước chung lớn nhất khác đều có dạng $c \cdot d$ với $c \in \mathbb{F}^*$.
- Ước chung lớn nhất của $a$ và $b$ được ký hiệu là:
$$
\gcd(a, b)
$$
- Để xác định duy nhất, người ta chọn **đa thức monic duy nhất** làm đại diện cho $\gcd(a, b)$, tức là đa thức có hệ số đầu bằng 1.

**Ví dụ 2.45**: Ước chung lớn nhất của $x^2 - 1$ và $x^3 + 1$ là $x + 1$.

Hãy quan sát rằng:

$$
x^2 - 1 = (x + 1)(x - 1) \quad \text{và} \quad x^3 + 1 = (x + 1)(x^2 - x + 1),
$$

⟹ Do đó, $x + 1$ là một **ước chung**.

**Mệnh đề 2.46 (Thuật toán Euclid mở rộng cho $F[x]$)**

Giả sử $\mathbb{F}$ là một trường, và $a, b$ là các đa thức trong $\mathbb{F}[x]$ với $b \ne 0$. Khi đó:

- ƯCLN $d$ của $a$ và $b$ luôn tồn tại,
- Và tồn tại các đa thức $u, v$ trong $\mathbb{F}[x]$ sao cho:
$$
a \cdot u + b \cdot v = d.
$$

**Ví dụ 2.47**:
Ta sử dụng **thuật toán Euclid** trong vành đa thức $\mathbb{F}_{13}[x]$ để tính:

$$
\gcd(x^5 - 1,\ x^3 + 2x - 3)
$$
- Chia $x^5 - 1$ cho $x^3 + 2x - 3$, ta được:
$$
x^5 - 1 = (x^3 + 2x - 3) \cdot (x^2 + 11) + (3x^2 + 4x + 6)
$$
- Chia $x^3 + 2x - 3$ cho phần dư trước là $3x^2 + 4x + 6$, ta được:
$$
x^3 + 2x - 3 = (3x^2 + 4x + 6) \cdot (9x + 1) + (9x + 4)
$$
→ Dư là $9x + 4$
- Chia $3x^2 + 4x + 6$ cho $9x + 4$, ta được dư bằng 0.
→ $\gcd = 9x + 4$
- Tuy nhiên, đây **không phải là đa thức monic** (tức là hệ số cao nhất khác 1). Ta cần nhân với **nghịch đảo của 9 modulo 13** để làm cho hệ số cao nhất thành 1.
→ Trong $\mathbb{F}_{13}$, ta có:
$$
9^{-1} \equiv 3 \pmod{13}
$$
→ Nhân $9x + 4$ với 3, ta được:
$$
3 \cdot (9x + 4) = 27x + 12 \equiv x - 1 \pmod{13}
$$
- Suy ra:
$$
\gcd(x^5 - 1,\ x^3 + 2x - 3) = x - 1 \quad \text{trong } \mathbb{F}_{13}[x]
$$

## Các thương của vành đa thức và các trường hữu hạn có bậc là lũy thừa của số nguyên tố

**Mệnh đề 2.50**: Lớp đồng dư theo một đa thức
- Cho $\mathbb{F}$ là một trường, và $m \in \mathbb{F}[x]$ là một đa thức khác 0.
Khi đó, **mỗi lớp đồng dư khác 0** $\overline{a} \in \mathbb{F}[x]/(m)$ đều có **một đại diện duy nhất** $r$ sao cho:

$$
\deg(r) < \deg(m) \quad \text{và} \quad a \equiv r \pmod{m}
$$
- Dễ hiểu hơn sẽ là:
- Khi bạn **lấy dư một đa thức** theo một đa thức khác $m$, bạn luôn tìm được **một đa thức duy nhất** có bậc nhỏ hơn $\deg(m)$ để đại diện cho lớp đồng dư đó.
- Đây là **cơ sở để coi các phần tử trong** $\mathbb{F}[x]/(m)$ như là các “số dư” sau phép chia.

- Chứng minh:
- Ta sử dụng **Mệnh đề 2.44** để tìm các đa thức $k$ và $r$ sao cho:
$$
a = m \cdot k + r
$$
với $r = 0$ hoặc $\deg r < \deg m$. Nếu $r = 0$, thì $a \equiv 0 \pmod{m}$, do đó $\bar{a} = \bar{0}$.
Ngược lại, việc chia dư theo $m$ cho ta $a \equiv r \pmod{m}$ với $\deg r < \deg m$, điều này chứng minh rằng $r$ tồn tại.
Giờ ta cần chứng minh rằng $r$ là duy nhất. Giả sử cũng có một đa thức $r'$ khác thỏa mãn các điều kiện tương tự. Khi đó:
$$
r - r' \equiv a - a \equiv 0 \pmod{m}
$$
Nghĩa là $m$ chia hết cho $r - r'$. Nhưng $\deg(r - r') < \deg m$, do đó ta phải có $r - r' = 0$, tức là:
$$
r = r'
$$

**Hệ quả 2.52**: Cho $\mathbb{F}_p$ là một trường hữu hạn và cho $m \in \mathbb{F}_p[x]$ là một đa thức khác không có bậc $d \geq 1$.
Khi đó, vành thương $\mathbb{F}_p[x]/(m)$ chứa chính xác $p^d$ phần tử.

**Mệnh đề 2.53**:
- Phần tử $\overline{a}$ có **nghịch đảo** trong $\mathbb{F}[x]/(m)$ nếu và chỉ nếu $a$ và $m$ **nguyên tố cùng nhau**, tức là không chia sẻ ước chung nào ngoài 1.
- Điều này tương tự như trong số học nguyên: một số nguyên $a$ chỉ có nghịch đảo modulo $m$ khi $\gcd(a, m) = 1$.

**Hệ quả 2.54**: Giả sử $\mathbb{F}$ là một trường và $m \in \mathbb{F}[x]$ là một đa thức **bất khả quy**.
--> Khi đó, vành thương $\mathbb{F}[x]/(m)$ là một **trường**, tức là mọi phần tử khác 0 trong $\mathbb{F}[x]/(m)$ đều có **nghịch đảo nhân**.

**Định lý 2.59**
Giả sử $\mathbb{F}_p$ là một **trường hữu hạn**.
- **a)** Với mọi $d \geq 1$, luôn tồn tại một **đa thức bất khả quy** $m \in \mathbb{F}_p[x]$ bậc $d$.

- **b)** Với mọi $d \geq 1$, luôn tồn tại một **trường hữu hạn** có đúng $p^d$ phần tử.

- **c)** Nếu $\mathbb{F}$ và $\mathbb{F}'$ là hai **trường hữu hạn** có cùng số phần tử, thì tồn tại một **phép ánh xạ tương ứng** giữa các phần tử của $\mathbb{F}$ và $\mathbb{F}'$ sao cho **bảng cộng và nhân** trong hai trường là giống nhau.
_(Thuật ngữ toán học nói rằng $\mathbb{F}$ và $\mathbb{F}'$ là **đẳng cấu** với nhau.)_

**Định nghĩa**
- Ta ký hiệu $\mathbb{F}_{p^d}$ cho một **trường có đúng $p^d$ phần tử**. `Định lý 2.59` đảm bảo rằng luôn tồn tại **ít nhất một** trường như vậy, và rằng **bất kỳ hai** trường có $p^d$ phần tử đều **về bản chất là giống nhau**, ngoại trừ việc đặt tên lại các phần tử.

- Những trường này còn được gọi là [trường Galois](https://en.wikipedia.org/wiki/Finite_field) (_Galois fields_) và thường được ký hiệu là $\mathrm{GF}(p^d)$, để vinh danh **nhà toán học Pháp thế kỷ 19 _Évariste Galois_**, người đã nghiên cứu về chúng.