# Các kiến thức toán cơ bản
## Cấu trúc đại số
### Phép toán 2 ngôi
* Định nghĩa: Cho X là một tập hợp khác rỗng. Một phép toán 2 ngôi trên X là một ánh xạ kí hiệu * :
* $X \times X \rightarrow X$
* $(x,y) \mapsto x*y$ ( $\mapsto$ là ký hiệu ánh xạ)
> Hiểu là với hai phần tử $x,y \in X$, thì qua phép toán $x*y$ vẫn thuộc tập $X$ (tính đóng)
**Một số thuật ngữ:**
* Phép toán $(*)$ có tính chất kết hợp nếu $(x*y)*z=x*(y*z)$ với mọi $x,y,z \in X$
* Phép toán $(*)$ có tính chất giao hoán nếu $x*y=y*x$ với mọi $x,y \in X$
* Có phần tử trung lập $e$ nếu $e*x=x*e=x$ với mọi $x \in X$ (trong phép cộng, phần tử trung lập được gọi là phần tử trung hòa, trong phép nhân, phần tử trung lập được gọi là phần tử đơn vị)
* phần tử $x \in X$ có phần tử nghịch đảo $x'$ nếu $x*x'=e$
**Ví dụ:** Xét $1 \in \mathbb{N}$, $2 \in \mathbb{N}$ nhưng $1-2=-1 \notin \mathbb{N}$, nên phép trừ trong tập $\mathbb{N}$ không phải là một phép toán 2 ngôi, nhưng là một phép toán 2 ngôi trên $\mathbb{Z}$. Vì $a,b \in \mathbb{Z}$, thì $a-b \in\mathbb{Z}$ .
### Nhóm
* Định nghĩa: Cho $G$ là một tập khác rỗng, cùng với phép toán 2 ngôi $(*)$. Khi đó $G$ được gọi là 1 nhóm nếu:
* $(*)$ trên $G$ có tính chất kết hợp
* $(*)$ trên $G$ có phần tử đơn vị
* Mọi $x \in G$ có phần tử nghịch đảo
Nếu $(*)$ trên $G$ có thêm tính chất giao hoán, thì $G$ được gọi là **nhóm giao hoán** hay **nhóm Abel**
* **Ví dụ:** $\mathbb{Z}_n= \{ \bar{0}, \bar{1}, \bar{2}, \dots, \overline{n-1} \}$ là tập các số nguyên modulo n.
Xét phép (+) được xác định như sau:
* $\overline{a} + \overline{b} = \overline{a+b}$ là một phép toán 2 ngôi trên $\mathbb{Z}_n$
* Có tính chất kết hợp $(\overline{a} + \overline{b}) + \overline{c}
= \overline{a+b} + \overline{c} = \overline{a+(b+c)} = \overline{a} + (\overline{b} + \overline{c})$
* Có phần tử trung lập là $\overline{0}$ do $\overline{a} + \overline{0} = \overline{a}$
* Với mọi $\overline{a} \in \mathbb{Z}_n$, có phần tử đối xứng là $-\overline{a}= \overline{n-a}$
* Có tính chất giao hoán $\overline{a} + \overline{b} = \overline{b} + \overline{a}$
$\Rightarrow$ Vậy $(\mathbb{Z}_n, +)$ là một nhóm Abel
### Cấp của nhóm, cấp của phần tử
* Cấp của nhóm G là số phần tử trong G, cấp của phần tử $a \in G$ là số nguyên dương $m$ nhỏ nhất thỏa mãn: $a^{m} = e$
* Kí hiệu:
* ord(G) hoặc $|G|$
* ord(a) hoặc $|a|$
* **Ví dụ:** Với $G = (\mathbb{Z}_3, +)$ thì các phần tử trong nhóm là $G = \{0,1,2\}$, vì có 3 phần tử nên bậc của $G$ là 3 hay $|G|=3$ có phần tử đơn vị là 0.
| a | 0 | 1 | 2 |
| -------- | -------- | -------- | -------- |
| ord(a) | 1 | 3 | 3|
* Cấp của 0 là 1 vì 0 mod 3 = 0
* Cấp của 1 là 3 vì 1 + 1 + 1 mod 3 = 0
* Cấp của 2 là 3 vì 2 + 2 + 2 mod 3 = 0
> Vì $|G|=3$ nên cấp của các phần tử trong nhóm $G$ sẽ là ước của 3
### Nhóm vòng (nhóm xyclic)
* **Định nghĩa:** Nhóm $G$ được gọi là nhóm xyclic nếu như tồn tại một phần tử $a \in G$ sao cho mọi phần tử thuộc $G$ tồn tại một số nguyên $i>0$ sao cho $b=a^i$. Phần tử a đượ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⟩$
* **Ví dụ:** Nhóm $\mathbb{Z}_7^*$ có phần tử sinh là 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.$$
### Vành
**Định nghĩa:** Cho một tập R khác rỗng và phép toán 2 ngôi $(\times, +)$ được gọi là một vành nếu thỏa mãn các điều kiện sau:
* **Về Phép Cộng (+):**
* $(R, +)$ là một nhóm Abel (có tính đóng, kết hợp, giao hoán, có phần tử đơn vị, phần tử nghịch đảo).
* **Về Phép Nhân ($\times$):**
* $(R, \times)$ có tính đóng, tính kết hợp.
* Nghĩa là: $a \times b \in R$ thì $(a \times b) \times c = a \times (b \times c) = a \times b \times c$.
* **Tính phân phối phép nhân với phép cộng**
* $a \times (b + c) = (a \times b) + (a \times c)$
* $(a + b) \times c = (a \times c) + (b \times c)$
* Nếu phép nhân có tính giao hoán thì tạo thành **vành giao hoán**
* Nếu phép nhân có tính nghịch đảo và không có thương 0 (tức là không có hai phần khác 0 mà tích của chúng lại bằng 0), thì nó tạo thành **miền nguyên**
Ký hiệu: $(\text{R}, +, \times)$
* **Ví dụ:**
* Tập hợp số nguyên $(\mathbb{Z}, +, \times)$ là ví dụ cơ bản nhất của một vành giao hoán có đơn vị và là miền nguyên.
* Xét trên nhóm $\mathbb{Z}_6 =\{ 0,1,2,3,4,5\}$ tồn tại 2 và 3, mà $2 \times 3 = 0 \bmod 6$, nên đây không phải là miền nguyên
* Vành ma trận 3x3 không phải là một vành giao hoán
$$A = \begin{pmatrix}
1 &2 &3 \\
0 &1 &0 \\
2 &0 &1 \\
\end{pmatrix},
B = \begin{pmatrix}
1 &0 &0 \\
0 &1 &0 \\
0 &0 &1 \\
\end{pmatrix}$$
Vì $A \times B \neq B \times A$
### Trường
* Định nghĩa: Trường là một tập hợp F với hai phép toán cộng và nhân, thỏa mãn tính chất sau:
* $(F, +)$ là một nhóm Abel có phần tử đơn vị là $0$
* $(F \setminus \{0\}, \times)$ là một nhóm Abel có phần tử đơn vị là $1$
* Có thể nói là có các phép toán cộng trừ, nhân, chia số khác 0. Phép trừ được coi là phép cộng đối với số đối của phép cộng và phép chia là nhân với số đối của phép nhân:
* $a - b = a + (-b)$
* $\frac{a}{b} = a*b^{-1}$
* **Ví dụ:** Xét $(\mathbb{Z}_5 , +, \times)$
* $(\mathbb{Z}_5, +)$ là nhóm Abel có phần tử đơn vị là $0$ (đã chứng minh ở ví dụ trước)
* $(\mathbb{Z}_5 \setminus\{0\}, \times)$
* Do 5 là số nguyên tố, nên $a\times b \not\equiv 0 \bmod 5$, suy ra $a \times b= \overline{ab} \in \mathbb{Z}_5 \setminus\{0\}$ $\rightarrow$ Tính đóng
* Có tính kết hợp
* Có phần tử đơn vị là 1
* Có phần tử nghịch đảo (1x1=1, 2x3=1 mod 5, 4x4=1 mod 5)
* Phép nhân trong $\mathbb{Z}$ có tính giao hoán
Suy ra $(\mathbb{Z}_5 \setminus\{0\}, \times)$ là nhóm Abel
Vậy $(\mathbb{Z}_5 , +, \times)$ là một trường
Bảng so sánh Nhóm – Vành – Trường
| Đặc điểm | Nhóm (Group) | Vành (Ring) | Trường (Field) |
|--------|--------------|-------------|----------------|
| **Phép toán** | Một phép toán (ký hiệu $*$) | Hai phép toán $(+, *)$ | Hai phép toán $(+, *)$ |
| **Tính kết hợp** | $a*(b*c) = (a*b)*c$ | $a*(b*c) = (a*b)*c$ ;<br>$a+(b+c) = (a+b)+c$ | $a*(b*c) = (a*b)*c$;<br>$a+(b+c) = (a+b)+c$ |
| **Tính giao hoán** | Không bắt buộc;<br>nếu có thì là **nhóm Abel** | Phép $+$ luôn giao hoán;<br>phép $*$ không bắt buộc (nếu có là **vành giao hoán**) | Luôn có:<br>$a*b = b*a$, $a+b = b+a$ |
| **Phần tử đơn vị** | Có phần tử đơn vị $e$ | Phép $+$ có $0$;<br>phép $*$ không bắt buộc | Phép $+$ có $0$;<br>phép $*$ có $1$ |
| **Phần tử nghịch đảo** | Mỗi phần tử đều có nghịch đảo | Phép $+$ có phần tử đối;<br>phép $*$ không nhất thiết có | Mọi phần tử khác $0$ đều có nghịch đảo nhân |
| **Tính phân phối** | Không bắt buộc| $a*(b+c)=a*b+a*c$;<br>$(b+c)*a=b*a+c*a$ | Luôn có tính phân phối |
| **Ví dụ** | $(\mathbb{Z},+)$;<br>$(\mathbb{Q},+)$;<br>$(\mathbb{R},+)$ | $(\mathbb{Z},+,\times)$| $(\mathbb{Q},+,\times)$;<br>$(\mathbb{R},+,\times)$;<br>$(\mathbb{C},+,\times)$ |
## Số học modulo
### Tính chia hết
* Cho 2 số nguyên $a$ và $n$, $n-1$. Thực hiện phép chia $a$ cho $n$ ta sẽ được 2 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, ký hiệu là a div n.
* $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 $a \pmod n = b \pmod n$
**Ví dụ:**
* $100 \bmod 11 = 1$
* $34 \bmod 11 = 1$
$\Rightarrow 100 \equiv 34 \bmod 11$
### Đại diện
* Đại diện của a mod: Số b được gọi là đại diện của a theo modulo n nếu $a \equiv b \pmod n$ và $0 \leq b < n$
* Ví dụ: $-12 \equiv -5 \equiv 2 \equiv 9 \pmod 7$ nên 2 là đại diện của -12, -5, 2 và 9 (mod 7).
* Tập các đại diện của các số nguyên theo modulo n gồn n phần tử ký hiệu:
$Z_n = \left\{0,1,2,3,\dots,n-1 \right\}$
* Ví dụ: $Z_7 = \{0,1,2,3,4,5,6\}$
### Các phép toán số học trên modulo
* Với phép cộng: $(a + b) \bmod n = (a \bmod n + b \bmod n) \bmod n$
* Với phép nhân: $(a \times b) \bmod n = (a \bmod n \times b \bmod n) \bmod n$
> Khi thực hiện các phép toán, có thể thay các số bằng só tương đương theo modulo n hoặc có thể thực hiện các phép toán trên các đại diện của nó
#### Tính chất rút gọn
* Nếu $(a+b) \equiv (a+c) \pmod n$ thì $b \equiv c \bmod n$
* Nhưng $(a\times b) \equiv (a \times c) \pmod n$ thì $b\equiv c \pmod n \Leftrightarrow \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 + 3^{17}) \\
&\equiv(6 + 3\times (((3^{2})^{2})^2)^2) \\
&\equiv(6 + 3 \times 4) \\
&\equiv 4\\
\end{align}$
#### Ước chung lớn nhất
Số nguyên $d$ được gọi là UCLN của $a$ và $b$ nếu $a$ và $b$ đều chia hết cho $d$ và mọi ước chung của $a$ và $b$ đều là ước của $d$.
* Ký hiệu: $gcd(a,b)$ là UCLN của $a$ và $b$
* Với mọi a, ta có $gcd(a,0) = a$
* Quy ước: $gcd(0,0) = 0$
#### Thuật toán tìm Euclide
* Thuật toán Euclide tìm $gcd(a,b)$:
```
1. A = a, B = b
2. while B>0
R = A mod B
A = B, B = R
3. Return A
```
Áp dụng tính gcd(1970, 1066)
```python=
def gcd(a,b):
while b>0:
r = a%b
a = b
b = r
return a
print(gcd(1970,1966))
```
Chạy đoạn code trên được kết quả là 2.
#### Euclide mở rộng
* Nếu $gcd(a,b)=d$ thì phương trình bất định $a.x + b.y=d$ có nghiệm nguyên x,y. Và một nghiệm nguyên x,y như vậy có thể được tính bằng thuật toán Euclide mở rộng.
* Điều kiện cần và đủ để có nghịch đảo là $d=1$ và khi đó x là nghịch đảo a mod b, y là nghịch đảo b mod a
> Chỉ khi gcd(a,b)=1 thì mới tồn tại phần tử nghịch đảo
* Ta mở rộng thuật toán Euclide:
* Tìm ước chung lớn nhất của a và b
* Tính nghịch đảo trong trường hợp $gcd(a,b)=1$
* **Thuật toán euclide mở rộng**
```
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)
```
Áp dụng thuật toán để tìm x,y với a=1579, b=550:
```python=
def gcd(a,b):
if(a<b):
a,b=b,a
if b==0:
return a
else:
x1=0
x2=1
y1=1
y2=0
while b>0:
q=a//b
r=a-q*b
x=x2-q*x1
y=y2-q*y1
a=b
b=r
x2=x1
x1=x
y2=y1
y1=y
d=a
x=x2
y=y2
return(d,x,y)
a=1579
b=550
print(gcd(a,b))
```
được kết quả là `(1, -31, 89)`
#### Số nguyên tố
* Số nguyên $a>1$ được gọi là số nguyên tố nếu $a$ chỉ có 2 ước là 1 và chính nó.
* Ví dụ: 2,3,5,7,11,13,17,19,23,27,29,31,37,41,43,47,59,61,67,71,73,79,83,89,97 là các số nguyên tố nhỏ hơn 100
* Số nguyên tố là trung tâm của lý thuyết số, số các số nguyên tố là vô hạn.
* Một trong những bài toán cơ bản của số học là phân tích ra thừa số nguyên tố, tức là viết nó dưới dạng tích của các số nguyên tố. Mọi số nguyên dương đều có phân tích **duy nhất** thành tích cá 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$
* **Nguyên tố cùng nhau:** Hai số $a$ và $b$ được gọi là nguyên tố cùng nhau nếu ước chung duy nhất của chúng là $1$
* Ví dụ: $gcd(8,9)=1$, nên 8 và 9 là hai số nguyên tố cùng nhau
#### Định lý Ferma (Định lý Fermat nhỏ)
* 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-1} \bmod p\equiv 1$
* Có thể biến đổi thành: $a^{p} \bmod p\equiv a$ hay $a^{p}-a$ chia hết cho $p$
* Ví dụ: Có 5 và 7 là 2 số nguyên tố
* Do $2<7$ nên ta có $2^{7-1} \bmod 7\equiv 1$ hay $2^{6}\bmod 7 = 64 \bmod 7\equiv 1$
* Do $3<5$ nên ta có $3^{5-1} \bmod 5\equiv 1$ hay $3^{4} \bmod 5=81 \bmod 5\equiv 1$
#### Hàm φ(n)
* Tập $Z_n = \left\{0,1,2,3,\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** (nhóm nhân của $Z_n$)
* Nếu p là số nguyên tố thì $Z^*_n = \{1,2,..., p-1\}$
* Ký hiệu $\phi(n)$ là số phần tử lớn hơn 0, nhỏ hơn n và nguyên tố cùng nhau với n
* **Các tính chất của hàm $\phi(n):$**
* Nếu $p$ nguyên tố $\rightarrow$ $\phi(p) = p-1$
* Nếu $gcd(m,n)=1$ thì $\phi(m.n)=\phi(m)\cdot\phi(n)$
* Nếu $n = p^{e_1}_1 \times p^{e_2}_2 \times \dots \times p^{e_k}_k$ với $p^{e_i}_i$ là các 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)=\phi(5^2)=25\times(1-\frac15)=20$
* $\phi(18)=\phi(2\times 9)= \phi(2) \times \phi(9) = 1 \times 9 \times \frac{3-1}{3} = 6$
* $\phi(21) = \phi(3 \times 7) = \phi(3) \times \phi(7) = 2 \times 6 = 12$
#### Định lý Ole
* Định lý Ole là tổng quát hóa của định lý Ferma. Định lý Ole khẳng định với mọi cặp số nguyên dương $a$ và $n$ sao cho $gcd(a,n)=1$ thì $a^{\phi(n)} \bmod n =1$
* Nếu n là tích các số nguyên khác nhau và $r \equiv s \bmod \phi(n)$ thì $a^r \equiv a^s \bmod n$
* Ví dụ:
* $a = 3, n = 10, \phi(10) = 4$. nên $3^4 = 81 = 1 \bmod 10$
* Tương tự với $a = 2, n = 11, \phi(11) = 10$. nên $2^{10} = 1024 = 1 \bmod 11$
#### Nhóm nhân $Z_n$
* 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^*$, được kí hiệu là: $|Z_n^*|$
* Theo định nghĩa hàm phi Euler: $|Z_n^*|=\phi(n)$
#### Cấp của phần tử
* Cho $a\in Z^*_n$. Cấp a kí hiệu ord(a) là số nguyên dương $t$ nhỏ nhất sao cho $a^t \equiv 1 \bmod n$.
* Cấp của các phần tử trong $Z^*_n$ thuộc tập ước của $|Z_n^*|$
* Ví dụ: Với $|Z_{20}^*|$
* Ta có $\phi(20)=\phi(4 \times 5) = 8$
* $Z_{20}^*=\{1,3,7,9,11,13,17,19\}$
* Ta có tập ước của 8 là $U=\{1,2,4,8\}$
* Lấy lần lượt lũy thừa của các phần tử với các số mũ trên đến khi thõa mãn điều kiện, ta được bảng sau
| a | 1 | 3 | 7 | 9 | 11 | 13 | 17 | 19 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| ord(a) | 1 | 4 | 4 | 2|2|4|4|2|
#### Phần tử sinh
- Phần tử $\alpha \in \mathbb{Z}_n^{*}$ được gọi là **phần tử sinh** của $\mathbb{Z}_n^{*}$ nếu:
$\mathbb{Z}_n^{*} = \{\alpha^i \bmod n \mid 0 \le i \le \varphi(n)-1\}$
- Cho $\alpha \in \mathbb{Z}_n^{*}$. Nếu **cấp của $\alpha$** bằng $\varphi(n)$ thì $\alpha$ được gọi là **phần tử sinh** của $\mathbb{Z}_n^{*}$ (hay còn gọi là **phần tử nguyên thủy**).
- Nếu $\mathbb{Z}_n^{*}$ có phần tử sinh thì $\mathbb{Z}_n^{*}$ được gọi là **nhóm xyclic**.
Ví dụ
- Xét $\mathbb{Z}_{20}^{*}$, có
$\phi(20) = |\mathbb{Z}_{20}^{*}| = 8$, mà $max(\operatorname{ord}(a)) = 4 \ne 8,\quad \forall a \in \mathbb{Z}_{20}^{*}$
- Do đó, $\mathbb{Z}_{20}^{*}$ **không có phần tử sinh**.
* Tính chất của phần tử sinh
- $Z^*_n$ có phần tử sinh $\Leftrightarrow$ $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$. Áp dụng tính chất số 3, ta có $A = \{\alpha^i \bmod n \mid \text{gcd}(i, \phi(n)) = 1\}=\{1,3,7,9,11,13,17,19,21,23\}$ 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\}$
> $2^{21}$ và $2^{23}$ lần lượt lặp lại các phần tử sinh đã tìm được
* Ví dụ: Tìm phần tử sinh của $Z_{37}^*$. Từ phần tử sinh vừa tìm được tìm tất cả các phần tử sinh còn lại của $Z_{37}^*$
* $Z_{37}^*=\{1,2,..., 35, 36\}$
* $\phi(37)=36=2^2 \times 3^2$
* Áp dụng tính chất số 4, phần tử sinh thỏa mãn $a^{36/2}\bmod 37 \not\equiv 1$ và $a^{36/3}\bmod 37 \not\equiv 1$
* Xét x=2, $2^{36/2}\bmod 37 \equiv 36$ và $2^{36/3}\bmod 37 \equiv 26$, nên 2 là phần tử sinh của $Z_{37}^*$
* Ta có: $36 = 2^2 \times 3^2$ nên các số $k$ thỏa $\gcd(k,36)=1$ là: $k \in \{1,5,7,11,13,17,19,23,25,29,31,35\}$, lần lượt thu được tập giá trị của các phần tử sinh là: $\{2,32,17,13,15,18,35,5,20,24,22,19\}$
#### Định lý phần 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ý phần 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$$
- $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}$
* Ví dụ: Giải hệ phương trình $\left\{\begin{matrix}
x \equiv 10 \bmod {11} \\
x \equiv 19 \bmod {21} \\
x \equiv 20 \bmod {26} \\
\end{matrix}\right.$
Áp dụng định lý phần dư Trung Hoa, code như sau:
```python=
n = [11,21,26]
a = [10,19,20]
N = 11*21*26
x=0
for i in range(3):
ni =N//n[i]
mi = pow(ni,-1,n[i])
x += (a[i]*ni*mi)%N
print(x%N)
```
được kết quả là 670, vậy 670 là nghiệm của hệ phương trình
* Đị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 \bmod {n_1} \\
x \equiv a \bmod {n_2} \\
\end{matrix}\right.$ có nghiệm duy nhất $x \equiv a \bmod n_1 \times n_2$
#### Định nghĩa thặng dư bậc hai và bất thặng dư bậc hai
* **Đị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$.
* Ví dụ: Xét các bình phương của $Z_7^*$:
* $1^2=1$, $2^2=4$, $3^2=2$, $4^2=2$, $5^2=4$, $6^2=1$
* Vậy $Q_7 = \{1,2,4\}$, $\overline{Q}_7 = \{3,5,6\}$
* **Đị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}$
> Hiểu là với $Z_p^*$ mà p là số nguyên tố, một nửa các phần tử trong $Z_p^*$ là thặng dư bậc 2, nửa còn lại là bất thặng dư bậc 2
* Ví dụ: Cho 3 là phần tử sinh của $Z^*_{17}$
Ta có:
$$
\begin{aligned}
3^0 &\equiv 1 \pmod{17} \\
3^2 &\equiv 9 \pmod{17} \\
3^4 &\equiv 13 \pmod{17} \\
3^6 &\equiv 15 \pmod{17} \\
3^8 &\equiv 16 \pmod{17} \\
3^{10} &\equiv 8 \pmod{17} \\
3^{12} &\equiv 4 \pmod{17} \\
3^{14} &\equiv 2 \pmod{17}
\end{aligned}
$$
Suy ra:
$$
Q_{17} = \{1,2,4,8,9,13,15,16\}
$$ $$
\overline{Q}_{17} = \{3,5,6,7,10,11,12,14\}
$$
* **Định lý:** Cho $n = p.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 \bmod n$.
* **Định lý về số căn bậc hai của một số mod n:** 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$.
* **Ký hiệu Legendre và Jacobi**
* Ký hiệu Legendre: $p$ là số nguyên tố lẻ, $a$ là số nguyên. KH Legendre $(\frac{a}{b})$ được xác định như sau:
$\left(\frac{a}{p}\right) =
\begin{cases}
0, & \text{nếu } p \mid a, \\
1, & \text{nếu } a \in Q_p, \\
-1, & \text{nếu } a \notin Q_p
\end{cases}$
* $(\frac{a}p) = a^{\frac{(p-1)}2} \bmod p$
* Ký hiệu Jacobi: Cho $n\geq3$ là sổ nguyên lẻ $n = p^{e_1}_1 \times p^{e_2}_2 \times \dots \times p^{e_k}_k$. Khi đó, ký hiệu Jacobi đượ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}$
Vậy, nếu n nguyên tố, KH Jacobi chính là KH Lagendre
* **Các tính chất ký hiệu Jacobi**
1. Nếu $n$ là số nguyên lẻ và $m_1 \equiv m_2 \bmod n$ thì $\left(\frac{m_1}{n}\right) = \left(\frac{m_2}{n}\right)$
2. Nếu $n$ là số nguyên lẻ thì: $\left(\frac{2}{n}\right) =
\begin{cases}
1 & \text{nếu } n \equiv \pm 1 \bmod{8} \\
-1 & \text{nếu } n \equiv \pm 3 \bmod{8}
\end{cases}$
3. Nếu $n$ là số nguyên lẻ thì: $\left(\frac{m_1 \cdot m_2}{n}\right) = \left(\frac{m_1}{n}\right) \left(\frac{m_2}{n}\right)$
Đặt biệt nếu $m = 2^k\cdot t$ ($t$ là số lẻ thì) $\left(\frac{m}{n}\right) = \left(\frac{2}{n}\right)^k \cdot \left(\frac{t}{n}\right)$
4. Giả sử $m$ và $n$ là số nguyên lẻ $\left(\frac{m}{n}\right) \left(\frac{n}{m}\right) =
\begin{cases}
-1 & \text{nếu } m \equiv n \equiv 3 \pmod{4} \\
1 & \text{others}
\end{cases}$+
**Số nguyên Blum:** Là một **hợp số** có dạng $n = p \cdot q$, trong đó $p$ và $q$ là các số nguyên tố khác nhau thỏa mãn:
$$p \equiv 3 \pmod 4 \quad \text{và} \quad q \equiv 3 \pmod 4$$
**Định lý:** Cho $n = p \cdot q$ là một **số nguyên Blum** và cho $a \in Q_n$. Khi đó $a$ có đúng **4 căn bậc hai** modulo $n$ và chỉ có **một** số nằm trong $Q_n$.
**Căn bậc hai chính:** Cho $n$ là số nguyên Blum và $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** (Principal Square Root) của $a \pmod n$.
Ví dụ: $n = 21$; $Q_{21} = \{1, 4, 16\}$
* 4 căn bậc hai của $4 \bmod{21}$ là: $2; 5; 16; 19$. Mà $16 \in Q_{21}$. Do vậy **16** là căn bậc hai chính của $4 \bmod{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 \pmod p$ (khi $p \equiv 3 \pmod 4$)
**Input:** Số nguyên tố lẻ **$p$**; $p \equiv 3 \pmod 4$; $a \in Q_p$.
**Output:** 2 căn bậc hai của $a \pmod p$.
1. Tính $r = a^{(p+1)/4} \pmod p$
2. Return $(r, -r)$
* Thuật toán 2: Tìm căn bậc hai của $a \pmod p$ (khi $p \equiv 5 \pmod 8$)
**Input:** Số nguyên tố lẻ **$p$**; $p \equiv 5 \pmod 8$; $a \in Q_p$.
**Output:** 2 căn bậc hai của $a \pmod p$.
1. Tính $d = a^{(p-1)/4} \pmod p$
2. Nếu $d = 1$ thì tính $r = a^{(p+3)/8} \pmod p$
3. Nếu $d = p - 1$ thì tính $r = 2a \cdot (4a)^{(p-5)/8} \pmod p$
4. Return $(r, -r)$
* Thuật toán 3: Tìm 4 căn bậc hai của $c \pmod n$ (khi $n$ là Số nguyên Blum)
**Input:** Số nguyên $n$; $p$, $q$ (sao cho $n=p \cdot q$, $p \equiv 3 \pmod 4$ và $q \equiv 3 \pmod 4$); $c \in Q_n$.
**Output:** 4 căn bậc hai của $c \pmod n$.
1. Dùng thuật toán Euclide mở rộng tìm $a, b$: $ap + bq = 1$
2. Tính:
* $r = c^{(p+1)/4} \pmod p$
* $s = c^{(q+1)/4} \pmod q$
* $x = (aps + bqr) \pmod n$
* $y = (aps - bqr) \pmod n$
3. Return $(\pm x, \pm y)$
* Thuật toán 4 (Tonelli–Shanks): Tìm căn bậc hai của $a \pmod p$ (Tổng quát)
**Input:** Số nguyên tố lẻ **$p$**; số nguyên $a$, $1 \le a \le p-1$.
**Output:** 2 căn bậc hai của $a \pmod p$ nếu $a \in Q_p$.
1. Tính ký hiệu Legendre $\left(\frac{a}{p}\right)$. Nếu $\left(\frac{a}{p}\right) = -1$ thì Return "a không có căn bậc hai theo $\pmod p$".
2. Chọn số nguyên $b$: $1 \le b \le p-1$ sao cho $\left(\frac{b}{p}\right) = -1$ (tức $b \in \overline{Q}_p$).
3. Phân tích $p-1 = 2^s \cdot t$ ($t$ là số lẻ)
4. Tính $a^{-1} \pmod p$
5. Đặt $c \leftarrow b^t \pmod p$; $r \leftarrow a^{(t+1)/2} \pmod p$
6. For $i$ from 1 to $s - 1$ do
* 6.1. Tính $d = (r^2 \cdot a^{-1})^{2^{s-i-1}} \pmod p$
* 6.2. Nếu $d \equiv -1 \pmod p$ thì đặt $r \leftarrow r \cdot c \pmod p$
* 6.3. $c \leftarrow c^2 \pmod p$
7. Return $(r, -r)$
**Thuật toán nhân bình phương có lặp** được sử dụng để tính lũy thừa lớn trong modulo một cách hiệu quả (nhanh chóng).
* Input:
* $a \in \mathbb{Z}_n$
* Số nguyên $k$, $0 \le k < n$ có biểu diễn nhị phân:
$$k = \sum_{i=0}^{t} k_i 2^i$$
* Output: $a^k \pmod n$
**Bài toán Lorarit rời rạc (DLP):**
- Cho g là phần tử sinh của $\mathbb{Z}_n^*$, ta luôn tìm được $x$ thỏa $g^x \equiv a \pmod p$ <=> $x \equiv \log_ga \pmod p$
- Thuật toán baby step giant step:
- Tính $m =\left \lceil \sqrt{\text{ord}(a)} \right \rceil$
- Lập bảng $(j, \alpha^{j} \mod n)$ với $j = \overline{0 \rightarrow m-1}$
- Tính $\beta\cdot(\alpha^{-m})^i \mod n$ với $i = \overline{0 \rightarrow m-1}$
- Tìm $i, j$ thỏa: $\beta\cdot(\alpha^{-m})^i = \alpha^j$
- $\log_{\alpha}\beta = m \cdot i + j$
# Thực hành
## Modular Math
### Quadratic Residues
Challange giới thiệu thặng dư bậc hai, đề cho p và list ints. Trong list ints sẽ có 1 thặng dư bậc 2 và 2 bất thặng dư bậc 2. Đề yêu cầu tìm ra thặng dư bậc 2 đó, và tìm số nhỏ hơn trong những căn bậc hai. Mình sẽ duyệt qua $Z_p$ và bậc hai từng phần tử để tìm ra thặng dư bậc hai và căn bậc hai tương ứng.
Code như sau:
```python=
from math import gcd
p=29
ints=[14,6,11]
a=[]
for i in range(1, 29):
k = pow(i,2,29)
for j in ints:
if k==j:
print(i)
break
```
Được kết quả là 8 và 21, do đề yêu cầu lấy kết quả có giá trị nhỏ hơn nên flag là `8`
### Legendre Symbol
Challange giới thiệu về ký hiệu Lagendre, ký hiệu Lagendre là một cách vô cùng tiện để xác định một số có phải là thặng dư bậc hai hay không. Có $\left(\frac{a}{p}\right) =
\begin{cases}
0, & \text{nếu } p \mid a, \\
1, & \text{nếu } a \in Q_p, \\
-1, & \text{nếu } a \notin Q_p
\end{cases}$
mà đề cho p và một list a, vậy mình sẽ duyệt qua tất cả các phần tử trong a và tính Lagendre, nếu Lagendre bằng 1, thì a[i] có thặng dư bậc hai.
Trong link wiki mà đề bài cho, có:
Mà $p \bmod 4 \equiv 3$, nên mình sẽ áp dụng công thức tìm căn của thặng dư bậc hai. Code như sau:
```python=
from math import gcd
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
a = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
for i in a:
k = pow(i,(p-1)//2,p)
if k==1:
if p%4==3:
print(pow(i, (p+1)//4, p))
break
```
và được flag: `93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526`
### Modular Square Root
Challenge giới thiệu thuật toán Tonelli-Shanks và yêu cầu tìm $r$ là căn bậc hai của $a \bmod p$
File output đề bài cho a và p như sau:
```python=
a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
```
Ở challenge trước, ta đã học cách tìm căn bậc hai của số với $p \bmod 4 \equiv 3$, nhưng ở challenge này $p \bmod 4 \equiv 1$, nên không thể dùng công thức Fermat nhỏ như challenge trước, đề đã gợi ý thuật toán [Tonelli-Shanks](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm), đây là thuật toán tìm $r$ sao cho $r^2 \equiv n \bmod p$ ở dạng tổng quát hơn với điều kiện p là số nguyên tố. Code như sau:
```python=
def tonelli_shanks(a, p):
if pow(a, (p - 1) // 2, p) != 1:
return None
s = 0
q = p - 1
while q % 2 == 0:
q //= 2
s += 1
if s == 1:
return pow(a, (p + 1) // 4, p)
z = 2
while pow(z, (p - 1) // 2, p) != p - 1:
z += 1
# 4. Khởi tạo các giá trị cho vòng lặp
m = s
c = pow(z, q, p)
t = pow(a, q, p)
r = pow(a, (q + 1) // 2, p)
# 5. Vòng lặp chính
while True:
if t == 0: return 0
if t == 1: return r
# Tìm i nhỏ nhất sao cho t^(2^i) = 1 (mod p)
i = 0
temp = t
for j in range(1, m):
temp = pow(temp, 2, p)
if temp == 1:
i = j
break
# Cập nhật các giá trị
b = pow(c, 2 ** (m - i - 1), p)
m = i
c = pow(b, 2, p)
t = (t * c) % p
r = (r * b) % p
a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
res = tonelli_shanks(a, p)
print(min(res,p-res))
```
được flag là `2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120`
Trong thư viện sympy có hàm sqrt_mod cũng có tác dụng tương tự
```python=
from sympy import sqrt_mod
a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
print(sqrt_mod(a,p))
```
### Chinese Remainder Theorem
Challenge giới thiệu cách giải hệ phương trình đồng dư bậc nhất (CRT). Mình sẽ dùng công thức của CRT để giải challenge này, code như sau:
```python=
n = [15,11,17]
a = [2,3,5]
N=1
for i in n: N*=i
x=0
for i in range(3):
ni =N//n[i]
mi = pow(ni,-1,n[i])
x += (a[i]*ni*mi)%N
print(x%N)
```
Ta được flag là `872`
## Brainteasers Part 1
### Successive Powers
Đề bài cung cấp một dãy gồm 12 số nguyên là lũy thừa lớn liên tiếp của một số nguyên modulo cho một số nguyên tố có 3 chữ số.
Với mỗi $a_i$ thuộc dãy số đã cho, có thể viết lại như sau: $a_i \equiv x^{k+i} \pmod p$, vậy $a_{i+1} \equiv a_i \cdot x \pmod p$. Vậy, mình sẽ duyệt qua tất cả các số nguyên tố có 3 chữ số $(p)$. Với mỗi p, mình sẽ tìm một x bằng công thức $x \equiv a_1 \cdot a_0^{-1} \pmod p$, sau đó duyệt đến hết dãy xem x có thõa mản các phần tử còn lại trong dãy không. Nếu có, x chính là kết quả cần tìm. Code như sau:
```python=
from gmpy2 import *
a = [588,665,216,113,642,4,836,114,851,492,819,237]
b=[]
for p in range(100,999):
if is_prime(p):
x=a[1]*pow(a[0], -1, p)%p
check = True
for i in range(len(a)-1):
if(a[i]*x%p!=a[i+1]):
check = False
break
if check:
print(f"crypto{{{p},{x}}}")
```
được kết quả là `919 209`, đưa vào format flag của đề bài ta được flag là `crypto{919,209}`
### Adrien's Signs
Đề bài cho source code:
```python=
from random import randint
a = 288260533169915
p = 1007621497415251
FLAG = b'crypto{????????????????????}'
def encrypt_flag(flag):
ciphertext = []
plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
for b in plaintext:
e = randint(1, p)
n = pow(a, e, p)
if b == '1':
ciphertext.append(n)
else:
n = -n % p
ciphertext.append(n)
return ciphertext
print(encrypt_flag(FLAG))
```
Dựa vào source, ta thấy đề mã hóa từng bit của flag theo công thức sau:
* Nếu $b_i = 1$, thì $c_i \equiv a^e \pmod p$.
* Nếu $b_i = 0$, thì $c_i \equiv -a^e \pmod p$
Có $a = 288260533169915$ và $p = 1007621497415251$
Do $\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p = 1$, nên a là thặng dư bậc 2
* TH1 $(b_i = 1)$: $$\left(\frac{n}{p}\right) \equiv n^{\frac{p-1}{2}} \equiv (a^e)^{\frac{p-1}{2}} \equiv (a^{\frac{p-1}{2}})^e \equiv 1 \pmod p$$
* TH2 $(b_i = 0)$: $$\left(\frac{-n}{p}\right) = \left(\frac{-1}{p}\right) \cdot \left(\frac{n}{p}\right) = \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} \equiv -11\pmod p$$
Vậy:
* Nếu $b_i = 1$, $c_i$ là số chính phương.
* Nếu $b_i = 0$, $c_i$ không phải là số chính phương.
Vậy mình sẽ duyệt qua toàn bộ list đề cho. Với mỗi phần tử trong list, kiểm tra xem có phải là thặng dư bậc hai không, từ đó khôi phục lại bit 0 hoặc 1 của flag.
```=python=
from Crypto.Util.number import long_to_bytes
from elftools.construct import bin_to_int
a = 288260533169915
p = 1007621497415251
c = [67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]
flag = ""
for i in c:
n = pow(i,(p-1)//2,p)
if n==1:
flag+="1"
else:
flag+="0"
m = bin_to_int(flag)
print(long_to_bytes(m).decode())
```
### Modular Binomials
Challenge cung cấp các thông tin sau
* $N = p \cdot q$
* $c_1 \equiv (2p + 3q)^{e_1} \pmod N$
* $c_2 \equiv (5p + 7q)^{e_2} \pmod N$
Chuyển từ modulo N về modulo p ta được:
* $c_1=3q^{e1} \bmod p$
* $c_2=7q^{e2} \bmod p$
Có $c_1 \times 7q^{e2} \equiv c_2 \times 3q^{e1} \bmod p$
Vậy $c_1 \times 7q^{e2} - c_2 \times 3q^{e1}$ (A) chia hết cho $p$
Mà N chia hết cho $p$, vậy ta chỉ cần lấy $gcd(A,N)$, sẽ tìm được $p$, từ đó tìm được $q$ và suy được flag
```python=
from gmpy2 import *
N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519
p = gcd(pow(c1, e2, N)*pow(7, e1*e2, N)- pow(c2, e1, N)*pow(3, e1*e2, N),N)
q=N//p
print(f"crypto{{{p},{q}}}")
```
được flag là: `crypto{112274000169258486390262064441991200608556376127408952701514962644340921899196091557519382763356534106376906489445103255177593594898966250176773605432765983897105047795619470659157057093771407309168345670541418772427807148039207489900810013783673957984006269120652134007689272484517805398390277308001719431273,132760587806365301971479157072031448380135765794466787456948786731168095877956875295282661565488242190731593282663694728914945967253173047324353981530949360031535707374701705328450856944598803228299967009004598984671293494375599408764139743217465012770376728876547958852025425539298410751132782632817947101601}`
### Broken RSA
Đề cho các dữ liệu sau:
```
n = 27772857409875257529415990911214211975844307184430241451899407838750503024323367895540981606586709985980003435082116995888017731426634845808624796292507989171497629109450825818587383112280639037484593490692935998202437639626747133650990603333094513531505209954273004473567193235535061942991750932725808679249964667090723480397916715320876867803719301313440005075056481203859010490836599717523664197112053206745235908610484907715210436413015546671034478367679465233737115549451849810421017181842615880836253875862101545582922437858358265964489786463923280312860843031914516061327752183283528015684588796400861331354873
e = 16
ct = 11303174761894431146735697569489134747234975144162172162401674567273034831391936916397234068346115459134602443963604063679379285919302225719050193590179240191429612072131629779948379821039610415099784351073443218911356328815458050694493726951231241096695626477586428880220528001269746547018741237131741255022371957489462380305100634600499204435763201371188769446054925748151987175656677342779043435047048130599123081581036362712208692748034620245590448762406543804069935873123161582756799517226666835316588896306926659321054276507714414876684738121421124177324568084533020088172040422767194971217814466953837590498718
```
Có $ct=m^e \bmod n$ mà $e=16=2^4$, vậy $gcd(e,phi(n))\not=1$ nên không thể inverse như bình thường và công thức $ct \equiv m^e \pmod n$ sẽ có 8 nghiệm khác nhau.
> Số nghiệm m được tìm như sau:
Ta có p là số nguyên tố, nên $Z_p$ là nhóm cyclic $\rightarrow$ Các thặng dư bậc 2 được viết dưới dạng $g^x$ (với g là phần tử sinh, x là số nguyên chẵn l) $\rightarrow$ $m=g^x$
Có $ct = g^y$ $\Rightarrow$ $g^y=(g^x)^{16}=g^{16x} \bmod p$
$\Rightarrow y = 16x \mod \phi(p)$ (A)
Để phương trình (A) có nghiệm, thì $gcd(\phi(p)$ phải là ước của 16x.
Có $gcd(\phi(p), 16x)=8$ là ước của 16x, nên số nghiệm m là $gcd(\phi(p)$.
Vậy, có tất cả 8 nghiệm m
Vậy, ta cần tìm tất cả các căn bậc 16 của $ct$ modulo $n$ để tìm ra flag chính xác.
Để làm bài này, mình sẽ dùng sagemath để tìm ra các căn bậc 16 của $ct$.
* Đầu tiên, dùng hàm `IntegerModRing(n)` để tạo ra vành số nguyên, các phép lũy thừa đều được tính trong môi trường $\bmod n$.
* `R(ct)` để ép kiểu ct vào vành $Z_n$
* Dùng `nth_root` với `all=True` để tìm tất cả các căn bậc 16
Sau khi đã có list các căn bậc 16 của $ct$, mình sẽ duyệt qua các phần tử trog list, long_to_byte từng phần tử để tìm ra flag
```python=
from gmpy2 import *
from Crypto.Util.number import *
from sympy import sqrt_mod
n = 27772857409875257529415990911214211975844307184430241451899407838750503024323367895540981606586709985980003435082116995888017731426634845808624796292507989171497629109450825818587383112280639037484593490692935998202437639626747133650990603333094513531505209954273004473567193235535061942991750932725808679249964667090723480397916715320876867803719301313440005075056481203859010490836599717523664197112053206745235908610484907715210436413015546671034478367679465233737115549451849810421017181842615880836253875862101545582922437858358265964489786463923280312860843031914516061327752183283528015684588796400861331354873
e = 16
ct = 11303174761894431146735697569489134747234975144162172162401674567273034831391936916397234068346115459134602443963604063679379285919302225719050193590179240191429612072131629779948379821039610415099784351073443218911356328815458050694493726951231241096695626477586428880220528001269746547018741237131741255022371957489462380305100634600499204435763201371188769446054925748151987175656677342779043435047048130599123081581036362712208692748034620245590448762406543804069935873123161582756799517226666835316588896306926659321054276507714414876684738121421124177324568084533020088172040422767194971217814466953837590498718
m = [27772857409875257529415990911214211975844307184430241451899407838750503024323367895540981606586709985980003435082116995884478493648417679670782240786518871242668255973770988737167589482305554697589427755948133831217194514801188587815879226601454549604874476927252882744344317256396808255582550941978968312010016490081931048157003674361093215320945272838509986687284028991543505902180465028764465401474732603047959528463455521587693401684330259430026213913640315266928039931940062910914620141512756390510844994503754868094272416592656824961726496896913664170409316563677657113965998358809997237032168697425106457591932, 19131664325244422450634030181888057284566825932645013932859065813345921245302100150721638094279911113216588827243825487231002063098557924909621276728411482071837861591454363693584865315301759586921308266563936067611580289196185791534523770162296677605924247221621200132163665062728462780938899078427860492539514834564122784884525820846824317285486786477714501565842078843832366209067143458287721632488618156139644229246144251907409379065461808127071002124177670596010376484587500071693473178347738323521244278594875880819212391879441116358217255924912293481706558302078892365977976347559606848786420190701175027128464, 4630361540119164638498318880320757224917973066675767169076022453085735149562954575209814363023887599722953966126514746206394662283584514894244940779217406676431236969298024848905285314320974655688614456863292576319637071761610469243805956404043991147459322825701729779874144173432471630489234834727790764147507262408574668434851900809737757962150126473526369201692631736829290155061667970351704759675524530807701076072222629503408993408471396130684817663824749056660925873736453124432277438917606895000162811273730240312127883638799174130142263676875753527386097040244568213368833271061688815949241840749146936342957, 15737564176056916599841033439863625438741359873619873409428350041517712853447522745052672637966252714480002726272786998114955619106521084966776009613201118238135649909583974317653180478422277687820684458684774321527928987044563927906505515058742972856334634403323302530025367587134394193797074396801843068272727492465379296417977275145263441693667228539391884523651300435695869063716919455598959674392109694315795550698399558188441049675348177435343320181883658511270527502642298025431853237936690031299200526270922959774455086177296931129954687912861957268748952649407389186387930181377573214150886925056803808709793, 3539237778217166137842555505989117928829373135679837081419793629975084339895165734744802166985243124825558545835111376731639963926630733027020121729222875979138253687409199990746840367239948177008792432240913040959783652482774028474930018387772452212315504588656134688759198795637320603697276380147029386127517034728685287241008264454039149966809075617511786899506397040329859490325408881358346677488650021265701441002763289567009616142451526468236858947361753824473530778652420098975754873762941, 8641193084630835078781960729326154691277481251785227519040342025404581779021267744819343512306798872763414607838291508657015668328076920899003519564096507099659767517996462125002517796978879450563285224128999930590857350430561342116466833170797835925580962732651804341403528172806599162052851854297948186710449832526600695513390894474052550518232514835725503509214402360026644281769456259235942564623435050605591679364340655807801057347553738543963476243501794637726739064864349738727544003494877557315009597267225664763710045978917149606272530539010986831154284729835623695349775835723921166898168605699686304226409, 23142495869756092890917672030893454750926334117754474282823385385664767874760413320331167243562822386257049468955602249681623069143050330914379855513290582495066392140152800969682097797959664381795979033829643421882800567865136664407184646929050522384045887128571274693693049062102590312502516097998017915102457404682148811963064814511139109841569174839913635873363849467029720335774931747171959437436528675937534832538262278211801443004544150540349660703854716177076189675715396685988739742925008985836091064588371305270794554219559091834347522787047526785474745991669947847958918912221839199735346955651714395011916, 12035293233818340929574957471350586537102947310810368042471057797232790170875845150488308968620457271500000708809329997773062112320113760841848786679306870933361979199866851500934202633858361349663909032008161676674508652582183205744485088274351540675170575550949701943541825648400667749194676535923965610977237174625344183979939440175613426110052072774048120551405180768163141427119680261924704522719943512429440357912085349526769386737667369235691158185795806722466588046809551784989163943905925849537053349591178585808467351681061334834535098551061323044111890382507126874939822001905954801533701871344057522645080]
for i in m:
print(long_to_bytes(i))
```
Ta được flag `crypto{m0dul4r_squ4r3_r00t}`
### No Way Back Home
Đề bài cho source code sau:
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import sha256
from Crypto.Util.number import getPrime, GCD, bytes_to_long, long_to_bytes, inverse
from random import randint
FLAG = b'crypto{????????????????????????????????}'
p, q = getPrime(512), getPrime(512)
n = p * q
# Alice side
v = (p * randint(1, n)) % n
k_A = randint(1, n)
while GCD(k_A, n) != 1:
k_A = randint(1, n)
vka = (v * k_A) % n
# Bob side
k_B = randint(1, n)
while GCD(k_B, n) != 1:
k_B = randint(1, n)
vkakb = (vka * k_B) % n
# Alice side
vkb = (vkakb * inverse(k_A, n)) % n
# Bob side
v_s = (vkb * inverse(k_B, n)) % n
# Alice side
key = sha256(long_to_bytes(v)).digest()
cipher = AES.new(key, AES.MODE_ECB)
m = pad(FLAG, 16)
c = cipher.encrypt(m).hex()
out = ""
out += f"p, q = ({p}, {q}) \n"
out += f"vka = {vka} \n"
out += f"vkakb = {vkakb} \n"
out += f"vkb = {vkb} \n"
out += f"c = '{c}' \n"
with open("out.txt", "w") as f:
f.write(out)
```
Đề cho $n = p \cdot q$ và $v = (p \cdot r) \pmod n$ (với $r$ là một số ngẫu nhiên trong khoảng từ 1 tới n).Vậy nên $v$ luôn là bội của $p$. Alice chọn số bí mật $k_A$, Bob chọn số bí mật $k_B$.
Quy trình như sau:
* Alice gửi cho Bob: $vka = (v \cdot k_A) \pmod n$.
* Bob gửi lại cho Alice: $vkakb = (vka \cdot k_B) \pmod n = (v \cdot k_A \cdot k_B) \pmod n$.
* Alice tính: $vkb = (vkakb \cdot k_A^{-1}) \pmod n = (v \cdot k_B) \pmod n$.
* Khóa AES được tạo từ: $key = \text{SHA256}(v)$.
Vậy, cần phải tìm được $v$ để có được flag cần tìm.
Có $vkakb$ và $vka$ đều có ước chung là $vka$, nhưng do $gcd(vka,n)\not=1$ và $gcd(vkb,n)\not=1$, nên không thể lấy inverse như bình thường, mình sẽ chuyển từ modulo $n$ về modulo $p$, vì $v$ chia hết cho $p$, ta có
$$k_A \equiv \left(\frac{vkakb}{p}\right) \cdot \left(\frac{vkb}{p}\right)^{-1} \pmod q$$
Sau khi tìm được $k_A$, thay lại vào phương trình đầu tiên, ta có: $$v \equiv vka \cdot k_A^{-1} \pmod n$$
Và tìm được v, thay v vào sha256 và AES, ta tìm được m ban đầu. Code như sau:
```python=
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import *
p, q = (10699940648196411028170713430726559470427113689721202803392638457920771439452897032229838317321639599506283870585924807089941510579727013041135771337631951, 11956676387836512151480744979869173960415735990945471431153245263360714040288733895951317727355037104240049869019766679351362643879028085294045007143623763)
vka = 124641741967121300068241280971408306625050636261192655845274494695382484894973990899018981438824398885984003880665335336872849819983045790478166909381968949910717906136475842568208640203811766079825364974168541198988879036997489130022151352858776555178444457677074095521488219905950926757695656018450299948207
vkakb = 114778245184091677576134046724609868204771151111446457870524843414356897479473739627212552495413311985409829523700919603502616667323311977056345059189257932050632105761365449853358722065048852091755612586569454771946427631498462394616623706064561443106503673008210435922340001958432623802886222040403262923652
vkb = 6568897840127713147382345832798645667110237168011335640630440006583923102503659273104899584827637961921428677335180620421654712000512310008036693022785945317428066257236409339677041133038317088022368203160674699948914222030034711433252914821805540365972835274052062305301998463475108156010447054013166491083
c = 'fef29e5ff72f28160027959474fc462e2a9e0b2d84b1508f7bd0e270bc98fac942e1402aa12db6e6a36fb380e7b53323'
n=p*q
ka = (vkakb//p)*pow((vkb//p),-1,q)%q
kb = (vkakb//p)*pow((vka//p),-1,q)%q
v=vka*pow(ka,-1,n)%n
key = sha256(long_to_bytes(v)).digest()
cipher = AES.new(key, AES.MODE_ECB)
plaintext = unpad(cipher.decrypt(bytes.fromhex(c)), 16)
print(plaintext.decode())
```
và được flag: `crypto{1nv3rt1bl3_k3y_3xch4ng3_pr0t0c0l}`
Sign in with Wallet
Connect another wallet