<h1 style="text-align:center;">Lý thuyết số cơ bản</h1>

Các nội dung trong bài này được mình lấy ở các nguồn sau:
- Giáo trình đại số hiện đại: [link](https://giaotrinh.net/giao-trinh-dai-so-hien-dai-chuong-1-co-ban-ve-dai-so-truu-tuong-5695/)
- Nhập môn mật mã học KMA buổi 6, 7, 8: [link](https://www.youtube.com/watch?v=BNhHail7X90&list=PLj4MXeFoK_O0xulM7XcCiYqUTqsKABxjY&index=7)

Hầu hết những gì mình ghi đều dựa trên ý hiểu của mình là chính, nên sẽ có thể có những chỗ sai và thiếu xót, bạn cần cẩn thận trước khi tiếp nhận kiến thức.

# I. Đại số trừu tượng
## Phép toán hai ngôi
- **++Định nghĩa++:** Cho $\text{S}$ là một tập hợp khác rỗng, một phép toán hai ngôi **(Binary operation)** trên tập hợp $\text{S}$ là một phép toán có thể thực hiện ánh xạ **tích Descartes** $\text{S} \times \text{S}\rightarrow\text{S}$.
> **Ký hiệu:** $x\circ y$, $x * y$ hoặc $x \cdot y$
- Hiểu đơn giản: với hai phần tử $x,y \in \text{S}$ thì kết quả của phép tính $x \circ y$ vẫn thuộc tập $\text{S}$.

> **Chú ý:** toán tử $\circ$ là ký hiệu chung và có thể đại diện cho toán tử cộng, nhân hoặc các toán tử toán học khác.

- **++Ví dụ++**: Trên tập số tự nhiên $\mathbb{N}$ thì phép **cộng** ($+$) sẽ là phép toán hai ngôi, phép **nhân** cũng tương tự. Nhưng phép **trừ** ($-$) và phép **chia** ($\div$) không phải là phép toán hai ngôi vì $1-2 =-1 \notin \mathbb{N}$ và $1 \div 2 = \frac{1}{2} \notin \mathbb{N}$.

- ++**Thuật ngữ**++:
- Phép toán hai ngôi $(\circ)$ được gọi là có tính chất **kết hợp** nếu $(x \circ y) \circ z = x \circ (y \circ z), \forall x,y,z \in \text{G}$.
- Có tính chất **giao hoán** nếu $x \circ y = y \circ x, \forall x,y \in \text{G}$.
- Có **phần tử đơn vị** $e$ nếu $e \circ x = x \circ e = x, \forall x \in \text{G}$.
- Có **phần tử nghịch đảo** $x'$ nếu $x \circ x' =x' \circ x = e$.

## Nhóm
### Nhóm
- **++Định nghĩa++ (Nhóm):** Nhóm $(\text{G}, \circ)$ là một tập hợp khác rỗng $G$ cùng với **một** phép toán hai ngôi $(\circ)$ và thỏa mãn **4** điều kiện sau:
- ++Tính đóng:++ Nếu $a,b \in G$ thì $a \circ b \in G$.
- ++Tính kết hợp:++ $(a \circ b) \circ c = a \circ (b \circ c)\hspace{3mm} \forall a,b,c \in G$.
- ++Phần tử đơn vị:++ Tồn tại duy nhất **một** phần tử được gọi là phần tử đơn vị $e$ sao cho $\forall a \in G$ thì $a \circ e = e \circ a = a$.
- ++Phần tử nghịch đảo:++ Với mọi phần tử $a \in G$ thì tồn tại một phần tử $a^{-1}$ sao cho: $a^{-1} \circ a = a \circ a^{-1} = e$.

- **++Ví dụ++:**
- Tập số thực $\mathbb{R}$ là một *nhóm* dưới phép cộng $(+)$ vì:
- Tổng của hai số thực bất kỳ luôn là số thực (tính đóng).
- $\forall a,b,c \in \mathbb{R}$ thì $(a+b)+c = a + (b+c)$ (tính kết hợp).
- $\forall a \in \mathbb{R}$, luôn tồn tại phần tử $0$ là phần tử đơn vị vì: $a + 0 = 0 +a = a$ (tồn tại phần tử đơn vị).
- $\forall a \in \mathbb{R}$ thì $-a + a = a + -a = 0$ (tồn tại phần tử nghịch đảo).
- Tập các số thực khác không $\mathbb{R}^*$ là một *nhóm* dưới phép nhân $(\times)$ vì:
- Tích của hai số thực luôn là số thực (tính đóng).
- $\forall a,b,c \in \mathbb{R}^*$ thì $(a \times b) \times c = a \times (b \times c)$ (tính kết hợp).
- $\forall a \in \mathbb{R}^*$ luôn tồn tại số $1$ là phần tử đơn vị vì $a \times 1 = 1\times a = a$ (tồn tại phần tử đơn vị).
- $\forall a \in \mathbb{R}^*$ thì $a \times a^{-1} = a \times \frac{1}{a} = 1$ (luôn tồn tại phần tử nghịch đảo).

- **++Định nghĩa++ (Nhóm Abel hoặc nhóm giao hoán):** Nhóm $(\text{G}, \circ)$ sẽ được gọi là nhóm **Abel** nếu phép toán hai ngôi có tính chất **giao hoán**, hay $\forall a,b \in G$ thì $a \circ b = b \circ a$.

- **++Ví dụ++**: Tập hợp $\mathbb{Z}$ (tập hợp các số nguyên) là một nhóm Abel với phép toán cộng (+) vì nó thỏa kết hợp (`(a+b)+c=a+(b+c)`), phần tử đơn vị (`0`), phần tử nghịch đảo (`a + (-a) = 0`) và quan trọng nhất là trính giao hoán (`a+b=b+a`).
- ++**Ví dụ**++: Nhóm Ma trận khả nghịch $2 \times 2$ trên trường số thực $\mathbb{R}$, ký hiệu là **$GL_2(\mathbb{R})$**, với phép toán là phép nhân ma trận không phải là một nhóm Abel vì ma trận không có tính chất giao hoán với phép nhân.

- **++Định nghĩa++ (Bậc của nhóm):** Là số lượng phần tử của nhóm hữu hạn $G$, ký hiệu là $\#G$

- **++Ví dụ++**: Xét nhóm $G=\mathbb{Z}_4$ (nhóm các số nguyên modulo 4) với phép toán là phép **cộng** modulo 4. Thì các phần tử của nhóm này là $G = \left\{0,1,2,3 \right\}$, vì có 4 phần tử nên bậc của $G$ là $4$. Ký hiệu $\#G = 4$.

- ++**Định lý:**++
- Phần tử đơn vị $e$ của một nhóm $(\text{G}, \circ)$ là duy nhất.
- Phần tử nghịch đảo của mỗi phần tử thuộc $(\text{G}, \circ)$ là duy nhất.
- $\forall a \in (\text{G}, \circ)$ thì $(a^{-1})^{-1} = a$.
- $\forall a,b \in (\text{G}, \circ), (a \circ b)^{-1} = a^{-1} \circ b^{-1}$.
- $\forall a,x,y \in (\text{G}, \circ)$, nếu $a \circ x = a \circ y$ thì $x = y$.

---

### Nhóm con
- **++Định nghĩa++ (Nhóm con):** Một tập con $H$ của $G$ được gọi là nhóm con của một nhóm $(\text{G}, \circ)$ nếu $H$ thỏa mãn các điều kiện để trở thành một nhóm và $H$ có chung toán tử $(\circ)$ với $G$. Ký hiệu $H \subseteq G$.

- ++**Ví dụ:**++
- Đối với phép cộng thì $\mathbb{Z} \subseteq \mathbb{Q}\subseteq \mathbb{R} \subseteq \mathbb{C}$.
- Tập $\left\{e \right\}$ là nhóm con của mọi nhóm.
- Tập hợp số nguyên chẵn $2 \mathbb{Z} = \left\{..., -2, 0, 2, 4, ... \right\}$ là một nhóm con của nhóm $\mathbb{Z}$ với phép cộng.

- ++**Định lý:**++
- Nếu $H$ là một nhóm con của $(\text{G}, \circ)$ thì phần tử đơn vị $e_H$ của $H$ cũng chính là phần tử đơn vị $e$ của nhóm $(\text{G}, \circ)$.
- Nếu $H$ là một nhóm con của $G$, và $h$ là một phần tử của $H$ thì nghịch đảo của $h$ trong $H$ cũng giống với nghịch đảo của $h$ trong $G$.
- Nếu $S$ là một tập con không rỗng của $G$, thì $S$ là một nhóm con của $G$ nếu và chỉ nếu $\forall a,b \in S, a \circ b^{-1} \in S$.
- Gọi $a$ là một phần tử của một nhóm $(\text{G}, \circ)$, khi đó tập hợp $\left\{ a^n: n \in \mathbb{Z}\right\}$ là một nhóm con của $G$.

>[!Important]
++**Định lý Lagrange:**++ Nếu $H$ là một nhóm con của một nhóm hữu hạn $G$, thì $\#H |\#G$, tức số lượng phần tử của $H$ là ước số của $\#G$.

---

### Bậc phần tử của nhóm
- **++Định nghĩa++ (Bậc phần tử của nhóm):** Cho $G$ là một nhóm và $a \in G$. Bậc của phần tử $a$ là số dương nhỏ nhất $i \in \mathbb{Z}$, thỏa mãn điều kiện $a^i = e$. Ký hiệu là $\text{ord}(a)$. Nếu $i$ không tồn tại thì $a$ là phần tử có bậc vô hạn.
> **Chú ý:** biểu thức $a^i$ để chỉ toán tử lặp $(a \circ a \dots \circ a)$ $i$ lần. Nếu phép toán của ta là phép cộng thì $a \circ a \dots \circ a = a \times i$, ngược lại khi phép toán là nhân thì $a \circ a \dots \circ a = a^i.$

- **++Định lý:++** Cho $G$ là một nhóm hữu hạn và $a \in G$ là một phần tử bất kỳ của nhóm. Khi đó $\text{ord}(a) | \#G$

- **++Ví dụ:++** Xét nhóm nhân modulo 7 (tức là các phần tử khả nghịch trong $\mathbb{Z}_7$), ký hiệu là $G = \mathbb{Z}_7^*$. Ta có các phần tử là $G = \{1, 2, 3, 4, 5, 6\}$ với phần tử đơn vị $e = 1$. Ta có bậc của nhóm là $\#G=6$.
- Ta có bậc của $3$ là $6$ vì $6$ là số nhỏ nhất thỏa: $3^6 \equiv 1\pmod 7$.
- Và $\text{ord}(3)$ cũng thỏa mãn tính chất $\text{ord}(3) | \#G$.

- **++Ví dụ:++** Bậc của các phần tử trong $G=\mathbb{Z}^*_{20}$:

- Có $G= \left\{ 1,3,7,9,11,13,17,19\right\}$ suy ra $\#G=8$.
- Cấp của $7$ sẽ là $4$ vì: $7^{4} \equiv 1 \pmod {20}$
- Lập bảng bậc các phần tử như sau:

|a|1|3|7|9|11|13|17|19|
|:--|:----:|:----:|:----:|:----:|:----:|:----:|:----:|---:|
|**ord(a)**|1|4|4|2|2|4|4|2
> Có thể thấy rằng vì $\# \mathbb{Z}_{20}^{*} = 8$ nên bậc của các phần tử trong nhóm sẽ là ước của $8$, ví dụ: $1,2,4$.

---

### Nhóm vòng (nhóm cyclic)

- **++Định nghĩa++ (Nhóm cyclic, phần tử sinh của nhóm):** Nhóm $G$ được gọi là nhóm cyclic, nếu như tồn tại một phần tử $a \in G$ sao cho $\forall b \in G$ tồn tại một số nguyên $i \geq 0$, thỏa mãn điều kiện $b = a^i$. Phần tử $a$ đó sẽ được gọi là phần tử sinh của nhóm $G$. Nếu nhóm $G$ được sinh bởi $a$, thì ta ký hiệu $G = ⟨a⟩$.

> Có thể hiểu là mọi phần tử $b$ trong nhóm $G$ đều được biểu diễn bằng phép tính $b = a^i$ với `^` là phép toán của nhóm và $a$ là phần tử sinh.

- ++**Ví dụ:**++
- $\mathbb{Z}^+_6 = \left\{ 0,1,2,3,4,5 \right\} = ⟨1⟩ = ⟨5⟩$ bởi vì mọi phần tử của $\mathbb{Z}^+_6$ đều có thể biểu diễn dưới dạng tổng của $1$ hoặc $5$ theo modulo $6$.
- Nhóm $\mathbb{Z}_{7}^{*} = \left\{1,2,3,4,5,6\right\} = ⟨3⟩$ vì:
$$
⟨3⟩ =
\left\{\begin{matrix}
3^{1} \equiv 3 \pmod 7 \\
3^{2} \equiv 2 \pmod 7 \\
3^{3} \equiv 6 \pmod 7 \\
3^{4} \equiv 4 \pmod 7 \\
3^{5} \equiv 5 \pmod 7 \\
3^{6} \equiv 1 \pmod 7
\end{matrix}\right.
$$
> Hoàn toàn có thể [chứng minh](https://youtu.be/aDydIaPr_L8) rằng một nhóm nhân $\mathbb{Z}^*_p$ với $p$ là một số nguyên tố là một nhóm cyclic.

- **++Định nghĩa++ (Hàm Euler):** Cho một số nguyên $n \geq 1$, thì giá trị $\phi(n)$ chính là **số lượng** các số nguyên $k$ thỏa mãn `0 < k < n` và $\text{gcd}(k,n) = 1$.

- ++**Ví dụ**++: Tính $\phi(10)$: hay tìm số lượng các số nguyên dương $k$ sao cho $0 < k < 10$ và $\text{gcd}(k, 10) = 1$. Đầu tiên các số nguyên $k$ thỏa mãn $0 < k < 10$ là: $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$, và trong tập trên, các giá trị nguyên tố với $10$ là $\{1,3,7,9 \}$ vậy suy ra: $\phi(10) = 4$.

> Để tính hàm Euler thì liệt kê từng phần tử như trên là rất chậm, nhưng ta hoàn toàn có thể dùng công thức để tính được nó rất nhanh, mình sẽ liệt kê công thức của nó ở phần sau.

- ++**Định lý:**++
- Nhóm con bất kỳ của một nhóm vòng cũng là một nhóm vòng.
- Nếu $\#⟨a⟩ = m$. Khi đó nhóm $⟨a⟩$ sẽ bao gồm $\phi(m)$ phần tử **sinh**. Chúng là các phần tử $a^r$, sao cho $\text{gcd}(r,m) = 1$
> Vì nếu $\#⟨a⟩ = m$, thì $\text{ord}(a^k) = \frac{m}{\text{GCD(k,m)}}$. Vậy nên nếu `gcd(k,m)=1` thì $a^k$ cũng là một phần tử sinh.
- Có một cách để kiểm tra liệu một phần tử có phải là phần tử sinh của nhóm $G$ hay không, đó là kiểm tra bậc của phần tử đó, nếu $\text{ord}(a) = \#G$ thì $a$ sẽ là phần tử sinh của nhóm. Số phần tử sinh sẽ là $\phi(\#G))$.

## Vành
- **++Định nghĩa++ (Vành):** Vành $(\text{R}, +, \times)$ là một tập hợp $R$ với **hai** phép toán hai ngôi là **cộng** và **nhân** thỏa mãn các điều kiện sau:
- $(\text{R}, +)$ là một nhóm giao hoán. Có phần tử đơn vị đối với phép cộng được ký hiệu là $0$.
- Phép nhân $(\times)$ có tính chất phân phối với phép cộng $(+)$, nghĩa là: $\forall a,b,c \in \mathbb{R}: a \times (b + c) = a \times b + a \times c$.
- Phép nhân có tính kết hợp, nghĩa là: $\forall a,b,c \in R: (a \times b) \times c = a \times (b \times c)$.
- Đối với phép nhân, vành $R$ có phần tử đơn vị, ký hiệu là $1$. Nghĩa là: $\exists 1, \forall a \in \mathbb{R}: 1\times a = a \times 1 = a$

> Tuy nhiên, có trường phái khác, định nghĩa một vành không có điều kiện phép nhân phải có phần tử đơn vị. Trong trường phái này, vành có phần tử đơn vị được gọi là **vành có đơn vị**.

- **++Ví dụ:++**
- Vành số nguyên $\mathbb{Z}$ có phần tử đơn vị là $1$: $a \times 1 = 1 \times a = a$
- Vành ma trận $2\times2$ có phần tử đơn vị là:
$$\begin{pmatrix}
1 &0 \\
0&1 \\
\end{pmatrix}$$
- Vành số chẵn $2 \mathbb{Z}$ *không phải* là một vành có đơn vị vì không tồn tại phần tử đơn vị cho phép nhân. Không thể tìm được số chẵn $x$ nào sao cho $2 \times x = 2$.

- **++Định nghĩa++ (Vành giao hoán):** là vành $R$ mà trong đó phép nhân có tính chất giao hoán.

- **++Định nghĩa++ (Vành con):** tập con $A$ của vành $R$ được gọi là vành con của $R$ nếu chính $A$ là một vành với hai phép toán cộng và nhân trên $R$.

- **++Ví dụ++:**
- Vành số nguyên $\mathbb{Z}$ là một ví dụ điển hình của vành giao hoán vì $\forall x,y \in \mathbb{Z}: a\times b = b \times a$, tương tự với vành số thực $\mathbb{R}$.
- Vành đa thức $\mathbb{R}[x]$: Tập hợp các đa thức với hệ số thực và phép cộng, phép nhân đa thức là một vành giao hoán. Ví dụ, với hai đa thức $p(x) = 2x+3$ và $q(x) = x^{2} + 1$, ta có $p(x) \times q(x) = q(x) \times p(x) = 2x^{3} + 3x^{2} +2x + 3$.
- Nhưng vành ma trận $2\times2$ không phải là một vành giao hoán, ví dụ:
$$A = \begin{pmatrix}
1 &2 \\
0 &1 \\
\end{pmatrix},
B = \begin{pmatrix}
0 &1 \\
1 &0 \\
\end{pmatrix}$$
thì $A \times B \neq B \times A$

## Trường
### Trường
- **++Định nghĩa++ (Trường):** Vành $R$ được gọi là trường $F$ nếu $R$ là một vành **giao hoán** có phần tử đơn vị khác $0$ và **với mọi** phần tử khác $0$ của $R$ đều có một phần tử nghịch đảo với phép nhân tức $\forall x \neq 0 \in R ,\exists \hspace{1mm} x^{-1}: x \times x^{-1} = e$.

> Để dễ hình dung thì một vành mà mọi phần tử trong nó đều có nghịch đảo thì vành đó sẽ là một **trường**.

- **++Định nghĩa++ (Trường con):** Giả sử $F$ là một trường. Tập con $E \subseteq F$ được gọi là trường con của $F$ nếu chính $E$ là một trường với cùng phép toán trong $F$.

- **++Ví dụ++:**
- Trường số hữu tỉ $\mathbb{Q}$, số thực $\mathbb{R}$ và số phức $\mathbb{C}$.
- Nhưng tập số nguyên $\mathbb{Z}$ không phải là một trường vì với mọi phần tử $x$ khác $0$ của tập không tồn tại phần tử nghịch đảo là $\frac{1}{x} \in \mathbb{Z}$. Nên nó chỉ là một vành giao hoán có đơn vị.

---

### Trường hữu hạn

- **++Định nghĩa++ (Trường nguyên tố):** Trường mà không bao gồm các trường con riêng biệt được gọi là trường nguyên tố.
> Các trường hữu hạn mà bậc của chúng là **số nguyên tố** là các trường có cấu trúc đơn giản nhất và được ứng dụng rộng rãi trong mật mã học. Điển hình là trong cơ chế trao đổi khóa [Diffie Hellman](https://hackmd.io/@at20n0118/SJ5cfXu0a#DIFFIE-HELLMAN) và hệ mã đường cong [Elliptic](https://hackmd.io/@at20n0118/HkJA5Ke6A).

- **++Định nghĩa++ (Trường hữu hạn):** Trường $F$ được gọi là trường hữu hạn nếu như số phần tử của nó là hữu hạn, ký hiệu là $F_q$ với $q$ là số phần tử của trường hữu hạn.
> ++**Chú ý:**++ Ở trên ta biết rằng nếu $p$ là số nguyên tố thì vành $Z_p$ là một trường, nhưng trên thực tế có nhiều trường hữu hạn không ở dạng trên. Ví dụ ta có $q = p^n$, với $p$ là số nguyên tố và $n \geq 1$ thì một trường $F_q$ như vậy được gọi là **trường Galois**.

- **++Định lý++**: Nhóm nhân $\mathbb{Z}^*_n$ của một trường hữu hạn $F_q$ là một **nhóm cyclic**. Phần tử sinh $\alpha$ của nhóm cyclic được gọi là phần tử nguyên thủy của trường hữu hạn $F_q$. Vì vậy tất cả các phần tử của trường hữu hạn có thể viết dưới dạng như sau: $$F_q = \left\{ 0, \alpha^1, \alpha^2, \dots, \alpha^{q-2}, \alpha^{q-1} = \alpha^{0} = 1 \right\}$$

# II. Số học Modulo
- **++Định nghĩa++ (Phép chia):** Cho hai số nguyên $a$ và $n$, $n>1$. Thực hiện phép chia $a$ cho $n$ ta sẽ được hai số nguyên $q$ và $r$ sao cho: $$a = n \times q + r \hspace{2mm} | \hspace{2mm} 0 <r<n$$
- $q$ được gọi là thương số, ký hiệu là $a$ $\text{div}$ $b$
- $r$ được gọi là số dư, ký hiệu là $a \mod n$

- **++Định nghĩa++ (Quan hệ đồng dư):** Ta ký hiệu $a \equiv b \pmod n$ khi và chỉ khi $a$ và $b$ có chung phần dư khi chia cho $n$.
- **++Ví dụ:++** ta có $100 \mod 11 = 1$ và $34 \mod 11 = 1$ vì vậy ta ta có thể viết chúng lại thành: $100 \equiv 34 \pmod {11}$

- **++Định nghĩa++ (Đại diện của a mod n):** Số $b$ được gọi là đại diện của $a$ theo $\mod n$ nếu: $a \equiv b \pmod n$ và $0 \leq b < n$.

- **++Ví dụ:++** $-12 \equiv -5 \equiv 2 \equiv 9 \pmod 7$ thì ta sẽ chọn số $2$ làm đại diện cho $-12,-5$ và $9$.

- Tập các **đại diện** của các số nguyên theo Modulo $n$ gồm $n$ phần tử, ký hiệu như sau:$$Z_n = \left\{0,1,2,3,\dots,n-1 \right\}$$

- **++Định nghĩa++ (Ước số):** Một số $b$ không âm được gọi là ước số của $a$, nếu tồn tại một số $m$ sao cho: $a = m \times b$. Trong đó cả $a,b,m$ đều là số nguyên. Ký hiệu: $b|a$.
- **++Ví dụ:++** $1,2,3,4,6,8,12,24$ là ước số của $24$.

---

- **Các phép tính trong không gian Modulo:** Ta có công thức của phép cộng $(+)$ và nhân $(\times)$ Modulo như sau:$$(a + b) \mod n = (a \mod n + b \mod n) \mod n$$

$$(a \times b) \mod n = (a \mod n \times b \mod n) \mod n$$

> Khi thực hiện tính toán, ta có thể thực hiện thay thế các số khó tính bằng một đồng dư khác của nó nhưng dễ tính hơn.

- Các tính chất rút gọn:
- Nếu $(a+b) \equiv (a+c) \pmod n$, thì $b \equiv c \pmod n$
- Nhưng $(a\times b) \equiv (a \times c) \pmod n$, thì $b\equiv c \pmod n$ khi và chỉ khi $\text{gcd}(a, n) = 1$.

- **++Ví dụ:++** Tính $(11 \times 19 + 10^{17}) \mod 7$
$$\begin{align}
(11 \times 19 + 10^{17}) &\equiv(4 \times 5 + 10^{17}) &\mod 7 \\
&\equiv(6 + 3^{17}) &\mod 7 \\
&\equiv(6 + 3\times (((3^{2})^{2})^2)^2) &\mod 7 \\
&\equiv(6 + 3 \times 4) &\mod 7 \\
&\equiv 4 &\mod 7\\
&= 4
\end{align}$$

- **++Định nghĩa++ (Ước số chung):** $d$ được gọi là ước số chung của hai số nguyên $a$ và $b$ nếu $d|a$ và $d|b$.

- **++Định nghĩa++ (Ước số chung lớn nhất):** Số nguyên $d$ được gọi là ước số chung lớn nhất của $a$ và $b$ nếu $d>0$ và $d$ là số nguyên lớn nhất trong số các ước của $a$ và $b$. Ký hiệu là $\text{gcd}(a,b)$.
- **++Ví dụ:++**
- $\text{gcd}(12,18) = 6$, $\text{gcd}(-18,27) = 9$, $\text{gcd}(7,5) = 1$.
- Ta luôn có $\text{gcd}(a,0) = a$ với mọi $a$.
- Quy ước rằng: $\text{gcd}(0,0) = 0$.

- **++Định lý:++**
- Nếu $b>0$ và $b|a$ thì $\text{gcd}(a,b) = b$.
- Nếu $a = b \times q + r$ hay $a \equiv r \pmod b$ thì $\text{gcd}(a,b) = \text{gcd}(r,b)$.

- **++Thuật toán Euclid tìm GCD:++**

    1. A = a, B = b
    2. while B > 0:
        r = A % B
        A = B, B = r
    3. return A

- **++Ví dụ:++ tính GCD(1970, 1066)**

        def gcd(a, b):
            while b > 0:
                a, b = b, a % b
            return a

        print(gcd(1970, 1066))
        #2

- **++Định nghĩa++ (Thuật toán Euclid mở rộng):** Nếu $\text{gcd}(a,b) = d$ thì phương trình bất định $a\cdot X + b\cdot Y = d$ có một cặp nghiệm nguyên $(X,Y)$, và ta có thể sử dụng thuật toán Euclid mở rộng để tìm chúng.

- **++Thuật toán Euclid mở rộng (EGCD):++**

    1. if b = 0 then d ← a, x ← 1, y ← 0 and return(d, x, y)
    2. x2 ← 1, x1 ← 0, y2 ← 0, y1 ← 1
    3. while b > 0 do:
        3.1 q ← a // b, r ← a - q * b
        3.2 x ← x2 - q * x1, y ← y2 - q * y1
        3.3 a ← b, b ← r
        3.4 x2 ← x1, x1 ← x
        3.5 y2 ← y1, y1 ← y
    4. d ← a, x ← x2, y ← y2
    5. return(d, x, y)

- **++Ví dụ:++ tính EGCD(2236725697, 3218145961)**

        a, b = 2236725697, 3218145961

        def egcd(a, b):
            if b == 0:
                d, x, y = a, 1, 0
                return (d, x, y)

            x2, x1 = 1, 0
            y2, y1 = 0, 1

            while b > 0:
                q = a // b
                r = a % b

                x = x2 - q * x1
                y = y2 - q * y1

                a, b = b, r

                x2 = x1
                x1 = x

                y2 = y1
                y1 = y

            d, x, y = a, x2, y2
            return (d, x, y)    

        print(egcd(a, b))
        #(1, 1331303798, -925303405)

- **++Định nghĩa++ (Phần tử nghịch đảo):** Phần tử nghịch đảo của một số nguyên $a$ trong modulo $n$ là một số nguyên $b > 0$ sao cho:
$$a \times b \equiv 1 \pmod n$$
> Điều kiện để tồn tại phần tử nghịch đảo đó là: $\text{gcd}(a, n) = 1$.

- ++Chứng minh:++ Để tìm được $b$, ta biến đổi phương trình trên như sau:

$$a \times b \equiv 1 \pmod n$$

$$\Leftrightarrow a \times b = 1 + q \times n$$

$$\Leftrightarrow a \times b - q \times n = 1 \hspace{5mm} (*)$$
- Ta hoàn toàn có thể dùng **EGCD** để tìm được hai nghiệm $(b, q)$ của phương trình $(*)$.
- **++Ví dụ:++ tính nghịch đảo của 127 trong modulo 319.** Sau khi áp dụng EGCD thì ta sẽ tìm được $b = -108$, nhưng đây là không gian Modulo nên ta phải chọn một phần tử đại diện là một số $0 \leq b < n$, chọn $221$ vì $221 \equiv -108 \pmod {319}$.

- **++Định nghĩa++ (Số nguyên tố):** Số nguyên tố là số nguyên dương chỉ có ước số là $1$ và chính nó. Không thể viết chúng dưới dạng tích của các số khác.
> Đây sẽ là con số gắng bó với toàn bộ sự nghiệp chơi cryptography của bạn 🐧

- Một trong những bài toán cơ bản của số học là **phân tích thừa số nguyên tố** của một số $a$. Đây là một bài toán rất khó, khó hơn nhiều so với bài toán nhân các số để nhận được tính.
- Người ta chứng minh được rằng: mọi số nguyên dương đều có thể được phân tích duy nhất thành lũy thừa của các số nguyên tố.
- **++Ví dụ:++** $51 = 3 \times 17$, $3600 = 2^4 \times 3^2 \times 5^2$

- **++Định lý Fermat++ (Định lý fermat nhỏ):** Định lý khẳng định rằng nếu $p$ là một số **nguyên tố**, thì với mọi số nguyên $a < p$ bất kỳ, $a^p - a$ sẽ chia hết cho $p$, hay:
$$a^p \equiv a \pmod p$$
- Vì $\text{gcd}(a, p) = 1$ nên ta có thể biến đổi công thức trên thành:
$$a^{p-1} \equiv 1 \pmod p$$
> Nhờ tính chất trên mà để kiểm tra xem một số $p$ có phải số nguyên tố hay không, họ sẽ chọn một số $a$ bất kỳ nhỏ hơn $p$ để tính $a^{p-1} \pmod p$, nếu kết quả là $1$ thì rất có khả năng $p$ là số nguyên tố, có thể tìm hiểu thêm ở link [**này**](https://youtu.be/tBzaMfV94uA).

- **++Ví dụ:++** cho $a = 5, p = 7$, ta có được: $a^{p-1} \mod p= 5^{6} \mod 7 = 1$

- **++Định nghĩa++ (Hàm φ(n)):**
- Tập $Z_n = \left\{0,1,2,\dots,n-1 \right\}$ được gọi là thặng dư đầy đủ theo mod $n$.
- Xét tập $Z^*_n = \left\{a \in Z_n: \text{gcd}(a, n) = 1\right\}$. Tập này được gọi là tập các thặng dư thu gọn theo mod $n$. Nếu $p$ là số nguyên tố thì $Z^*_p = \left\{1,2,3,\dots,p-1 \right\}$.
- Ký hiệu $\phi(n)$ (hàm Euler) là số phần tử lớn hơn $0$, nhỏ hơn $n$ và nguyên tố cùng nhau với $n$.

- **++Tính chất++:**
- Nếu $p$ là số nguyên tố thì $\phi(p) = p-1$. Vì $p$ là số nguyên tố nên các số lớn hơn 0 bé hơn $p$ sẽ nguyên tố với $p$ hết, ta có tổng cộng $p-1$ giá trị.
- Nếu $\text{gcd}(m,n) = 1$ thì $\phi(m \times n) = \phi(m) \times \phi(n)$.
- Nếu $n = p^{e_1}_1 \times p^{e_2}_2 \times \dots \times p^{e_k}_k$ là phân tích thừa số nguyên tố của $n$ thì:
$$\phi(n) = n \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \dots \times (1 - \frac{1}{p_k}) $$

- **++Ví dụ:++ tính** $\phi(37), \phi(25), \phi(18), \phi(21)$.
- $\phi(37) = 37-1 = 36$.
- $\phi(25) = 5^2 = 5^2 \times \frac{5-1}{5} = 20$.
- $\phi(18) = 2 \times 9 = \phi(2) \times \phi(9) = 1 \times 3^2 \times \frac{3-1}{3} = 6$.
- $\phi(21) = 3 \times 7 = \phi(3) \times \phi(7) = 2 \times 6 = 12$.

- **++Định lý Euler++:** Đây là dạng tổng quát hóa của định lý fermat nhỏ. Với mọi cặp số nguyên dương $(a,n)$ nguyên tố cùng nhau, ta có:
$$a^{\phi(n)} \equiv 1 \pmod n$$

- **++Ví dụ:++** Với $a = 3, n = 10, \phi(n) = 4$ vì vậy $3^4 = 81 \equiv 1 \pmod {10}$.

- **++Định nghĩa++ (Nhóm nhân Zn):**
- Nhóm nhân của $Z_n$ là $Z^*_N = \left\{ a \in Z_n |\hspace{2mm} \text{gcd}(a,n) = 1 \right\}$.
- Cấp của $Z^*_n$ là số các phần tử trong $Z^*_n$, ký hiệu là $|Z^*_N|$.
- Theo định nghĩa hàm Euler ta có $|Z^*_n| = \phi(n)$.

- **++Định nghĩa++ (Cấp của phần tử):**
- Cho $a\in Z^*_n$. Cấp của một phần tử $a$ được ký hiệu là $\text{ord}(a)$ là số nguyên dương nhỏ nhất $t$ sao cho:
$$a^t \equiv 1 \pmod n$$
- Cho $a \in Z^*_n$, $\text{ord}(a) = t$ và $a^s \equiv 1 \pmod n$, khi đó $t$ sẽ là ước của $s$. Đặc biệt: $t|\phi(n)$.

- **++Ví dụ:++** Tính cấp của các phần tử trong $Z^*_{10}$
- Ta có $\mathbb{Z}_{10}^{*} = \left\{ 1,3,7,9\right\}$
- Ví dụ cấp của $3$ sẽ là $4$ vì: $3^{4} \equiv 1 \pmod {10}$
- Làm theo cách trên ta lập được bảng như sau:

|a|1|3|7|9|
|:--|:----:|:----:|:----:|:----:
|**ord(a)**|1|4|4|2|

- **++Tính chất++ (phần tử sinh):**
- $Z^*_n$ có phần tử sinh nếu và chỉ nếu $n=2,4,p^k$ hoặc $n = 2\cdot p^k$. Trong đó $p$ là số nguyên tố lẻ và $k \geq 1$.
- Nếu $\alpha$ là một phần tử sinh của $Z^*_n$ thì: $Z^*_n = \left\{\alpha^i \mod n| \hspace{2mm}1 \leq i \leq\phi(n) - 1 \right\}$.
- Giả sử $\alpha$ là một phần tử sinh của $Z^*_n$. Khi đó $b = \alpha^i \mod n$ cũng là phần tử sinh của $Z^*_n$ nếu và chỉ nếu $\text{gcd}(i, \phi(n)) = 1$. Nếu $Z^*_n$ là nhóm cyclic thì số phần tử sinh là $\phi(\phi(n))$.
- Nếu $\alpha$ là một phần tử sinh của $Z^*_n$ thì $\alpha^{\frac{\phi(n)}{p_i}} \not\equiv 1 \pmod n$ với mỗi $p_i$ là thừa số nguyên tố của $\phi(n)$.

- **++Ví dụ:++** Cho $Z^*_{25}$ là nhóm cyclic và có phần tử sinh là $\alpha = 2$. Tìm các phần tử sinh còn lại của $Z^*_{25}$.
- Ta có $\phi(\phi(25)) = 8$ vậy ta sẽ có tổng cộng $8$ phần tử sinh là $\left\{2^1, 2^3, 2^7, 2^9, 2^{11}, 2^{13}, 2^{17}, 2^{19} \right\} \mod 25 = \left\{2,3,8,12,13,17,22,23 \right\}$

---

- **++Định nghĩa++ (Định lý thặng dư Trung Hoa):** Cho $n_1, n_2, \dots, n_k$ nguyên tố cùng nhau từng đôi một thì hệ sau sẽ có nghiệm duy nhất theo Modulo $n = n_1 \times n_2 \times \dots \times n_k$ :
$$
\left\{\begin{matrix}
x \equiv a_1 \pmod {n_1} \\
x \equiv a_2 \pmod {n_2} \\
\cdots \\
x \equiv a_k \pmod {n_k} \\
\end{matrix}\right.
$$
- Áp dụng định lý thặng dư trung hoa, ta tìm được nghiệm $x$ như sau:
$$x = \sum_{i=1}^{k} (a_i \times N_i \times M_i) \mod N$$
- Với $N = n_1 \times n_2 \times \dots \times n_k$
- $N_i = N \div n_i$
- $M_i \equiv N_i^{-1} \pmod {n_i}$

---

>[!Important]
Để giải thích tại sao có công thức CRT trên, ta sẽ lấy một ví dụ nhỏ vô cùng chi tiết để nắm được bản chất công thức:

Giả sử ta muốn tìm một số $A$ thỏa mãn:
$$
\left\{\begin{matrix}
A \equiv a_1 \pmod {n_1} \\
A \equiv a_2 \pmod {n_2} \\
A \equiv a_3 \pmod {n_3}
\end{matrix}\right.
$$

Đầu tiên ta xây một công thức $X$ chứa cả $a_1,a_2$ và $a_3$ là: $$X \equiv a_1 + a_2 + a_3 \pmod N$$

> Trong đó $N = n_1.n_2.n_3$.

Ta muốn rằng $X$ của ta khi mod cho $n_1$ phải ra $a_1$, vì thế chỉ cần nhân $a_2$ và $a_3$ cho $n_1$ thì khi mod $X$ cho $n_1$ thì $a_2$ và $a_3$ sẽ biến thành $0$ và chỉ còn $a_1$, khi này công thức của ta là:

$$X = a_1 + a_2.n_1 + a_3.n_1 \pmod N$$

Làm tương tự với $a_2$ và $a_3$, ta được công thức mới:
$$X = a_1.n_2.n_3 + a_2.n_1.n_3 + a_3.n_1.n_2 \pmod N$$

Với công thức $X$ bây giờ, khi đem nó mod $n_1, n_2$ và $n_3$ ta được
$$
\left\{\begin{matrix}
X \equiv a_1.(n_2.n_3) \pmod {n_1} \\
X \equiv a_2.(n_1.n_3) \pmod {n_2} \\
X \equiv a_3.(n_1.n_2) \pmod {n_3}
\end{matrix}\right.
$$

Giờ ta cần cách để triệt tiêu $(n_2.n_3)$, $(n_1.n_3)$ và $(n_1.n_2)$ đi, khi này ta chỉ đơn giản nhân lần lượt $(n_2.n_3)$, $(n_1.n_3)$ và $(n_1.n_2)$ với nghịch đảo modulo của nó thôi, tức ta có:

$$
\left\{\begin{matrix}
X \equiv a_1.(n_2.n_3). (n_2.n_3)^{-1} \equiv a_1 \pmod {n_1}\\
X \equiv a_2.(n_1.n_3). (n_1.n_3)^{-1} \equiv a_2\pmod {n_2}\\
X \equiv a_3.(n_1.n_2). (n_1.n_2)^{-1} \equiv a_3 \pmod {n_3}
\end{matrix}\right.
$$

Vậy ta được công thức tổng quát là:
$$A \equiv X \equiv a_1.(n_2.n_3).[(n_2.n_3)^{-1} \mod n_1] + a_2.(n_1.n_3).[(n_1.n_3)^{-1}\mod n_2] + a_3.(n_1.n_2).[(n_1.n_2)^{-1}\mod n_3] \pmod N$$

Hay:
$$A = \sum_{i=1}^{3} (a_i \times N_i \times M_i) \mod N$$

Với $N_i = N/n_i$ và $M_i = N_i^{-1} \mod n_i$

---

- **Trường hợp đặc biệt** khi ta chỉ có một hệ hai phương trình:

$$
\left\{\begin{matrix}
x \equiv a_1 \pmod {n_1} \\
x \equiv a_2 \pmod {n_2} \\
\end{matrix}\right.
$$
- Vì $\text{gcd}(n_1, n_2) = 1$ nên tồn tại hai số $m_1, m_2$ sao cho: $m_1 \cdot n_1 + m_2 \cdot n_2 = 1$

- Vì vậy nghiệm $x$ của ta có công thức như sau:
$$x = a_1 \times m_2 \times n_2 + a_2 \times m_1 \times n_1$$

$$\Leftrightarrow x = a_1 \times(1 - m_1\times n_1) + a_2 \times m_1 \times n_1$$

$$\Leftrightarrow x = a_1 + (a_2 - a_1) \times m_1 \times n_1$$

---

- **++Định lý++:** Nếu $\gcd(n_1, n_2) = 1$ thì cặp phương trình đồng dư
$$
\left\{\begin{matrix}
x \equiv a \pmod {n_1} \\
x \equiv a \pmod {n_2} \\
\end{matrix}\right.
$$
có một nghiệm duy nhất: $x \equiv a \pmod {n_1 \times n_2}$

---

- **++Định nghĩa++ (Thặng dư bậc hai và bất thặng dư bậc hai):**
- Cho $a \in Z^*_n, a$ được gọi là thặng dư bậc hai theo modulo $n$ (hay bình phương modulo $n$) nếu $\exists x \in Z^*_n: x^2 \equiv a \pmod n$. Nếu không tồn tại $x$ như vậy thì $a$ được gọi là bất thặng dư bậc hai modulo $n$.
- Tấp tất cả các thặng dư bậc hai modulo $n$ được ký hiệu: $Q_n$.
- Tập tất cả các bất thặng dư bậc hai modulo $n$ được ký hiệu: $\overline{Q}_n$.

- **++Định lý++:** Cho $p$ là một số nguyên tố **lẻ** và $\alpha$ là phần tử sinh của $Z^*_p$. Khi đó $a \in Z^*_p$ là một thặng dư bậc hai modulo $p$ nếu và chỉ nếu $a = \alpha^i \pmod p$ với $i$ là số nguyên **chẵn**.

- **++Hệ quả++:** $|Q_n| = \frac{p-1}{2};|\overline{Q}_n| = \frac{p-1}{2}$

- **++Định lý++:** Cho $n = p\times q$, với $p,q$ là hai số nguyên tố, $p \neq q$. Khi đó $a \in Z^*_p$ là thặng dư bậc hai theo modulo $n$ nếu và chỉ nếu $a\in Q_p$ và $q \in Q_q$.

- **++Hệ quả++:** $|Q_n| = \frac{(p-1)(q-1)}{4};|\overline{Q}_n| = \frac{3\times(p-1)(q-1)}{4}$

- **++Định nghĩa++ (căn bậc hai của một số modulo n):** Cho $a \in Q_n$. Nếu $x \in Z^*_n$ thỏa mãn $x^2 \equiv a \pmod n$ thì $x$ được gọi là căn bậc hai của $a \mod n$.

- **++Định lý về số căn bậc hai++:** Cho $n = p^{e_1}_1 \times p^{e_2}_2 \times \dots \times p^{e_k}_k$, trong đó $p_i$ là các số nguyên tố lẻ phân biệt và $e_i \geq 1$. Nếu $a \in Q_n$ thì có đúng $2^k$ căn bậc hai khác nhau theo modulo $n$.

---

- **++Định nghĩa++ (Ký hiệu Legendre):** $p$ là số nguyên tố lẻ, $a$ là số nguyên. Ký hiệu Legendre $\left(\frac{a}{p}\right)$ được xác định như sau:
$$ \left(\frac{a}{p}\right) =
\left\{\begin{matrix}
0 \hspace{5mm} p|a \\
1 \hspace{5mm} a \in Q_p\\
-1 \hspace{5mm} a \in \overline{Q_p}\\
\end{matrix}\right.
$$

- **++Định nghĩa++ (Ký hiệu Jacobi):** Cho $n \geq 3$ là số nguyên lẻ có phân tích $n = p^{e_1}_1 \times p^{e_2}_2 \times \dots \times p^{e_k}_k$, khi đó ký hiệu Jacobi $\left(\frac{a}{n}\right)$ được định nghĩa là:$$ \left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{e_1} \times \left(\frac{a}{p_2}\right)^{e_2} \times \dots \times \left(\frac{a}{p_k}\right)^{e_k}$$

> Ta thấy rằng nếu $n$ là số nguyên tố thì ký hiệu Jacobi chính là ký hiệu Legendre.

- **++Tính chất++:**
- Nếu $n$ là số nguyên lẻ và $m_1 \equiv m_2 \pmod n$ thì:
$$ \left(\frac{m_1}{n}\right) = \left(\frac{m_2}{n}\right)$$
- Nếu $n$ là số nguyên lẻ thì:
$$
\left(\frac{2}{n}\right) =
\left\{\begin{matrix}
1 \hspace{5mm}|\hspace{2mm} n \equiv \pm 1 \pmod 8 \\
-1 \hspace{1mm}|\hspace{2mm} n \equiv \pm 3 \pmod 8\\
\end{matrix}\right.
$$
- Nếu $n$ là số nguyên lẻ thì:
$$
\left(\frac{m_1 \cdot m_2}{n}\right) = \left(\frac{m_1 }{n} \right)\cdot \left(\frac{m_2}{n}\right)
$$
- Nếu $m = 2^k \times t$ ( $t$ là số lẻ) thì:
$$
\left(\frac{m}{n}\right) = \left(\frac{2}{n}\right)^k \cdot \left(\frac{t}{n}\right)
$$
- Giả sử $m$ và $n$ là hai số nguyên lẻ và $m,n \equiv 3 \pmod 4$ thì:
$$
\left(\frac{m}{n}\right) = - \left(\frac{n}{m}\right)
$$

---

# III. Một số kiến thức toán học
- **++Định nghĩa++ (Số nguyên Blum):** Là một hợp số có dạng $n = p\times q$. Trong đó $p,q$ là hai số nguyên tố khác nhau thỏa mãn: $p \equiv 3 \pmod 4, q \equiv 3 \pmod 4$.

- **++Định lý++:** Cho $n$ là một số nguyên Blum và cho $a \in Q_n$. Khi đó $a$ có đúng $4$ căn bậc hai Modulo và chỉ có một số nằm trong tập $Q_n$.

- **++Định nghĩa++ (Căn bậc hai chính):** Cho $n$ là một số nguyên Blum và cho $a \in Q_n$ Căn bậc hai duy nhất của $a$ nằm trong $Q_n$ được gọi là căn bậc hai chính của $a \mod n$

- **++Ví dụ:++** $n = 7 \times 3; Q_{21} = \left\{ 1,4,16\right\}$
- $4$ căn bậc hai của $4 \mod 21$ là: $2,5,16,19$. Trong đó $16 \in Q_{21}$. Do vậy $16$ là căn bậc hai chính của $4 \mod 21$.
- $4$ căn bậc hai của $1 \mod 21$ là: $1,8,13,20$. Trong đó $1 \in Q_{21}$. Do vậy $1$ là căn bậc hai chính của $1 \mod 21$.
- $4$ căn bậc hai của $16 \mod 21$ là: $4,10,11,17$. Trong đó $4 \in Q_{21}$. Do vậy $4$ là căn bậc hai chính của $16 \mod 21$.

---

> **Một số Thuật toán tìm căn bậc hai theo modulo n**
- **++Thuật toán 1:++** Tìm căn bậc hai của $a \mod p$ với $p \equiv 3 \pmod 4$.
- **Input:** Số nguyên tố lẻ $p$; $p \equiv 3 \pmod 4$ và $a \in Q_p$.
- **Output:** $2$ căn bậc hai của $a \mod p$.
- **Thuật toán:**

    1. Tính r = a^(p+1)/4 mod p
    2. return (r, -r)

- **Ví dụ:**

    from Crypto.Util.number import *

    # tạo số nguyên tố 4k + 3
    def gen_prime(nbits):
        while True:
            p = getPrime(nbits)
            if p % 4 == 3:
                break
        return p

    p = gen_prime(64) #14478919332384239767
    a = getPrime(8) #157

    def sqrt_mod(a, p):
        # a phải thuộc tập Qp, tức bản thân nó phải có căn
        assert pow(a, (p-1)//2, p) == 1

        r = pow(a, (p+1)//4, p)

        return (r, -r % p)

    print(f"{a = }")
    print(f"{p = }")
    x, y = sqrt_mod(a, p)

    assert pow(x, 2, p) == a and pow(y, 2, p) == a
    print(f"{x, y = }")
    # (1843963708521949480, 12634955623862290287)

---

- **++Thuật toán 2:++** Tìm căn bậc hai của $a \mod p$ với $p \equiv 5 \pmod 8$.
- **Input:** Số nguyên tố lẻ $p;$ $p \equiv 5 \pmod 8$ và $a \in Q_p$.
- **Output:** $2$ căn bậc hai của $a \mod p$.
- **Thuật toán:**

    1. Tính d = a^(p-1)/4 mod p
    2. Nếu d = 1 thì ta tính r = a^(p+3)/8 mod p
    3. Nếu d = p-1 thì ta tính r = 2a*(4a)^(p-5)/8 mod p
    4. return (r, -r)

- **Ví dụ:**

    from Crypto.Util.number import *

    # tạo số nguyên tố 8k + 5
    def gen_prime(nbits):
        while True:
            p = getPrime(nbits)
            if p % 8 == 5:
                break
        return p

    p = gen_prime(64) #9910265760910607149
    a = getPrime(8) #191

    def sqrt_mod(a, p):
        # a phải thuộc tập Qp
        assert pow(a, (p-1)//2, p) == 1

        d = pow(a, (p-1)//4, p)

        if d == 1:
            r = pow(a, (p+3)//8, p)
        elif d == p-1:
            r = (2 * a * pow(4*a, (p-5)//8, p)) % p
        else:
            return None

        return (r, -r % p)

    print(f"{a = }")
    print(f"{p = }")
    x, y = sqrt_mod(a, p)

    assert pow(x,2,p) == a and pow(y,2,p) == a
    print(f"{x,y = }")
    # (8159618136968258823, 1750647623942348326)

---

- **++Thuật toán 3:++** Tìm căn bậc hai của $c \mod n$ với $n=p\times q$; $p \equiv 3 \pmod 4$; $q \equiv 3 \pmod 4$
- **Input:** Số nguyên $n$; $p,q$ và $c \in Q_n$.
- **Output:** $4$ căn bậc hai của $c \mod n$
- **Thuật toán:**

    1. Dùng thuật toán Euclid mở rộng để tìm hai số a,b thỏa mãn: a*p + b*q = 1
    2. Tính:
        r = c^(p+1)/4 mod p
        s = c^(q+1)/4 mod q

        x = (a*p*s + b*q*r) mod n
        y = (a*p*s - b*q*r) mod n
    3.return (±x, ±y)

- **Ví dụ:**

    from Crypto.Util.number import *

    # hàm tính Euclid mở rộng
    def egcd(a, b):
        if b == 0:
            d, x, y = a, 1, 0
            return (d, x, y)

        x2, x1 = 1, 0
        y2, y1 = 0, 1

        while b > 0:
            q = a // b
            r = a % b

            x = x2 - q * x1
            y = y2 - q * y1

            a, b = b, r

            x2 = x1
            x1 = x

            y2 = y1
            y1 = y

        d, x, y = a, x2, y2
        return (d, x, y)       

    # tạo số nguyên tố 4k + 3
    def gen_prime(nbits):
        while True:
            p = getPrime(nbits)
            if p % 4 == 3:
                break
        return p

    def sqrt_mod(c, n):
        d, a, b = egcd(p, q)

        r = pow(c, (p+1)//4, p)
        s = pow(c, (q+1)//4, q)

        x = (a*p*s + b*q*r) % n
        y = (a*p*s - b*q*r) % n

        return ((x, -x % n, y, -y % n))

    while True:
        try:
            p, q = gen_prime(64), gen_prime(64) 
            n = p * q
            c = getPrime(16) 
            # c phải có căn bậc hai mod n
            assert pow(c, (p-1)//2, p) * pow(c, (q-1)//2, q) == 1

            # 4 nghiệm
            x = sqrt_mod(c, n)

            if x:
                # đảm bảo  mũ hai của 4 nghiệm đều ra c
                assert all(pow(i, 2, n) == c for i in x)

                print(f"{c = }")
                print(f"{p = }")
                print(f"{q = }")
                print(f"{x = }")
                break
        except:
            continue
            
    #c = 59473
    #p = 13330698667827392939
    #q = 15068154159563508007
    #x = (29544105786808492182804987494227445882, 171324916794702553663340065021834316691, 121577661115858318052386208407844295385, 79291361465652727793758844108217467188)

---

- **++Thuật toán 4:++** Tìm căn bậc hai của $a \mod p$, $p$ là số nguyên tố lẻ bất kỳ. Ta gọi thuật toán này là thuật toán **Toneli-Shanks**.
- **Input:** Số nguyên tố lẻ, số nguyên $a$, $1 \leq a \leq p-1$.
- **Output:** $2$ căn bậc hai của $a \mod p$ nếu $a \in Q_p$.
- **Thuật toán:**

    1. Tính ký hiệu (a/p), nếu kết quả là -1 thì Exit
    2. Chọn số nguyên b: 1 <= b <= p-1 sao cho (a/p) = -1 tức (b ∉ Qp)
    3. Phân tích: p-1 = 2^s * t (t là số lẻ)
    4. Tính a^-1 mod p
    5. Đặt c = b^t mod p; r = a^(t+1)/2 mod p
    6. For i from 1 to s-1 do:
        6.1 Tính d = (r^2 * a^-1)^(2^(s-i-1)) mod p
        6.2 Nếu d ≡ -1 (mod p) thì đặt r = r * c mod p
        6.3 c = c^2 mod p
    7. return (r, -r)

- **Ví dụ:**

    from Crypto.Util.number import *

    def legendre_symbol(a, p):
        return pow(a, (p - 1) // 2, p)

    def tonelli_shanks(a, p):
        # Bước 1: Tính ký hiệu Legendre (a/p)
        if legendre_symbol(a, p) == p - 1:
            return None  # a không có căn bậc hai mod p

        # Bước 2: Chọn b sao cho (b/p) = -1
        b = 2
        while legendre_symbol(b, p) != p - 1:
            b += 1

        # Bước 3: Phân tích p-1 = 2^s * t, với t lẻ
        s = 0
        t = p - 1
        while t % 2 == 0:
            s += 1
            t //= 2

        # Bước 4: Tính a^-1 mod p
        a_inv = pow(a, -1, p)

        # Bước 5: Đặt c = b^t mod p, r = a^((t+1)/2) mod p
        c = pow(b, t, p)
        r = pow(a, (t + 1) // 2, p)

        # Bước 6: Vòng lặp chính
        for i in range(1, s):
            d = pow((r * r * a_inv) % p, 2 ** (s - i - 1), p)
            if d == p - 1:
                r = (r * c) % p
            c = (c * c) % p

        # Bước 7: Trả về (r, -r)
        return r, p - r

    # thuật toán này có thể tính với bất kỳ số nguyên tố lẻ nào
    p = getPrime(64) #15665986565251892539 
    a = getPrime(8) #151
    print(f"{a = }")
    print(f"{p = }")

    roots = tonelli_shanks(a, p)
    if roots:
        print(f"căn bậc hai của {a} mod {p} là: {roots}")
    else:
        print("a không có căn bậc hai mod p :(")
    # (1131347568394072411, 14534638996857820128)

---

- **++Thuật toán nhân bình phương có lặp:++**
- **Input:** $a\in Z_n$ và số nguyên $0 \leq k < n$ có biểu diễn nhị phân bên dưới:
$$ k = \sum_{i=0}^{t}(k_i \times 2^i)$$
- **Output:** $a^k \mod n$

    1. Đặt b = 1
        Nếu k = 0 thì Return b
    2. Đặt A = a
    3. Nếu k0 = 1 thì đặt b = a
    4. For i from 1 to t do:
        4.1. Đặt A = A^2 mod n
        4.2. Nếu ki = 1 thì b = A*b mod n
    5. return b

- **Ví dụ:** tính $5^{596} \mod 1234$

    def power(a, k, n):
        t = bin(k)[2:][::-1]
        b = 1
        A = a

        if t[0] == "1":
            b = a

        for i in t[1:]:
            A = pow(A, 2, n)
            if i == "1":
                b = (A * b) % n

        return b

    print(power(5, 596, 1234)) #1013

- Để dễ hình dung thì ta sẽ biểu diễn bằng một bảng như sau:

| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| --- | --- | --- | --- | --- | --- | --- | --- | -------- | -------- | -------- |
|ki| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
|A | 5 | 25 | 625| 681 | 1011| 369 |421 | 779 | 947 | 925 |
| b | 1 | 1 | 625| 625 | 67| 67 |1059 | 1059 | 1059 | **++1013++** |

---

- **++Định nghĩa++ (Bài toán Logarit rời rạc):**
- Giả sử cho $g$ là phần tử sinh của một nhóm nhân $Z^*_p$ tức là với $a \neq 0$ bất kỳ thuộc $Z^*_p$ ta có thể tìm được một số nguyên $x$ **duy nhất** thỏa mãn: $a \equiv g^x \pmod p$.
- Ta có thể viết lại $x \equiv \log_ga \pmod p$
- Bài toán Logarit rời rạc chính là bài toán tìm $x$ khi biết $g$ và $a$.

---

- **++Thuật toán bước lớn bước nhỏ:++** Giải bài toán $\log_{\alpha}\beta$ trên $Z^*_n$, với $\alpha$ là phần tử sinh của $Z^*_n$.
- **Input:** $\alpha, \beta, n$.
- **Output:** $\log_{\alpha}\beta$ trên $Z^*_n$.
- **Thuật toán:**
1. Tính $m =\left \lceil \sqrt{\text{ord}(a)} \right \rceil$.
2. Lập bảng $(j, \alpha^{j} \mod n)$ với $j = \overline{0 \rightarrow m-1}$
3. Tính $\beta\cdot(\alpha^{-m})^i \mod n$ với $i = \overline{0 \rightarrow m-1}$
4. Tra bảng $(j, \alpha^j)$ cho tới khi thỏa mãn $\beta\cdot(\alpha^{-m})^i = \alpha^j$.
5. Khi đó: $\log_{\alpha}\beta = m \cdot i + j$.

- **Ví dụ:** Tính $x \equiv \log_{31}45 \pmod {61}$
- Ta có: $m = \left \lceil \sqrt{\text{ord}(31)} \right \rceil = \left \lceil \sqrt{60} \right \rceil = 8$.
- Tiến hành lập bảng $(j, 31^j)$ với $j = \overline{0 \rightarrow 7}$

| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| --- | --- | --- | --- | --- | --- | -------- | -------- | -------- |
| $31^j \mod 61$ | 1 | 31 | 46 | 23 | 42| 21 | 41 | 51 |

- Ta có $31^{-1} \mod 61 =2 \Rightarrow 31^{-8} \mod 61 = 2^8 \mod 61 = 12$. Ta lập bảng tính $\beta\cdot(\alpha^{-m})^i \mod n = 45 \cdot12^i \mod 61$ với $i = \overline{0 \rightarrow 7}$.

| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| --- | --- | --- | --- | --- | --- | -------- | -------- | -------- |
| $45 \cdot 12^i \mod 61$ | 45 | 52 | 14 | 46 | 3 | 36 | 5 | 60 |

- Từ hai bảng, ta thấy rằng tại $j = 2, i = 3$ thì $31^j \equiv 41\cdot 12^i \pmod {61}$.
- Vì vậy giá trị của $\log_{31}45 \pmod {61}$ sẽ là $m \cdot i + j = 8 \cdot 3 + 2 = 26$.

---
<h1 style="text-align:center;">END</h1>