# Cấu trúc đại số
## Định nghĩa Nhóm
Tập hợp **G** với phép toán nhân **(x)** gọi là nhóm, nếu nó thỏa mãn các tính chất sau với mọi phần tử $a, b, c$ thuộc **G** :

1. Tính kết hợp : $a.b.c = (a.b).c = a.(b.c)$
2. Có phần tử đơn vị e : $a.e = e.a = a$
3. Có phần tử nghịch đảo : $a.a^{-1} = a^{-1}.a = e$

<div style="background-color: #E7F3FF; padding: 10px; border-radius: 5px;">
💡 <span style="color: #007bff;">Nếu có thêm tính giao hoán : a.b = b.a, thì gọi là nhóm Abel hay nhóm giao hoán.</span>
</div>

Điều đó cũng đúng với phép toán **(+)** :
1. $a+b+c = (a+b)+c = a+(b+c)$
2. $a + e = e + a = a$, với $e\in G$
3. $a+(-a) = (-a)+a = e$
4. $a+b = b+a$ (có tính chất này sẽ là nhóm Abel)

Một số tính chất khác :
- Cấp của nhóm G chính là số phần tử của G
- Cấp của phần tử a trong nhóm G chính là số nguyên dương nhỏ nhất $t$ thỏa mãn $a^t = e$, trong đó e là phần tử đơn vị của G
- Kí hiệu cấp của nhóm G : $ord(G)$ hoặc $|G|$, cấp của phần tử là $ord(a)$ hoặc $|a|$

Ngoài ra ta cũng có **Định nghĩa nhóm cyclic** : G được gọi là **nhóm cyclic** nếu nó chứa một phần tử a sao cho mọi phần tử của G đều là lũy thừa nguyên nào đó của a, với a được gọi là **phần tử sinh** (hay phần tử nguyên thủy của nhóm G)
>Ví dụ : $a = 2$ $\Rightarrow$ $G = (2^1, 2^2, 2^3,...,2^n)$ với n là số nguyên.

## Định nghĩa Vành
Cho một tập $R \neq \emptyset$ và phép toán hai ngôi $(+,*)$ được gọi là 1 vành nếu :
- Với phép cộng, R là nhóm Abel
- Với phép nhân, có :
+ Tính kết hợp : $a.b.c = a.(b.c) = (a.b).c$
+ Tính phân phối với phép cộng :
+ $a.(b+c) = a.b + a.c$
+ $(b+c).a = b.a + c.a$
- 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ó 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**
>Ví dụ : Cho $Z_6 = (0,1,2,3,4,5)$. Ta nói $Z_6$ không phải là miền nguyên vì $(2.3) \mod(6) = 0$.

## Định nghĩa Trường
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 vành
- Với phép nhân $F \setminus \{0\}$ là nhóm Abel

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 như là cộng 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)
$$

$$
a \div b = a.b^{-1}
$$

# Số học Modulo
## Tính chia hết
- Chia số nguyên $a$ cho $n$ được thương là số nguyên $q$, tức $a=n.q$
- $a$ chia hết cho $n$, $n$ chia hết $a$ hay $a$ là bội số của $n$, $n$ là ước số của $a$ và kí hiệu là $n \mid a$
- 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.q + r, 0 < r < n $$

+ $q$ được gọi là thương, kí hiệu là $a \mid n$
+ $r$ được gọi là dư, kí hiệu là $a \mod n$
### Định nghĩa quan hệ đồng dư trên tập số nguyên
$a \equiv b \mod{n}$ khi và chỉ khi $a$ và $b$ có phần dư như nhau khi chia cho $n$.

Ví dụ :
$$
100 \mod 11 = 1
$$

$$
34 \mod 11 = 1
$$

$$
=> 100 \equiv 34 \mod{11}
$$

### Đạ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 \mod n, 0 \leq b \leq n
$$

>Ví dụ : $-12 \\mod(7) \equiv -5 mod(7) \equiv 2 mod(7) \equiv 9 mod(7) = 2$
Ta có thể thấy rằng các kết quả trên đều bằng $2$. Tuy nhiên trong 4 số $-12, -5, 2, 9$ thì ta sẽ chỉ lấy $2$ bởi vì : $-12, -5 < 0$ và $9 > 7$.

Hay ta có một bảng các lớp tương đương như sau :
<style>
table {
border-collapse: collapse;
width: auto;
}
th, td {
border: 1px solid black;
padding: 8px;
text-align: center;
}
.red {
color: red;
}
</style>

| -21 | -20 | -19 | -18 | -17 | -16 | -15 |
|------|------|------|------|------|------|------|
| -14 | -13 | -12 | -11 | -10 | -9 | -8 |
| -7 | -6 | -5 | -4 | -3 | -2 | -1 |
| <span class="red">0</span> | <span class="red">1</span> | <span class="red">2</span> | <span class="red">3</span> | <span class="red">4</span> | <span class="red">5</span> | <span class="red">6</span> |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |

>Trong đó : Các phần tử trong cùng một cột có cùng mối quan hệ đồng dư với nhau trong Modulo 7.

Tập hợp các đại diện của các số nguyên theo $mod(n)$ gồm **n** phần tử, khi đó ta có $Z_n = (0,1,2,...,n-1)$ (dòng màu đỏ). Hay có thể hiểu theo cách khác là các phần tử này là đại diện cho các phần tử khác đồng dư với nó trong $mod(n)$.

## Ước số và Ước chung lớn nhất
### Ước số
- Số $b$ không âm được gọi là ước số của $a$ nếu có số nguyên $m$ sao cho $a = m.b$, $a, b, m \in Z$. Hay ta có thể nói là a chia hết cho b.
- Kí hiệu : $b | a$.
>Ví dụ : $1,2,3,4,6,12$ là ước của $12$.

### Ước chung lớn nhất (GCD)
- $d$ được gọi là ước số chung của $a, b$ nếu : $d|b$, $d|a$
- $d$ được gọi là ước chung lớn nhất của $a, b$ nếu : $d>0$, $d$ là ước chung của $a, b$ và mọi ước số của $a, b$ là ước của $d$.
- Kí hiệu : $d = gcd(a, b)$
- Với mọi $a$ ta có : $gcd(a, 0) = a$ và $gcd(0, 0) = 0$.

Thuật toán tìm **Ước chung lớn nhất (GCD)** :

def gcd(a, b):
    while True: 
        a, b = b, a % b
        if b == 0:
            return a
            
print(gcd(15, 5)) #5


#hoặc nhanh hơn thì dùng hàm gcd của thư viện math
import math
print(math.gcd(15, 5)) 

## Các phép toán trên Modulo
Thực hiện phép toán trên các số nguyên cộng, trừ, nhân, chia rồi rút gọn lại bằng Modulo.

Có thể vừa tính toán vừa kết hợp với rút gọn Modulo tại bất kì thời điểm nào.

<div style="background-color: #E7F3FF; padding: 10px; border-radius: 5px;">
💡 <span style="color: #007bff;">Hãy nhớ rằng : Các số trong quá trình tính toán không được vượt quá Modulo N.</span>
</div>

Các tính chất :
$$
(a+b)\mod(N) = [amod(N) + bmod(N)] \mod(N)
$$

$$
(a.b)\mod(N) = [amod(N).bmod(N)] \mod(N)
$$

Như vậy khi thực hiện các phép tính toán ta có thể thay các số bằng các số tương đương theo Modulo N, hoặc đơn giản hơn là thay bằng các đại diện $Z_n = (0,1,2,...,n-1)$.

$Z_n$ với các phép toán theo Modulo N tạo thành vành giao hoán có đơn vị. Các tính chất kết hợp, giao hoán và nghịch đảo được suy ra từ các tính chất tương ứng của các số nguyên.
$$
(a+b) \equiv (a+c) \pmod{N} => b \equiv c \pmod{N}
$$

$$
(a.b) \equiv (a.c) \pmod{N} => b \equiv c \pmod{N}
$$
>Tính chất số 2 chỉ đúng khi $gcd(a, N) = 1$

Ví dụ : Tính $(11.19 + 10^{17}) \mod(7)$
$$
(11.19 + 10^{17}) \mod(7)
$$

$$
\Leftrightarrow (11mod(7).19mod(7) + (10mod(7))^{17}) \mod(7)
$$

$$
\Leftrightarrow (4.5 + 3^{17}) \mod(7)
$$

$$
\Leftrightarrow (20mod(7) + 3^{17}) \mod(7)
$$

$$
\Leftrightarrow (6 + 3^{17}) \mod(7)
$$

$$
\Leftrightarrow (6 + 3.3^{16}) \mod(7)
$$

$$
\Leftrightarrow (6 + 3.(3^2)^8 \mod(7)
$$

$$
\Leftrightarrow (6 + 3.(9mod(7))^8 \mod(7)
$$

$$
\Leftrightarrow (6 + 3.(2^4)^2) \mod(7)
$$

$$
\Leftrightarrow (6 + 3.(16mod(7))^2) \mod(7)
$$

$$
\Leftrightarrow (6 + 3.2^2) \mod(7)
$$

$$
\Leftrightarrow 18\mod(7) = 4
$$

## Thuật toán Euclid mở rộng (exGCD)
- Nếu $gcd(a, b) = d$ thì ta sẽ có một phương trình bậc nhất 2 ẩn $(x, y)$ có nghiệm nguyên là :
$$
a.x + b.y = gcd(a,b)
$$

- Nếu $gcd(a, b) = 1$ thì ta sẽ có :
+ **x** là nghịch đảo của a mod b, $x = a^{-1} \mod(b)$
+ **y** là nghịch đảo của b mod a, $y = b^{-1} \mod(a)$

Thuật toán exGCD :

def exGCD(a, b):
    def exGCD(a, b):
    if b == 0:
        return a, 1, 0  
    
    x1, y1 = 0, 1
    x2, y2 = 1, 0
    
    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
    
    return a, x2, y2  

print(exGCD(15, 6)) 
#gcd = 3, (x,y) = (1, -2)

## Số nguyên tố
- Số nguyên $a > 1$ gọi là số nguyên tố (prime number) nếu $a$ chỉ có 2 ước số là : $1$ và $a$.
- Hai số $a, b$ được gọi là **nguyên tố cùng nhau** nếu chúng không có ước chung nào khác ngoài 1, tức $gcd(a, b) = 1$.
>Ví dụ : $gcd(15, 8) = 1$
- Có thể nói, các 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.
>**Fact** : Số nguyên tố lớn nhất hiện nay mà con người tìm được là số nguyên tố Mersenne có dạng $2^{136279841}-1$.
- 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ố của một số $N$. Hay ta có định lý như sau :
<div style="background-color: #E7F3FF; padding: 10px; border-radius: 5px;">
💡 <span style="color: #007bff;">Định lý cơ bản của số học : Với mọi số nguyên N > 1, ta luôn phân tích được dưới dạng tích của lũy thừa số nguyên tố. </span>
</div>

$$
N = p_1^{e_1}.p_2^{e_2}...p_i^{e_i}
$$
>Trong đó : $p_i$ là các số nguyên tố nguyên tố khác nhau, $e_i \in N^{*}$ và phân tích trên là duy nhất.
- Việc phân tích một số thành tích các số khó hơn nhiều so với bài toán nhân các số để được tích.

## Định lý Fermat nhỏ
- Với a là số nguyên bất kì, p là số nguyên tố, $a<p$ và $gcd(a, p) = 1$ ta có :
$$
a^{p-1} \equiv 1 \pmod{p} => a^{p} \equiv a \pmod{p}
$$
>Ví dụ : $2^{7-1} \equiv 1 \pmod{7}$

## Hàm phi Euler
- Tập $Z_n = (0,1,2,...,n-1)$ thường được gọi là thặng dư đầy đủ theo Modulo N.
- Tập $Z_n^* = (a \in Z_n|gcd(a, n) = 1)$ được gọi là tập các thặng dư thu gọn theo Modulo N.
>Tức là : $Z_n$ là tập hợp các số tự nhiên từ 0 tới $n-1$, còn $Z_n^*$ là tập hợp các số tự nhiên $a<n$ sao cho $gcd(a, n) = 1$.

- Nếu $n=p$ là số nguyên tố thì $Z_p^* = (0,1,2,...,p-1)$
- Kí hiệu : $\phi(n)$ (hàm Euler) là số phần tử của tập $Z_n^*$
- Tính chất :
+ Nếu $p$ là số nguyên tố thì $\phi(p) = p-1$
+ Nếu $gcd(m, n) = 1$ thì $\phi(m.n) = \phi(m).\phi(n)$
+ Nếu $n = p_1^{e_1}.p_2^{e_2}...p_i^{e_i}$ thì :
$$
\phi(n) = n.(1-\frac{1}{p_1}).(1-\frac{1}{p_2})...(1-\frac{1}{p_i})
$$
>Ví dụ : $\phi(37) = 37 - 1 = 36$, $\phi(21) = 12$

## Định lý Euler
Định lý Euler là tổng quát hóa của định lý Fermat nhỏ với điều kiện $a<n$ và $gcd(a, n) = 1$ :
$$
a^{\phi(n)} \equiv 1 \pmod{n}
$$
>Ví dụ : $3^{\phi(10)} \mod(10) = 3^{\phi(2).\phi(5)}\mod(10) = 3^{1.4} \mod(10) = 1$

## Định nghĩa cấp của phần tử $Z_n^*$
- Nhóm nhân của $Z_n$ là $Z_n^* = (a \in Z_n|gcd(a, n) = 1)$
- Cấp của $Z_n^*$ là số phần tử của trong $Z_n^*$, kí hiệu $|Z_n^*| = \phi(n)$
- Nếu n là tích các số nguyên khác nhau và $r \equiv s \pmod{\phi(n)}$ thì: $a^r \equiv a^s \pmod{n}$

- Cấp của phần tử $a \in Z_n^*$ là số nguyên dương t nhỏ nhất thỏa : $a^t \equiv 1 \pmod{n}$. Kí hiệu : $ord(a) = t$
- Cho $a \in Z_n^*$, $ord(a) = t$, $a^s \equiv 1 \pmod{n}$, khi đó t là ước của s và $t|\phi(n)$.

>Ví dụ : Tính cấp của các phần tử trong $Z_{20}^*$
Ta có : $n=20 => \phi(n) = 8 = |Z_{20}^*|$, $a\in Z_{20}^* => a = (1,3,7,9,11,13,17,19)$

| a | 1 | 3 | 7 | 9 | 11 | 13 | 17 | 19 |
|------|------|------|------|------|------|------|------|------|
| ord(a) | 1 | 4 | 4 | 2 | 2 | 4 | 4 | 2 |

## Định nghĩa phần tử sinh
$a \in Z_{n}^*$ là phần tử sinh nếu :
$$
Z_{n}^* = (a^i \mod(n) |0 \leq i \leq \phi(n)-1)
$$

- Nếu $ord(a) = \phi(n)$ thì **a** được gọi là phần tử sinh của $Z_{n}^*$, hay còn gọi là phần tử nguyên thủy. Và nếu $Z_{n}^*$ có phần tử sinh thì $Z_{n}^*$ được gọi là nhóm cyclic.

- $Z_{n}^*$ có phần tử sinh khi và chỉ khi $n = 2, 4, p^k, 2.p^k$.
>Từ tính chất trên có thể suy ra $Z_{20}^*$ không phải là nhóm cyclic vì $Z_{20}^*$ không có phần tử sinh vì max $ord(a) = 4 \neq 8$.

- Giả sử **a** là một phần tử sinh của $Z_{n}^*$. Khi đó, $b = a^i mod n$ cũng là phần tử sinh của $Z_{n}^*$ nếu $gcd(i, \phi(n)) = 1$
- Nếu $Z_{n}^*$ là nhóm cyclic thì số phần tử sinh là :
$$
\phi(\phi(n))
$$
- Sở dĩ có được điều đó là vì :
+ $\phi(n)$ là các phần tử nguyên tố cùng nhau với $n$
+ $\phi(\phi(n))$ là các phần tử nguyên tố cùng nhau với $\phi(n)$.
+ Mà ta có $gcd(i, \phi(n)) = 1$ và $gcd(\phi(\phi(n)), \phi(n)) = 1$ => $\phi(\phi(n)) = i$. Có bao nhiêu i thì có bấy nhiêu phần tử sinh thuộc $Z_{n}^*$.

- Với $a\in Z_{n}^*$ là phần tử sinh của $Z_{n}^*$ khi :
$$
a^{\frac{\varphi(n)}{p_i}} \not\equiv 1 \pmod{n}
$$
>với $p_i$ là ước số nguyên tố của $\phi(n)$

Ví dụ : Cho $Z_{25}^*$ là nhóm cyclic có phần tử sinh $a=2$. Tìm các phần tử sinh còn lại.
Các số nguyên tố cùng nhau với $\phi(25) = 20$ là : $i = (1,3,7,9,11,13,17,19)$
=> $b_1 = 2^1 \mod(25) = 2$, $b_2 = 2^3 \mod(25) = 8$,...
=> Các phần tử sinh còn lại là : $b = (2,3,8,12,13,17,22,23)$

## Định lý phần dư Trung Hoa (CRT)
Cho $n_1, n_2,..., n_i$ nguyên tố cùng nhau từng đôi một $gcd(n_i, n_j) = 1, \forall i \neq j$ thì hệ sau có nghiệm duy nhất với Modulo $N = \prod_{i=1}^{k} n_i$ :
$$
\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\quad \vdots \\
x \equiv a_k \pmod{m_k}
\end{cases}
$$

Nghiệm **x** của hệ được tính như sau :
$$
x=\sum_{i=1}^{k} a_i.N_i.M_i \mod(N)
$$
>Trong đó : $N = \prod_{i=1}^{k} n_i$, $N_i = \frac{N}{n_i}$, $M_i = N_i^{-1} \mod(n_i)$

Ví dụ : Giải hệ phương trình
$$
\begin{cases}
x \equiv 7 \pmod{9} \\
x \equiv 4 \pmod{10} \\
x \equiv 15 \pmod{23}
\end{cases}
$$

Có :
- $N = 9.10.23 = 2070$
- $(N_1, M_1) = (230, 2)$
- $(N_2, M_2) = (207, 3)$
- $(N_3, M_3) = (90, 11)$
$$
x = (7.230.2 + 4.207.3 + 15.90.11) \mod(2070)
$$

$$
\Leftrightarrow x=20554 \mod(2070) \equiv 1924 \mod(2070)
$$

Vậy nghiệm của ta có dạng là : $x \equiv 1924 \mod(2070)$.

## Đị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 \mod(N)
$$
- Nếu không tồn tại $x$ như vậy thì người ta nói a là **bất thặng dư bậc hai** theo Modulo N.
- Tập hợp của tất cả thặng dư được kí hiệu là : $Q_n$
- Ngược lại là : $\bar{Q_n}$

Từ đây ta sẽ có định lý và hệ quả sau :
- **Định lý** : Cho $p$ là số nguyên tố lẻ và $a$ là phần tử sinh của $Z_{p}^*$. Khi đó $b \in Z_{n}^*$ là thặng dư bậc hai theo Modulo p nếu :
$$
b \equiv a^i \mod(p), i = 2k
$$

- **Hệ quả** :
$$
|Q_p| = |\bar{Q_n}| = \frac{p-1}{2}
$$
>Ví dụ : Cho $a=3$ là phần tử sinh của $Z_{17}^*$. Khi đó :
$|Q_p| = |\bar{Q_n}| = \frac{17-1}{2} = 8$ và
$=> |Q_{17}| = (3^2mod(17), 3^4mod(17)),...) = (9,13,15,16,8,4,2,1)$
$=> |\bar{Q_{17}}| = (3^1mod(17), 3^3mod(17)),...) = (3,10,5,11,14,7,12,6)$

Cho $n=p.q$ với $p,q$ là 2 số nguyên tố ($p\neq q$). Khi đó $a \in Z_{n}^*$ là thặng dư bậc hai theo Modulo n khi và chỉ khi : $a \in Q_p$ và $a \in Q_q$.

Từ đó ta có :
$$
|Q_n| = \frac{(p-1).(q-1)}{4}
$$

$$
|\bar{Q_p}| = \frac{3.(p-1).(q-1)}{4}
$$

## Định lý 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 $x^2 \equiv a \mod(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 của một số Modulo N
Cho $n = p_1^{e_1}.p_2^{e_2}...p_i^{e_i}$, với $p_i$ là số nguyên tố lẻ phân biệt và $e_i \in N^*$. Nếu $a \in Q_n$ thì có đúng $2^i$ căn bậc hai theo Modulo n.
>Ví dụ : Tìm các căn bậc hai của $4\mod15$
Ta có : $15 = 3.5 =>$ có $2^2$ căn bậc hai có thể
$=> x = (2,7,8,13)$ là các căn bậc hai của $4\mod15$

## Kí hiệu Legendre và Jacobi
Cho $p$ là số nguyên tố lẻ, $a$ là số nguyên. Kí hiệu **Legendre** được xác định như sau :
$$
\left( \frac{a}{p} \right) =
\begin{cases}
1, & \text{nếu } a \text{ là số dư bậc hai theo modulo } p, \text{ tức là tồn tại } x \text{ sao cho } x^2 \equiv a \pmod{p} \\
-1, & \text{nếu } a \text{ không là số dư bậc hai theo modulo } p \\
0, & \text{nếu } a \equiv 0 \pmod{p}
\end{cases}
$$

Cho $n \geq 3$ là các số nguyên lẻ và có phân tích : $n = p_1^{e_1}.p_2^{e_2}...p_i^{e_i}$. Khi đó ta có kí hiệu **Jacobi** như sau :
$$
\left( \frac{a}{n} \right) = \left( \frac{a}{p_1} \right)^{e_1}. \left( \frac{a}{p_2} \right)^{e_2}... \left( \frac{a}{p_i} \right)^{e_i}
$$
<div style="background-color: #E7F3FF; padding: 10px; border-radius: 5px;">
💡 <span style="color: #007bff;">Vì vậy khi n là số nguyên tố thì kí hiệu Jacobi chính là kí hiệu Legendre. </span>
</div>

**Cách tính kí hiệu Legendre :**
$$
(\frac{a}{p}) \equiv a^{\frac{p-1}{2}} \mod p
$$
**Các tính chất quan trọng :**
- Nếu n là số nguyên lẻ và $m_1 \equiv m_2 \mod(n)$ thì :
$$
\left( \frac{m_1}{n} \right) \equiv \left( \frac{m_2}{n} \right)
$$
- Nếu n là số nguyên lẻ thì :
$$
\left( \frac{m_1.m_2}{n} \right) \equiv \left( \frac{m_1}{n} \right).\left( \frac{m_2}{n} \right)
$$

$$
\left( \frac{2}{n} \right) =
\begin{cases}
1, \text{ nếu } n \equiv \pm1\mod(8)\\
-1, \text{ nếu } n \equiv \pm3\mod(8)\\
\end{cases}
$$

- Nếu $m = 2^k.t$ (t là số lẻ) thì :
$$
\left( \frac{m}{n} \right) = \left( \frac{2}{n} \right)^{k}. \left( \frac{t}{n} \right)
$$

- Nếu $m,n$ là số nguyên lẻ thì :
$$
\left( \frac{m}{n} \right) =
\begin{cases}
-(\frac{n}{m}), \text{ nếu cả } m,n \equiv \pm3\mod(4)\\
(\frac{n}{m}), \text{ trường hợp còn lại }
\end{cases}
$$
>Ví dụ : Tính $(\frac{7411}{9283})$
Code :

def legendre(a, p):
    if p <= 1 or p % 2 == 0:
        raise ValueError("p must be an odd positive prime number")
    if a % p == 0:
        return 0
    return pow(a, (p - 1) // 2, p) if pow(a, (p - 1) // 2, p) == 1 else -1

a = 7411
p = 9283
print("Legendre (a/p) =", legendre(a, p))
# Legendre (7411/9283) = -1

## Số nguyên Blum
Là một hợp số có dạng $n=p.q$ với $p,q$ là các số nguyên tố khác nhau thỏa mãn :
$$
\begin{cases}
p \equiv 3 \mod(4) \\
q \equiv 3 \mod(4)
\end{cases}
$$

Cho $a \in Q_n$. Khi đó $a$ có đúng 4 căn bậc hai theo modulo n và chỉ có 1 trong 4 căn bậc hai nằm trong $Q_n$. Khi này, 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ụ : Cho $n=21, Q_{21} = (1,4,16)$
- 4 căn bậc hai của $1 \mod 21$ là : $(1,8,13,20)$ có $1 \in Q_{21}$
- 4 căn bậc hai của $4 \mod 21$ là : $(2,5,16,19)$ có $16\in Q_{21}$
- 4 căn bậc hai của $16 \mod 21$ là : $(4,10,11,17)$ có $4\in Q_{21}$

## Bài toán logarit rời rạc
- Cho $g$ là phần tử sinh của nhóm nhân $Z_{p}^*$, với $a \in Z_{p}^*, a\neq0$ bất kì ta có tìm được một số nguyên $x$ duy nhất thỏa mãn :
$$
a \equiv g^x \mod(p)
$$

$$
\Leftrightarrow x = \log_g a \mod(p)
$$

Ví dụ : Tìm $x$ thỏa : $2^x \equiv 8 \mod(19)$
- Ta có : $2^1 \mod(19) = 2$, $2^2 \mod(19) = 4$, $2^3 \mod(19) = 8$
- Như vậy ta có : $2^x \equiv 8 \mod(19) \Leftrightarrow x \equiv \log_2 8 \mod(19) \equiv 3 \mod(19)$

### Thuật toán tính logarit rời rạc : Baby-step Giant-step Algorithm (BSGS)
Cho $a$ là phần tử sinh của $Z_n^*$, $b$ là số nguyên dương bất kì, tính $log_a b$.
- Tính $m = \lceil \sqrt{ord(a)} \rceil = \lceil \sqrt{\phi(n)} \rceil$
- Lập bảng $(j, a^j \mod(n))$ với $0 \leq j \leq m-1$
- Lập bảng $(i, b.(a^{-m})^i) \mod(n)$ với $0 \leq i \leq m-1$
- Tra bảng tìm cặp $(i,j)$ thỏa $a^j \mod(n) = b.(a^{-m})^i \mod(n)$
- Khi đó, $log_a b = m.i + j$
>Ví dụ : Tính $log_{17} 15$ trên $Z_{97}^*$

import math
def baby_step_giant_step(a, b, n):
    m = math.isqrt(n) + 1  
    table_j = {pow(a, j, n): j for j in range(m)}
    a_inv = pow(a, -m, n)  
    gamma = b
    
    for i in range(m):
        if gamma in table_j:  
            j = table_j[gamma]
            return i * m + j  
        gamma = (gamma * a_inv) % n  
    
    return None

a = 17  
b = 15   
n = 97      
log = baby_step_giant_step(a, b, n)
print(log)
# 31

# Mathematics - Challenges CryptoHack
Ngoài các lý thuyết về toán nói trên, ta có thể làm một số các bài tập liên quan đến chủ đề này trong CryptoHack, phần Mathematics.