Chapter 2hffhhhhhhhhhhhhhhhhhhhhhhhh.pdf

sdfbs

1. Hoang Dac Thang, IOIT - VAST 1
An toàn thông tin
Chương 2: Cơ sở toán học

2. Hoang Dac Thang, IOIT - VAST 2
Chương 2: Cơ sở toán học
2.1 Quan hệ đồng dư
2.2 Thuật toán Euclide mở rộng và phép toán nghịch đảo
2.3 Hàm số Euler
2.4 Một số định lý số học cơ bản
2.5 Thuật toán bình phương và nhân liên tiếp
2.6 Độ phức tạp tính toán

3. Hoang Dac Thang, IOIT - VAST 3
2.1 Quan hệ đồng dư
•Tập hợp các số nguyên, Z = {…, -2, -1, 0, 1, 2,…}
•Tập hợp các số nguyên không âm, Z
+
= {0, 1, 2,…}

4. Hoang Dac Thang, IOIT - VAST 4
2.1 Quan hệ đồng dư
1. Định nghĩa Modulo
•Modulo là một phép tính số học thu gọn tất cả các số về một trong
các số trong tập cố định [0, 1, 2, … n-1] với một số n cho trước.
•Bất kỳ một số nào nằm ngoài dải này đều được thu gọn vào trong
giải này bằng cách lấy số dư trong phép chia cho n.

5. Hoang Dac Thang, IOIT - VAST 5
2.1 Quan hệ đồng dư
1. Định nghĩa Modulo
•Cho hai số nguyên bất kỳ a và b (với b ≠ 0).
•Thực hiện phép chia a cho b ta sẽ được hai số q và r sao cho:
a = b.q + r, 0 ≤ r < b.
•Số q được gọi là số thương của phép chia a cho b, ký hiệu a div b
•Số r được gọi là số dư của phép chia a cho b, ký hiệu a mod b.

6. Hoang Dac Thang, IOIT - VAST 6
1. Định nghĩa Modulo
Ví dụ:
➢10 div 3 = 3 và 10 mod  3 = 1, vì 10 = 3.3 + 1,
➢15 div 4 = 3 và 15 mod 4 = 3, vì 15 = 4.3 + 3,
➢-25 div 7 = -4 và -25 mod 7 = 3 vì -25 = 7.(-4) + 3.

7. Hoang Dac Thang, IOIT - VAST 7
1. Định nghĩa Modulo
Cho hai số nguyên a và b, và một số nguyên dương n.
Ta nói rằng a và b đồng dư với nhau theo modulo n,
và viết a ≡ b(modn), nếu hiệu của chúng chia hết cho n, hay khi
chia a và b cho n ta được cùng một số dư như nhau.

8. Hoang Dac Thang, IOIT - VAST 8
1. Định nghĩa Modulo
Ví dụ:
•17 ≡ 5(mod6), vì 17 – 5 = 12 chia hết cho 6 hay 17 mod 6 = 5,
và 5 mod 6 = 5. Vậy 17 và 5 là đồng dư với nhau theo modulo 6.
•23 ≡ 8(mod5), vì 23 – 8 = 15 chia hết cho 5. Vậy 23 và 8 là đồng
dư với nhau theo modulo 5.
•-19 ≡ 9(mod7), vì –19 - 9 = -28 chia hết cho 7. Vậy -19 và 9 là
đồng dư với nhau theo modulo 7.

9. Hoang Dac Thang, IOIT - VAST 9
Tính chất của đồng dư
•Tính phản xạ: Với mọi số nguyên a, ta luôn có a ≡ a(modn).
Một số luôn đồng dư với chính nó theo modulo n.
•Tính đối xứng: Nếu a ≡ b(modn) thì b ≡ a(modn).
Nếu a đồng dư với b theo modulo n, thì b cũng đồng dư với a theo modulo n.
•Tính bắc cầu: Nếu a ≡ b(modn) và b ≡ c(modn), thì a ≡ c(modn).
Nếu a đồng dư với b, và b đồng dư với c, thì a cũng đồng dư với c theo
modulo n.

10. Hoang Dac Thang, IOIT - VAST 10
Lớp tương đương
•Quan hệ đồng dư tạo ra một phân hoạch trên Z thành các lớp tương đương.
•Lớp tương đương của một số nguyên a theo modulo n bao gồm tất cả các số
nguyên b sao cho b ≡ a(modn).
•Nói cách khác, các số a và b thuộc cùng một lớp tương đương khi và chỉ khi
chúng cho cùng một số dư khi chia cho n.

11. Hoang Dac Thang, IOIT - VAST 11
Lớp tương đương
Ví dụ: Với n = 3, Z sẽ được phân hoạch thành ba lớp tương đương:
➢Lớp tương đương của 0 (gồm các số có dạng 0, ±3, ±6, …)
➢Lớp tương đương của 1 (gồm các số có dạng 1, 4, 7,…, -2, -5, -8,…)
➢Lớp tương đương của 2 (gồm các số có dạng 2, 5, 8,…, -1, -4, -7,…)
Mỗi lớp tương đương có thể được biểu diễn bằng số dư khi chia cho n

12. Hoang Dac Thang, IOIT - VAST 12
2. Các phép toán số học trên Modulo
•Phép cộng modulo
•Phép trừ modulo
•Phép nhân modulo

13. Hoang Dac Thang, IOIT - VAST 13
Phép cộng Modulo
Cho hai số nguyên a và b và một modulo n, phép cộng modulo được định
nghĩa là:
(a + b) mod n = (a mod n + b mod n) mod n
Ví dụ: (29 + 12) mod 7 = (29 mod 7 + 12 mod 7) mod 7 = (1 + 5) mod 7 = 6
Tính chất:
•Giao hoán: (a + b) mod  n = (b + a) mod n
•Kết hợp: ((a + b) + c) mod  n = (a + (b + c)) mod n = (b + (a + c)) mod n
•Phần tử trung hòa: (a + 0) mod  n = a mod  n

14. Hoang Dac Thang, IOIT - VAST 14
Phép trừ Modulo
Cho hai số nguyên a và b và một modulo n, phép trừ modulo được
định nghĩa là:
(a - b) mod n = (a mod n - b mod n) mod n
Ví dụ:
(29 - 12) mod 7 = (29 mod 7 - 12 mod 7) mod 7 = (1 - 5) mod 7 = 3

Tính chất:
•Giao hoán: (a - b) mod  n = -(b - a) mod n
•Kết hợp: ((a - b) - c) mod  n = (a - (b + c)) mod n

15. Hoang Dac Thang, IOIT - VAST 15
Phép nhân Modulo
Cho hai số nguyên a và b và một modulo n,
phép nhân modulo được định nghĩa là:
(a x b) mod n = (a mod n x b mod n) mod n
Ví dụ: (29 x 12) mod 7 = (29 mod 7 x 12 mod 7) mod 7 = (1 x 5) mod 7 = 5
Tính chất:
•Giao hoán: (a x b) mod  n = (b x a) mod n
•Kết hợp: ((a x b) x c) mod  n = (a x (b x c)) mod n = ((a x c) x b) mod n
•Phần tử trung hòa: a x 1 mod n = a mod n

16. Hoang Dac Thang, IOIT - VAST 16
2.2 Thuật toán Euclide mở rộng
Ước số
Số nguyên b không âm được gọi là ước số của a, nếu có số m sao cho: a = mb
trong đó a, b, m đều nguyên.
Khi a chia hết cho b, ta ký hiệu là b|a.
Ví dụ: 1, 2, 3, 5, 6, 10, 15, 30 là ước số của 30

17. Hoang Dac Thang, IOIT - VAST 17
Ước số chung lớn nhất
Ước chung lớn nhất (UCLN), hay còn gọi là GCD (greatest common divisor),
của hai hoặc nhiều số nguyên là số lớn nhất chia hết cho tất cả các số đó.

Cho hai số nguyên dương a và b, ta ký hiệu GCD(a, b) là ước số chung lớn
nhất của a và b, tức là số nguyên dương vừa là ước của a vừa là ước của b và
là số nguyên dương lớn nhất có tính chất đó.

18. Hoang Dac Thang, IOIT - VAST 18
Ước số chung lớn nhất
Cách tìm ước chung lớn nhất (UCLN): Có 03 phương pháp phổ biến sau:
(i)Phương pháp liệt kê ước chung
(ii) Phương pháp phân tích ra thừa số nguyên tố
(iii) Phương pháp Euclid

19. Hoang Dac Thang, IOIT - VAST 19
Cách tìm ước chung lớn nhất (UCLN)
(i)Phương pháp liệt kê ước chung
•Bước 1: Liệt kê tất cả các ước của từng số.
•Bước 2: Tìm các ước chung của các số.
•Bước 3: Chọn ước lớn nhất trong các ước chung đó.
Ví dụ: Tìm UCLN của 24 và 36:
oƯớc của 24: 1, 2, 3, 4, 6, 8, 12, 24.
oƯớc của 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.
oƯớc chung: 1, 2, 3, 4, 6, 12.
Vậy UCLN: 12.

20. Hoang Dac Thang, IOIT - VAST 20
Cách tìm ước chung lớn nhất (UCLN)
(ii) Phương pháp phân tích ra thừa số nguyên tố:
•Bước 1: Phân tích các số cần tìm UCLN thành thừa số nguyên tố.
•Bước 2: Chọn các thừa số chung với số mũ nhỏ nhất.
•Bước 3: Nhân các thừa số chung lại với nhau để được UCLN.
Ví dụ: Tìm UCLN của 24 và 36:
o24 = 2³ × 3.
o36 = 2² × 3².
Vậy UCLN: 2² × 3 = 12.

21. Hoang Dac Thang, IOIT - VAST 21
Cách tìm ước chung lớn nhất (UCLN)
(iii) Phương pháp Euclid:
Cho số nguyên không âm a và số nguyên dương b thì
gcd(a, b) = gcd(b, a mod b)
Ví dụ:
gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6
gcd(11, 10) = gcd(10, 1) = gcd(1, 0) = 1

22. Hoang Dac Thang, IOIT - VAST 22
Cách tìm ước chung lớn nhất (UCLN)
(iii) Phương pháp Euclid:
•Bước 1: Chia số lớn cho số nhỏ hơn.
•Bước 2: Lấy số dư của phép chia trước làm số chia tiếp theo, số chia trước
làm số bị chia.
•Bước 3: Lặp lại quá trình cho đến khi số dư là 0. Số chia cuối cùng là
UCLN.
Ví dụ: Tìm UCLN của 24 và 36:
o36 ÷ 24 = 1 dư 12.
o24 ÷ 12 = 2 dư 0.
Vậy UCLN: 12.

23. Hoang Dac Thang, IOIT - VAST 23
Thuật toán Euclide tìm ước số chung lớn nhất
Input: Hai số nguyên không âm a và b, với a ≥ b
Output: Ước số chung lớn nhất của a và b
While (b > 0)
{
r = a mod b
a = b
b = r
}
return a

24. Hoang Dac Thang, IOIT - VAST 24
Thuật toán Euclide tìm ước số chung lớn nhất

25. Hoang Dac Thang, IOIT - VAST 25
Thuật toán Euclide tìm ước số chung lớn nhất
Ví dụ: Dùng thuật toán Euclide tìm GCD(225, 35), ta lần lượt được các giá trị
gán cho các biến a, b và r như sau:
Vậy thuật toán cho ta kết quả: GCD(225, 35) = 5
a b r a = m.b + r
225 35 15 225 = 6.35 + 15
35 15 5 35 = 2.15 + 5
15 5 0 15 = 3.5 + 0
5 0

26. Hoang Dac Thang, IOIT - VAST 26
Thuật toán Euclide mở rộng
Ta biết 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ể tìm
được bởi thuật toán Euclide mở rộng

27. Hoang Dac Thang, IOIT - VAST 27
Input: Hai số nguyên không âm a và b với a ≥ b
Output: d = GCD(a, b) và hai số x, y sao cho a.x + b.y = d.
If ( b = 0)
{
d = a, x = 1, y = 0
return (d, x, y)
}
x2 = 1, x1 = 0, y2 = 0, y1 = 1
While (b > 0 )
{
q = a div b
r = a mod b
x = x2 – qx1
y = y2 – qy1
a = b, b = r
x2 = x1, x1 = x
y2 = y1, y1 = y
}
d = a, x = x2, y = y2
Return (d, x, y)

28. 28
Tìm GCD của a = 225 và b = 35 và các hệ số x và y sao cho: 225x + 35y = d
Bước 1: Áp dụng thuật toán Euclide để tìm GCD
(i) Tính toán:
225 = 35 x 6 +15
35 = 15 x 2 + 5
15 = 5 x 3 + 0
(ii) Ước số chung lớn nhất:
GCD(225, 35) = 5

29. 29
Bước 2: Áp dụng ngược lại để tìm hệ số x và y
Dựa vào phương trình ở trên:
Từ 15 = 225 – 35 x 6 ta có: 5 = 35 −15 × 2
Thay thế 15 từ phương trình đầu vào:
5 = 35 – 2 × (225 – 35 × 6)
(iii) Mở rộng và đơn giản hóa phương trình:
5 = 35 – 2 × 225 + 2 x 35 x 6
(iv) Kết hợp các hệ số:
5 = 225 × (−2) + 35× (1 + 12)
5 = 225 × (−2) + 35 × 13
Kết quả:
GCD(225, 35) = 5
Các hệ số tìm được là x = −2 và y = 13
Vậy 225 x (−2) + 35 x (13) = 5.

30. Hoang Dac Thang, IOIT - VAST 30
Số nguyên tố
• Số nguyên tố là một số nguyên dương lớn hơn 1 và chỉ có hai ước
số là 1 và chính nó.
• Nói cách khác, số nguyên tố không thể chia hết cho bất kỳ số
nguyên dương nào khác ngoài 1 và chính nó.
•Ví dụ: Các số nguyên tố nhỏ hơn 200 là
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, …

31. Hoang Dac Thang, IOIT - VAST 31
Đặc điểm của số nguyên tố
•2 là số nguyên tố chẵn duy nhất. Tất cả các số nguyên tố khác đều
là số lẻ.
•Số nguyên tố không có ước số bất kỳ nào khác ngoài 1 và chính
nó.
•Có vô số số nguyên tố.

32. Hoang Dac Thang, IOIT - VAST 32
Phân tích ra thừa số nguyên tố
•Một trong những bài toán cơ bản của số học là phân tích số a ra
thừa số nguyên tố, tức là viết nó dưới dạng tích của lũy thừa các
số nguyên tố.
•Ví dụ: 33 = 3×11; 3600=2
4
× 3
2
× 5
2

33. Hoang Dac Thang, IOIT - VAST 33
Các số nguyên tố cùng nhau
•Hai số nguyên dương a và b không có ước chung nào ngoài 1,
được gọi là nguyên tố cùng nhau.
•Ví dụ: 8 và 15 là nguyên tố cùng nhau, vì
ước của 8 là 1, 2, 4, 8.
ước của 15 là 1, 3, 5, 15.
Chỉ có 1 là ước chung của 8 và 15.

34. Hoang Dac Thang, IOIT - VAST 34
Các số nguyên tố cùng nhau
•Hai số nguyên tố cùng nhau có UCLN là 1.
•GCD(a, b) = 1
•Ví dụ: GCD(8, 15) = 1, → 8 và 15 là hai số nguyên tố cùng nhau

35. Hoang Dac Thang, IOIT - VAST 35
2. Phép toán nghịch đảo Modulo
•Giả sử ta có hai số nguyên a và n, với n là số modulo
•Nghịch đảo modulo được ký hiệu a
-1
mod n.
•Phép toán nghịch đảo của a theo modulo n là số nguyên x sao cho:
(a.x) mod n = 1 hay a.x ≡ 1 (mod n).
•Nói cách khác, x là số mà khi nhân với a, ta được 1 theo modulo n.

36. Hoang Dac Thang, IOIT - VAST 36
2. Phép toán nghịch đảo Modulo
Điều kiện tồn tại nghịch đảo Modulo
Phép toán nghịch đảo Modulo chỉ tồn tại khi a và n là hai số nguyên tố cùng
nhau, tức là GCD(a, n) = 1. Điều này có nghĩa là a và n không có bất kỳ ước
chung nào ngoài 1.

37. Hoang Dac Thang, IOIT - VAST 37
Tìm nghịch đảo Modulo
•Để tìm nghịch đảo Modulo của a Modulo n, ta có thể sử dụng Thuật toán
Euclide mở rộng.
•Tìm các hệ số x và y sao cho: a.x + n.y = GCD(a, n).
•Nếu GCD(a, n) = 1, thì x chính là nghịch đảo Modulo của a modulo n.

38. Hoang Dac Thang, IOIT - VAST 38
Ví dụ: Tìm nghịch đảo của a = 3 modulo n = 11 (3
-1
mod 11 = ?)
Bước 1: Áp dụng Thuật toán Euclide để tìm GCD:
11 = 3 x 3 +2
3 = 2 x 1 + 1
2 = 1 x 2 + 0
Vậy GCD(3, 11) = 1
Bước 2: Sử dụng các phương trình trên, tính toán ngược lại để tìm x:
1 = 3 − 2 × 1
1 = 3 – (11 - 3 × 3)
1 = 3 × 4 – 11 × 1
Do đó, nghịch đảo modulo của 3 modulo 11 là x = 4, tức là 3 × 4 ≡ 1(mod11).

39. 39
Phép chiatheo modulo
•Từ khái niệmsố nghịch đảochúng ta sẽ định nghĩaphép chiatheo modulo.
•Khi tính: (a / b) mod n,
Nếu b|a thì tính bình thường.
Trường hợp ngược lại, ta sẽ định nghĩa: (a / b) mod n = (a * b
-1
) mod n.

•Ví dụ: 7/2 = (7 * 2
-1
) mod 5 = 7 * 3 = 21 mod 5 = 1.

40. 40

41. Hoang Dac Thang, IOIT - VAST 41
2.3 Hàm phi Euler
Định nghĩa:
Hàm phi Euler ∅(n) của một số nguyên dương n là số lượng các số
nguyên dương nhỏ hơn hoặc bằng n mà nguyên tố cùng nhau với n
(tức là các số nguyên k sao cho gcd(k, n)=1).
Ví dụ:
•Nếu n = 1 thì ∅(1) = 1 vì 1 là nguyên tố cùng nhau với chính nó
•Nếu n = 8 thì các số nguyên dương nhỏ hơn hoặc bằng 8 mà
nguyên tố cùng nhau với 8 là 1, 3, 5, 7. Do đó ∅(8) = 4

42. Hoang Dac Thang, IOIT - VAST 42
2. Hàm phi Euler

43. Hoang Dac Thang, IOIT - VAST 43
Tính chất của Hàm phi Euler
•Nếu n = p x q thì: ∅(n) = ∅(p x q) =∅(p) x ∅(q)
Ví dụ: ∅(5x7) = ∅(5) x ∅(7)
•Nếu p là một số nguyên tố, thì: ∅(p) = p - 1
Ví dụ: ∅(7) = 7 – 1 = 6, vậy ∅(7) = 6
•Nếu p là một số nguyên tố và k là một số nguyên dương, thì:
∅(??????
??????
)=??????
??????
− ??????
??????−1
Ví dụ: ∅(7
3
) = 7
3
– 7
2
= 294
•Nếu n là hợp số thì phân tích thành số thừa số nguyên tố
∅(12) = ∅(2
2
x3) = ∅(2
2
)x∅(3) = (2
2
– 2)x(3 -1 ) = 2x2 = 4, vậy ∅(12) = 4

44. Hoang Dac Thang, IOIT - VAST 44
Ứng dụng của Hàm phi Euler
•Hàm phi Euler đóng vai trò quan trọng trong mật mã và xác thực.
•Ví dụ: RSA sử dụng hai số nguyên tố lớn và tính ∅(n) của tích của
chúng. Bảo mật của RSA dựa trên việc tính toán hàm phi Euler
cho một số n lớn.

45. Hoang Dac Thang, IOIT - VAST 45
2.4 Một số định lý số học cơ bản
1. Định lý Fermat nhỏ
Giả sử p là số nguyên tố và a là số nguyên bất kỳ sao cho a và p là
nguyên tố cùng nhau (tức là gcd(a, p) = 1). Khi đó, định lý Fermat
nhỏ khẳng định rằng:
a
p-1
mod p = 1
Nói cách khác, lũy thừa của a với số mũ p - 1 chia cho p sẽ luôn có
phần dư là 1.

46. Hoang Dac Thang, IOIT - VAST 46
1. Định lý Fermat nhỏ
Ví dụ:
•Nếu p = 7 và a = 3 vì gcd(3, 7) = 1,
theo định lý fermat nhỏ: 3
7-1
mod 7 = 1
Thực tế, 3
7-1
= 3
6
= 729, và 729 mod 7 = 1

•Nếu p = 11 và a = 2 vì gcd(2, 11) = 1,
theo định lý fermat nhỏ: 2
11-1
mod 11 = 1
Thực tế, 2
11-1
= 2
10
= 1024, và 1024 mod 11 = 1

47. Hoang Dac Thang, IOIT - VAST 47
1. Định lý Fermat nhỏ
Phiên bản mở rộng của định lý
•Nếu p là một số nguyên tố và a là một số nguyên dương bất kỳ
(không cần nguyên tố cùng nhau với p), thì: a
p
≡ a (mod p).
•Ví dụ: Nếu p = 5 và a = 10, thì 10
5
≡ 10 (mod 5)
vì 10
5
= 100000, và 100000 mod 5 = 10 mod 5 = 0.

48. Hoang Dac Thang, IOIT - VAST 48
1. Định lý Fermat nhỏ
Ứng dụng của định lý Fermat
•Định lý Fermat nhỏ là một công cụ quan trọng trong các thuật toán
mật mã, đặc biệt trong RSA và hệ thống mã hóa công khai.
•Định lý Fermat cũng được sử dụng để kiểm tra tính nguyên tố của
một số, như trong thuật toán kiểm tra nguyên tố Fermat.

49. Hoang Dac Thang, IOIT - VAST 49
2. Định lý Euler
•Định lý Euler: Nếu n là một số nguyên dương và a là một số
nguyên sao cho gcd(a, n) = 1, thì: ??????
∅(&#3627408475;)
mod n = 1,
trong đó ∅(n) là hàm Euler của n.
•Định lý Fermat nhỏ chính là trường hợp đặc biệt của định lý Euler
khi n = p là số nguyên tố ∅(p) = p -1.

50. Hoang Dac Thang, IOIT - VAST 50
2. Định lý Euler
•Định lý Euler: ??????
∅(&#3627408475;)
mod n = 1
•Ví dụ:
a = 3, n = 10, ∅(10) = 4; vì vậy 3
4
mod 10 = 1
a = 2, n = 11, ∅(11) = 10; vì vậy 2
10
mod 11 = 1

51. Hoang Dac Thang, IOIT - VAST 51
2. Định lý Euler
•Cho các số nguyên dương a, n, m bất kỳ, áp dụng tính chất của
phép nhân modulo và định lý Euler ta luôn có:
a
m
mod n = (a mod n)
(&#3627408474; &#3627408474;&#3627408476;?????? ∅&#3627408475;)
mod n
•Ví dụ:
65
18
mod 20 = (65 mod 20)
(18 &#3627408474;&#3627408476;?????? ∅20)
mod 20
= 5
(18 mod 8)
mod 20 = 5
2
mod 20 = 5

52. Hoang Dac Thang, IOIT - VAST 52
3. Định lý phần dư Trung hoa
•Các phép toán trên modulo các số nhỏ tính nhanh hơn nhiều so với
các số lớn.
•Nếu số lớn phân tích được thành tích của các số nhỏ, từng cặp
nguyên tố cùng nhau, thì ta sẽ có cách tính hiệu quả nhờ vào định
lý phần dư Trung Hoa.

53. Hoang Dac Thang, IOIT - VAST 53
3. Định lý phần dư Trung hoa
Triển khai định lý này theo một số cách như sau:
•Tính toán theo modulo
•Giải hệ phương trình modulo

54. Hoang Dac Thang, IOIT - VAST 54
3. Định lý phần dư Trung hoa
Tính toán theo modulo
Để tính A mod M, với M khá lớn và A là biểu thức số học nào đó. Trước hết
ta cần tính tất cả a
i = A mod m
i. Sau đó sử dụng công thức:
Trong đó: M
i = M/m
i
c
i = M
i x ( M
??????
−1
mod m
i) và 1 ≤ i ≤ k

55. Hoang Dac Thang, IOIT - VAST 55
Tính toán theo modulo
Ví dụ: Tính 17
8
mod 77. Áp dụng định lý phần dư Trung Hoa, ta coi A = 17
8

và M = 77, ta phân tích 77 thành tích của 7 x 11, ta được m
1 = 7, m
2 = 11.
Khi đó M
1 = M/m
1 = 77/7 = 11, M
2 = M/m
2 = 77/11 = 7
11
-1
mod 7 = 2, suy ra c
1 = 11 x 2 = 22 => c
1 = 22
7
-1
mod 11 = 8, suy ra c
2 = 7 x 8 = 56 => c
2 = 56
a
1 = 17
8
mod 7 = (17 mod 7)
8
mod 7 = 3
8
mod 7 = (3
2
)
4
mod 7 = 2
a
2 = 17
8
mod 11 = (17 mod 11)
8
mod 11 = 6
8
mod 7 = (6
2
)
4
mod 11 = 4
Vậy A = 17
8
mod 77 = (2.22 + 4.56) mod 77 = 268 mod 77 = 37.

56. Hoang Dac Thang, IOIT - VAST 56
Giải hệ phương trình modulo
Cho tập các số nguyên tố cùng nhau từng đôi một: m
1, m
2, …, m
r .
Với mỗi bộ số nguyên tố bất kỳ a
1, a
2, …, a
r .
Hệ phương trình đồng dư x ≡ a
i (mod m
i), với i = 1, 2, …, r luôn có nghiệm
duy nhất theo modulo m = m
1m
2 …m
r . Nghiệm này là:
x = a
1m
2m
3 …m
r b
1+ m
1a
2m
3 …m
r b
2+ …+ m
1m
2 …m
r-1 a
rb
r(mod m)
Trong đó b
i = (m
1m
2 …m
r )
-1
(mod m
i)

57. Hoang Dac Thang, IOIT - VAST 57
Giải hệ phương trình modulo
Ví dụ: Cho x ≡ 5 (mod 7)
x ≡ 6 (mod 11).
Tìm x?
Ta tính: 7
-1
mod 11 = 8
11
-1
mod 7 = 2.
Như vậy: x = (5.2.11 + 6.8.7) mod (7.11) = 61 mod 77

58. 58
Giải hệ phương trình: x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
•Bước 1: Xác định M
M = 3 x 5 x 7 = 105
•Bước 2: Xác định M
i =
M
m
i
→ M
1 = 105/3 = 35, M
2 = 105/5 = 21, M
3 = 105/7 = 15
•Bước 3: Tìm số nghịch đảo modulo của M
i
35 x b
1 ≡ 1 (mod 3). Giải ra ta được b
1 = 2
21 x b
2 ≡ 1 (mod 5). Giải ra ta được b
2 = 1
15 x b
3 ≡ 1 (mod 7). Giải ra ta được b
3 = 1
•Bước 4: Tính nghiệm x = a
1M
1b
1 + a
2M
2b
2 + a
3M
3b
3 (mod M)
x = 2 x 35 x 2 + 3 x 21 x 1 + 2 x 15 x 1 = 140 + 63 + 30 = 233
x = 233 mod 105 = 23
Vậy nghiệm của hệ phương trình là x = 23 (mod 105)

59. Hoang Dac Thang, IOIT - VAST 59
2.5 Thuật toán bình phương và nhân liên tiếp
•Là một phương pháp hiệu quả để tính lũy thừa của một số lớn
trong toán học, đặc biệt trong số học modulo.
•Trước hết ta phân tích số mũ theo cơ số 2, xét biểu diễn nhị phân
của số mũ
•Sau đó sử dụng thuật toán bình phương và nhân liên tiếp.
•Khái niệm được dựa trên phép lặp cơ sở bình phương và nhân liên
tiếp để nhận được kết quả mong muốn

60. Hoang Dac Thang, IOIT - VAST 60
2.5 Thuật toán bình phương và nhân liên tiếp
Cần tính a
n
mod m với a, n và m là các số nguyên lớn.
Ví dụ: 7
5
mod 11 = 7
4
.7
1
mod 11 = (7
4
mod 11).(7
1
mod 11) mod 11
Vì 7
2
mod 11 = 49 mod 11 = 5
7
4
mod 11 = (7
2
)
2
mod 11 = 5
2
mod 11 = 3

→ 7
5
mod 11 = 3.7 mod 11 =10

61. Hoang Dac Thang, IOIT - VAST 61
2.5 Thuật toán bình phương và nhân liên tiếp
5
123
mod 11 = ?
Đổi 123
(10) = 1111011
(2)
=> 5
123
= 5
(64+32+16+8+2+1)
= 5
64
x 5
32
x 5
16
x 5
8
x 5
2
x 5
1
5
1
mod 11 = 5
5
2
mod 11 = 3
5
4
mod 11 = (5
2
)
2
mod 11 = 3
2
mod 11 = 9
5
8
mod 11 = (5
4
)
2
mod 11 = 9
2
mod 11 = 4
5
16
mod 11 = (5
8
)
2
mod 11 = 4
2
mod 11 = 5
5
32
mod 11 = (5
16
)
2
mod 11 = 5
2
mod 11 = 3
5
64
mod 11 = (5
32
)
2
mod 11 = 3
2
mod 11 = 9
Vậy 5
123
mod 11 = (9 x 3 x 5 x 4 x 3 x 5) mod 11 = 4

62. Hoang Dac Thang, IOIT - VAST 62
2.5 Thuật toán bình phương và nhân liên tiếp
Khi cài đặt thuật toán tính lũy thừa ta có thể kết hợp bình phương và nhân
liên tiếp dựa trên triển khai nhị phân của lũy thừa.
Phân tích số mũ theo cơ số 2
Ví dụ: Với số mũ 11,
Trước hết ta chuyển số mũ 11 từ cơ số 10 sang cơ số 2: 11
(10) = 1011
(2).
Sau đó tính toán như sau:
M
11
= M
1.2^3 + 0.2^2+ 1.2^1 + 1.2^0
= (M
1.2^2 + 0.2^1+ 1.2^0
)
2
M =
= (M
1.2^1 + 0.2^0
)
2
M)
2
M = ((M
2
)
2
M)
2
M

63. Hoang Dac Thang, IOIT - VAST 63
2.5 Thuật toán bình phương và nhân liên tiếp
Như vậy, giả sử ta có số mũ là số nguyên được biểu diễn dưới dạng cơ số 2.
Bước khởi tạo: ban đầu gán kết quả bằng 1, thực hiện vòng lặp:
Bước lặp: duyệt dãy bit biểu diễn lũy thừa từ phải qua trái cho đến hết:
• Bình phương kết quả;
• Nếu bit là 1, thì nhân kết quả với cơ số.
Kết thúc: khi duyệt hết dãy bit, kết quả cho giá trị lũy thừa cần tìm

64. Hoang Dac Thang, IOIT - VAST 64
2.5 Thuật toán bình phương và nhân liên tiếp
Giả sử b
kb
k-1…b
0 là biểu diễn cơ số 2 của n. Tức là n có thể được viết như:
n = b
k.2
k
+ b
k-1.2
k-1
+…+ b
1.2
1
+ b
0.2
0
Với mỗi b
i là 0 hoặc 1, biểu diễn mỗi bit của n.
Tính a
n
mod m

65. 65
2.5 Thuật toán bình phương và nhân liên tiếp
n  0; d  1
for (i = k, i>=0, i--)
{
n  2 * n
d  (d * d) mod m
if (b
i = =1)
{
n  n + 1
d  (d * a) mod m
}
}

66. 66
2.6 Độ phức tạp tính toán
•Độ phức tạp tính toán đề cập đến mức độ khó khăn trong việc giải quyết các
bài toán dựa trên tài nguyên tính toán cần thiết như thời gian và không gian
bộ nhớ.
•Đây là một yếu tố quan trọng trong việc thiết kế và đánh giá hiệu quả của
các hệ thống bảo mật.
•Dữ liệu đầu vào đối với một thuật toán thường được biểu diễn qua các từ
trong một bảng ký tự nào đó.
•Độ dài của một từ là số ký tự trong từ đó.

67. 67
2.6 Độ phức tạp tính toán
•Cho một thuật toán A trên bảng ký tự Σ (tức có đầu vào là các từ trong Σ).
•Độ phức tạp tính toán của thuật toán A được hiểu là một hàm số f
A(n) sao
cho mỗi số n, f
A(n) là số ô nhớ, hay số phép toán sơ cấp tối đa mà A cần để
thực hiện tiến trình tính toán của mình trên các dữ liệu vào có độ dài ≤ n.
•Ta nói thuật toán A có độ phức tạp thời gian đa thức, nếu có một đa thức
P(n) sao cho với mọi n đủ lớn ta có f
A(n) ≤ P(n), trong đó f
A(n) là độ phức
tạp tính toán theo thời gian của A.

68. 68
2.6 Độ phức tạp tính toán
Khi nói đến các bài toán, ta hiểu đó là các bài toán quyết định, mỗi bài toán P
như vậy được xác định bởi:
•Một tập các dữ liệu vào I (trong một bảng ký tự Σ nào đó)
•Một câu hỏi Q trên các dữ liệu vào, sao cho với mỗi dữ liệu vào x ∈ I, câu
hỏi Q có một trả lời đúng hoặc sai

69. 69
2.6 Độ phức tạp tính toán
•Ta nói bài toán quyết định P là giải được, nếu có thuật toán để giải nó, tức là
thuật toán làm việc có kết thúc trên mọi dữ liệu vào của bài toán, và cho kết
quả đúng hoặc sai tùy theo câu hỏi Q trên dữ liệu đó có trả lời đúng hoặc
sai.
•Bài toán P là giải được trong thời gian đa thức, nếu có thuật toán giải nó với
độ phức tạp thời gian đa thức.

70. 70
1. Phân loại các lớp độ phức tạp
•P: Các bài toán có thể được giải quyết trong thời gian đa thức (polynomial
time) bởi máy tính xác định. Đây là những bài toán "dễ" trong lý thuyết độ
phức tạp.
•NP (Non-deterministic Polynomial time): Các bài toán có thể kiểm chứng
được nghiệm trong thời gian đa thức. Một số bài toán trong NP có thể "khó"
và chưa có cách giải hiệu quả.
•NP-complete: Tập hợp những bài toán trong NP, được coi là khó nhất. Nếu
tìm được cách giải hiệu quả cho một bài toán NP-complete, tất cả các bài
toán khác trong NP cũng có thể được giải quyết hiệu quả.
•NP-hard: Những bài toán có thể "khó hơn" NP, và không cần phải thuộc
lớp NP.

71. 71
2. Các thuật toán mã hóa và độ phức tạp
•Thuật toán mã hóa đối xứng (như AES, DES) thường có độ
phức tạp tính toán dựa trên kích thước khóa và số vòng lặp của
thuật toán.
•Thuật toán mã hóa bất đối xứng (như RSA, ECC) dựa trên các
bài toán toán học khó (như nhân số nguyên tố lớn hay logarit rời
rạc), với độ phức tạp tính toán phụ thuộc vào kích thước khóa và
tính khó của bài toán toán học.

72. 72
3. Logarit rời rạc
•Bài toán ngược của bài toán lũy thừa là tìm logarit rời rạc của một
số modulo p, tức là tìm số nguyên x sao cho: a
x
= b mod p
• hay còn được viết là x = log
ab mod p hoặc x = log
a,p(b)

73. 73
3. Logarit rời rạc
•Nếu a là căn nguyên tố của p và p là số nguyên tố, thì luôn luôn
tồn tại logarit rời rạc.
•Tổng quát hơn, nếu a là căn nguyên tố của n và hai số b, n là
nguyên tố cùng nhau, thì luôn tồn tại logarit rời rạc cơ số a của b.

74. 74
3. Logarit rời rạc
Ví dụ: Tìm x = log
2 3 mod 13.
Nghĩa là tìm x sao cho 2
x
mod 13 = 3
Bằng cách thử lần lượt:
2
0
mod 13 = 1; 2
1
mod 13 = 2, 2
2
mod 13 = 4,
2
3
mod 13 = 8, 2
4
mod 13 = 3.
Vậy x = 4

75. 75
3. Logarit rời rạc
Tìm x = log
3 4 mod 13 (tìm x: 3
x
= 4 mod 13).
3
0
mod 13 = 1; 3
1
mod 13 = 3;
3
2
mod 13 = 9; 3
3
mod 13 = 1= 3
0
mod 13.
Do lũy thừa của 3 theo modulo 13 chỉ nhận các giá trị 1, 3, 9 và
không có lũy thừa nào đạt giá trị bằng 4. → Không có lời giải.
Ở đây 3 không là căn nguyên tố của 13.

76. 76
3. Logarit rời rạc
•Ta nhận thấy, trong khi bài toán lũy thừa là dễ dàng,
thì bài toán logarit rời rạc là rất khó.
•Đây cũng là một cơ sở để thiết lập mã công khai.