Bài giảng Giải thuật nâng cao - Một số giải thuật trên số - Ngô Quốc Việt

= 8 
x3 = 7x2+4 = 7*8+4 = 60 mod 9 = 6 
x4 = 7x3+4 = 7*6+4 = 46 mod 9 = 1 
x5 = 7x4+4 = 7*1+4 = 11 mod 9 = 2 
x6 = 7x5+4 = 7*2+4 = 18 mod 9 = 0 
x7 = 7x6+4 = 7*0+4 = 4 mod 9 = 4 
x8 = 7x7+4 = 7*4+4 = 32 mod 9 = 5 
• Các giá trị 𝑚 = 232 − 1, 𝑎 = 75 = 16,807, 𝑐 = 0 
thường được dùng để sinh số ngẫu nhiên 
• Yêu cầu: anh/chị hãy viết hàm sinh ra số ngẫu nhiên 
 Giải thuật nâng cao-Một số giải thuật trên số 
The Caesar cipher 
• Julius Caesar sử dụng thủ tục sau để mã hóa 
messages 
• Hàm f để mã hóa chữ được định nghĩa như sau: 
f(p) = (p+3) mod 26 
• Với p là a letter (0 là A, 1 là B, 25 là Z, etc.) 
• Giải mã: f-1(p) = (p-3) mod 26 
• Thủ tục này được gọi là substitution cipher 
Giải thuật nâng cao-Một số giải thuật trên số 
Mã hóa Caesar 
• Mã hóa “go cavaliers” 
• Chuyển thành số: g = 6, o = 14, etc. 
• Chuỗi số: 6, 14, 2, 0, 21, 0, 11, 8, 4, 17, 18 
• Áp dụng cipher cho từng số: f(6) = 9, f(14) = 17, etc. 
• Chuỗi đã mã: 9, 17, 5, 3, 24, 3, 14, 11, 7, 20, 21 
• Chuyển số thành chuỗi: 9 = j, 17 = r, etc. 
• Chuỗi chữ: jr wfdydolhuv 
• Giải mã “jr wfdydolhuv” 
• Chuyển thành số: j = 9, r = 17, etc. 
• Chuỗi số: 9, 17, 5, 3, 24, 3, 14, 11, 7, 20, 21 
• Áp dụng cipher cho từng số : f-1(9) = 6, f-1(17) = 14, etc. 
• Chuỗi số đã giải mã: 6, 14, 2, 0, 21, 0, 11, 8, 4, 17, 18 
• Chuyển số thành chuỗi: 6 = g, 14 = 0, etc. 
• Chuỗi gốc: “go cavaliers” 
Giải thuật nâng cao-Một số giải thuật trên số 
Số nguyên tố và ước chung lớn nhất 
• Số nguyên dương p được gọi là số nguyên tố nếu chỉ 
chia hết cho chính nó và 1. Ngược lại gọi là số hợp 
nguyên (composite integer). 
• Chú ý: 1 không phải là số nguyên tố 
Giải thuật nâng cao-Một số giải thuật trên số 
Số nguyên tố và ước chung lớn nhất 
• Định lý số học cơ bản: mọi số nguyên đều có thể biểu 
diễn duy nhất bởi tích của các số nguyên tố. 
• Định lý: số hợp nguyên n có số chia nguyên tố nhỏ 
hơn hoặc bằng 𝒏. 
• Suy ra: n là số nguyên tố nếu không chia hết cho bất 
kỳ số nguyên tố nào nhỏ hơn hay bằng 𝑛. 
• Định nghĩa: hai số nguyên a, b là nguyên tố cùng 
nhau nếu ước chung lớn nhất (GCD) của chúng là 1. 
• Định nghĩa: Các số 𝑎1, 𝑎2,  , 𝑎𝑛 là đôi một nguyên tố 
cùng nhau nếu: 𝑔𝑐 𝑑 𝑎𝑖 , 𝑎𝑗 = 1, 1 ≤ 𝑖 < 𝑗 ≤ 𝑛 
 Giải thuật nâng cao-Một số giải thuật trên số 
Một số định lý 
• Định lý Bézout : 
• ∀𝑎, 𝑏 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠, 𝑎, 𝑏 > 0: ∃𝑠, 𝑡: gcd 𝑎, 𝑏 = 𝑠𝑎 + 𝑡𝑏 
• Bổ đề 1: 
• ∀𝑎, 𝑏, 𝑐 > 0: gcd 𝑎, 𝑏 = 1 𝑎𝑛𝑑 𝑎 | 𝑏𝑐 thì 𝑎 | 𝑐. 
• Bổ đề 2: 
• Nếu p là số nguyên tố và 𝑝 | 𝑎1𝑎2𝑎𝑛 thì ∃𝑖: 𝑝 | 𝑎𝑖 
• Định lý 2: 
• Nếu 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚) và gcd 𝑐,𝑚 = 1 thì 
𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) 
Giải thuật nâng cao-Một số giải thuật trên số 
1. Start with (a,b) such that a >= b 
2. Take reminder r of a/b 
3. Set a := b, b := r so that a >= b 
4. Repeat until b = 0 
Chứng minh định lý Bézout 
Định lý Bézout: 𝑎 ≥ 𝑏 ≥ 0 𝑠, 𝑡: gcd (𝑎, 𝑏) =
 𝑠𝑎 + 𝑡𝑏 
Chứng minh 
Bổ đề Bézout là hệ quả của Euclidean division. 
𝑎 = 𝑏𝑥1 + 𝑟1, 0 < 𝑟1 < 𝑏 , gcd 𝑎, 𝑏 = gcd (𝑏, 𝑟1) 
Giải thuật nâng cao-Một số giải thuật trên số 
Chứng minh định lý Bézout 
𝑎 = 𝑏𝑥1 + 𝑟1, 0 < 𝑟1 < 𝑏 , gcd 𝑎, 𝑏 = gcd (𝑏, 𝑐) 
𝑏 = 𝑟1𝑥2 + 𝑟2, 0 < 𝑟2 < 𝑟1 
⋮ 
𝑟𝑛−1 = 𝑟𝑛𝑥𝑛+1 + 𝑟𝑛+1, 0 < 𝑟𝑛+1 < 𝑟𝑛, 
𝑟𝑛 = 𝑟𝑛+1𝑟𝑛+2 
• 𝑟𝑛+1 là phần dư khác zero cuối cùng trong tiến trình 
trên. 𝑟𝑛+1 là linear combination của 𝑟𝑛 và 𝑟𝑛−1, 𝑟𝑛 là 
linear combination của 𝑟𝑛−1 và 𝑟𝑛−2, 
•⋯ 
• 𝑟𝑛+1 là linear combination của a và b và là gcd của 
chúng. 
Giải thuật nâng cao-Một số giải thuật trên số 
Giải thuật nâng cao-Một số giải thuật trên số 
Ví dụ về định lý Bézout 
gcd(252,198) = 18. 
Biểu diễn 18 là kết hợp tuyến tính của 252 và 198. 
Sử dụng divisions theo Euclid Algorithm: 
252 = 1 198 + 54 (252 mod 198 = 54) 
198 = 3  54 + 36 (198 mod 54 = 36) 
54 = 1  36 +18 etc. 
36 = 2  18 
Vì, 18 = 54 - 1  36 (3rd equation) 
36 = 198 – 3  54 (2th equation) 
Do đó 18 = 54 - 1  (198 – 3  54) = 4  54 – 1  198 
Nhưng 54 = 252 - 1 198; thay thế 54 trong biểu thức này : 
18 = 4 (252 - 1 198) - 1  198 = 4  252 – 5  198 
gcd(252,198) = 
gcd(198,54) = 
gcd(54,36) = 
gcd(36,18) = 
gcd(18,0) = 
18 
Chứng minh Bổ đề 1 
Bổ đề 1: ∀𝑎, 𝑏, 𝑐 > 0: gcd 𝑎, 𝑏 = 1 & 𝑎 | 𝑏𝑐 thì 𝑎 | 𝑐. 
Theo định lý Bézout: 𝑠, 𝑡: 𝑠𝑎 + 𝑡𝑏 = 1. 
Nhân hai vế với c, c𝑠𝑎 + 𝑐𝑡𝑏 = 𝑐. 
Nếu 𝑎 | 𝑏𝑐 thì 𝑎 | 𝑡𝑏𝑐 . Ngoài ra 𝑎 | 𝑐𝑠𝑎 nên 
𝑎 | c𝑠𝑎 + 𝑐𝑡𝑏 . 
Vì vậy: 𝑎 | 𝑐 𝑠𝑎 + 𝑡𝑏 ⇒ 𝑎 | 𝑐 
Giải thuật nâng cao-Một số giải thuật trên số 
Chứng minh bổ đề 2 
Bổ đề 2: Nếu p là số nguyên tố và 𝑝 | 𝑎1𝑎2𝑎𝑛 thì 
∃𝑖: 𝑝 | 𝑎𝑖 
Chứng minh quy nạp: n = 1, hiển nhiên 
Giả sử đúng với 𝑛 < 𝑘 . Giả sử 𝑝 | 𝑎1𝑎2𝑎𝑘 . Đặt 
𝑚 = 𝑎1𝑎2𝑎𝑘−1 
Trường hợp 1: nếu 𝑝 | 𝑚, ∃𝑖: 𝑝 | 𝑎𝑖 
Trường hợp 2: nếu ≦𝑝 | 𝑚 ⇒ gcd 𝑝,𝑚 = 1. Ngoài ra 
𝑝 | 𝑚𝑎𝑘 (giả thiết). 
Theo bổ đề 1 thì: 𝑝 | 𝑎𝑘  
Giải thuật nâng cao-Một số giải thuật trên số 
Chứng minh định lý 2 
Định lý 2: Nếu 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚) và gcd 𝑐,𝑚 = 1 thì 
𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) 
Do: 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚) nên: 𝑚 𝑎𝑐 − 𝑏𝑐 ⟹ 𝑚 𝑐 (𝑎 − 𝑏) 
Theo bổ đề 1 với: gcd 𝑐,𝑚 = 1 và 𝑚| 𝑐 (𝑎 − 𝑏) nên 
 𝑚 | (𝑎 − 𝑏) 
Vì vậy: 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚)  
Giải thuật nâng cao-Một số giải thuật trên số 
Ứng dụng của định lý 2 
• Trong phát sinh số giả ngẫu nhiên: chọn bội số a là 
nguyên tố cùng nhau với m. Nghĩa là: gcd (𝑚, 𝑎) = 1. 
Thì: 
• Hàm chuyển từ xn thành xn+1 là đơn ánh 
• Vì nếu: 𝑥𝑛+1 ≡ 𝑎𝑥𝑛 𝑚𝑜𝑑 𝑚 = 𝑎𝑥
′
𝑛𝑚𝑜𝑑 𝑚, (giả sử gia số 
𝑐 = 0), thì: 𝑥𝑛 ≡ 𝑥
′
𝑛(𝑚𝑜𝑑 𝑚) 
• Nghĩa là: dãy số giả ngẫu nhiên không lặp lại cho đến 
khi gặp lại số x0 ban đầu 
Giải thuật nâng cao-Một số giải thuật trên số 
Lũy thừa modulo 
• Cho m nguyên dương, giá trị của 𝑏𝑛 𝑚𝑜𝑑 𝑚 được gọi là 
lũy thừa modulo. 
• Không thực tế nếu tính 𝑎 = 𝑏𝑛, sau đó tính 𝑎 𝑚𝑜𝑑 𝑚 
• Dựa trên khai triển nhị phân của số nguyên để tính 𝑏𝑛 
𝒃𝒏 = 𝒃𝒂𝒌−𝟏𝟐
𝒌−𝟏+𝒂𝒌−𝟐𝟐
𝒌−𝟐+⋯+𝒂𝟏𝟐+𝒂𝟎 = 𝒃𝒂𝒌−𝟏𝟐
𝒌−𝟏
𝒃𝒂𝟏𝟐𝒃𝒂𝟎 
• Để tính 𝑏𝑛 𝑚𝑜𝑑 𝑚 thì cần tính: 
𝑏2 𝑚𝑜𝑑 𝑚, 𝑏2
2
𝑚𝑜𝑑 𝑚, 𝑏2
3
𝑚𝑜𝑑 𝑚, , 𝑏2
𝑘−1
 𝑚𝑜𝑑 𝑚 (bổ 
đề: 𝑎𝑏 𝑚𝑜𝑑 𝑚 = 𝑎 𝑚𝑜𝑑 𝑚 . (𝑏 𝑚𝑜𝑑 𝑚) 𝑚𝑜𝑑 𝑚 ) 
Giải thuật nâng cao-Một số giải thuật trên số 
Giải thuật tính lũy thừa modulo 
• Bổđề: 
𝑎𝑏 𝑚𝑜𝑑 𝑚 = 𝑎 𝑚𝑜𝑑 𝑚 . (𝑏 𝑚𝑜𝑑 𝑚) 𝑚𝑜𝑑 𝑚 
Giải thuật nâng cao-Một số giải thuật trên số 
Giải thuật tính lũy thừa modulo: ví dụ 
• Tính 3644 𝑚𝑜𝑑 645 
Giải thuật nâng cao-Một số giải thuật trên số 
Số Mersenne 
• Số có dạng: 2𝑛 − 1 
• Số nguyên tố Mersenne: là số nguyên tố có dạng 2𝑝 − 1, 
với p nguyên tố. 
• Ví dụ: 25-1 = 31 là nguyên tố Mersenne, nhưng 211-1 = 2047 
không phải là nguyên tố Mersenne 
• Nếu M là nguyên tố Mersenne thì M(M+1)/2 là số hoàn 
hảo (số bằng với tổng các thương của nó – ví dụ: 
28 = 1 + 2 + 4 + 7 + 14 ) 
• Ví dụ: 25-1 = 31 là nguyên tố Mersenne, thì 31*32/2=496 là số 
hoàn hảo 
• 496 = 2*2*2*2*31  1+2+4+8+16+31+62+124+248 = 496 
• Số nguyên tố lớn nhất xác định được là số 
Mersenne. 
Giải thuật nâng cao-Một số giải thuật trên số 
Số nguyên tố Mersenne 
• Định lý: có vô hạn số nguyên tố 
• Kiểm tra Lucas-Lehmer: xác định số nguyên tố 
Mersenne 
• Số nguyên tố lớn nhất được tìm thấy: 12 triệu chữ số 
(tháng 10/2014) 
Giải thuật nâng cao-Một số giải thuật trên số 
Định lý số nguyên tố 
• Tỉ lệ của số lượng các số nguyên tố không lớn 
hơn x và x/ln(x) tiến tới 1 khi x tăng vô hạn 
• Số lượng các số nguyên tố nhỏ hơn x xấp xỉ bằng 
x/ln(x) (in 1792 by Gauss at 15...) 
• Cơ hội để số x là số nguyên tố xấp xỉ bằng: 1/ln(x). 
• Ví dụ: xét số nguyên tố có 200 chữ số 
• 𝑙𝑛 10200 ≈ 460 
• Trong 460 số nguyên có 200 chữ số thì có có thể có 1 số 
nguyên tố. 
• Manindra Agrawal et al (2002) giới thiệu giải thuật 
𝑂 𝑙𝑜𝑔𝑛 6 để xác định số n có phải là số nguyên tố 
Giải thuật nâng cao-Một số giải thuật trên số 
Ước chung lớn nhất 
• Cho hai số nguyên a, b: có thể sử dụng biểu diễn 
dạng tích của các nguyên tố để xác định GCD. 
• 𝑎 = 𝑝1
𝑎1𝑝2
𝑎2 𝑝𝑛
𝑎𝑛 , 𝑏 = 𝑝1
𝑏1𝑝2
𝑏2 𝑝𝑛
𝑏𝑛 . Các số mũ là 
nguyên không âm 
• Thì 𝑔𝑐𝑑 𝑎, 𝑏 = 𝑝1
min (𝑎1,𝑏1)𝑝2
min (𝑎2,𝑏2)𝑝𝑛
min (𝑎𝑛,𝑏𝑛) 
• Ví dụ: 120 = 23. 3.5, 500 = 22. 53 . Khi đó: 
𝑔𝑐𝑑 120,500 = 2min (3,2)3min (1,0)5min (1,3) = 20 
• Nhận xét: biểu diễn dạng thừa số nguyên tố có thể 
xác định được bội chung nhỏ nhất 
Giải thuật nâng cao-Một số giải thuật trên số 
Bội chung nhỏ nhất 
• Cho 𝑎 = 𝑝1
𝑎1𝑝2
𝑎2 𝑝𝑛
𝑎𝑛 , 𝑏 = 𝑝1
𝑏1𝑝2
𝑏2 𝑝𝑛
𝑏𝑛 . Các số mũ 
là nguyên không âm, thì: 
• 𝑙𝑐𝑚 𝑎, 𝑏 = 𝑝1
max (𝑎1,𝑏1)𝑝2
max (𝑎2,𝑏2)𝑝𝑛
max (𝑎𝑛,𝑏𝑛) 
• Ví dụ: 95256 = 23. 35. 72; 432 = 24. 33. Khi đó: 
𝑙𝑐𝑚 95256,432 = 2max (3,4)3max (5,3)7max (2,0)
= 190512 
Giải thuật nâng cao-Một số giải thuật trên số 
Định lý LCM & GCD 
• Định lý: cho a, b là hai số nguyên dương, thì 
𝑎 × 𝑏 = 𝑔𝑐𝑑 (𝑎, 𝑏) × 𝑙𝑐𝑚 𝑎, 𝑏 
• Ví dụ: : 𝑔𝑐𝑑 (10,25) = 5, 𝑙𝑐𝑚 (10,25) = 50, vì vậy 
10 × 25 = 5 × 50 
• Định lý: cho 𝑎 = 𝑏𝑞 + 𝑟, với a, b, q, r là số nguyên. 
Thì 𝑔𝑐𝑑 (𝑎, 𝑏) = 𝑔𝑐𝑑 (𝑏, 𝑟). 
Giải thuật nâng cao-Một số giải thuật trên số 
Giải thuật Euclid xác định GCD 
• Tính GCD dựa trên phân tích thừa số nguyên tố: hạn 
chế vì cần xác định các thừa số nguyên tố 
• Nhận xét: Với mọi cặp số nguyên a, b thì: 
𝑔𝑐𝑑 (𝑎, 𝑏) = 𝑔𝑐𝑑 𝑎 𝑚𝑜𝑑 𝑏, 𝑏 
Giải thuật nâng cao-Một số giải thuật trên số 
procedure procedure (a,b:positive integers) 
x := a 
y := b 
while y  0 
begin 
 r := x mod y 
 x := y 
 y := r 
end { gcd(a, b) is x } 
Giải thuật Euclid-Ví dụ 
Giải thuật nâng cao-Một số giải thuật trên số 
gcd(372,164) = gcd(164, 372 mod 164). 
372 mod 164 = 372164 372/164 = 372164·2 = 
372328 = 44. 
gcd(164,44) = gcd(44, 164 mod 44). 
164 mod 44 = 16444 164/44 = 16444·3 = 164132 = 
32. 
gcd(44,32) = gcd(32, 44 mod 32) 
 = gcd(32,12) = gcd(12, 32 mod 12) 
 = gcd(12,8) = gcd(8, 12 mod 8) 
 = gcd(8,4) = gcd(4, 8 mod 4) 
 = gcd(4,0) = 4. 
Đồng dư tuyến tính-nghịch đảo 
• Đồng dư tuyến tính có dạng: 𝑎𝑥 ≡ 𝑏 (𝑚𝑜𝑑 𝑚). Mục 
tiêu là tìm x thỏa biểu thức trên 
• Gọi a’ là nghịch đảo (modulo m)của a, nếu: 
𝑎′𝑎 ≡ 1 (𝑚𝑜𝑑 𝑚) 
• Nếu tồn tại a’, biểu thức trên: 
𝑎′𝑎𝑥 ≡ 𝑎′𝑏 (𝑚𝑜𝑑 𝑚) 
1. 𝑥 ≡ 𝑎′𝑏 (𝑚𝑜𝑑 𝑚) 
Định lý: nếu gcd (𝑎,𝑚) = 1 và 𝑚 > 1 thì tồn tại duy 
nhất a’ là nghịch đảo (modulo m) của a. 
Giải thuật nâng cao-Một số giải thuật trên số 
Ví dụ: đồng dư tuyến tính-nghịch đảo 
• Tìm nghịch đảo của 4 (modulo 9) 
𝑔𝑐𝑑 4,9 = 1 
9 = 2  4 + 1 
1 = −2  4 + 19 
−𝟐  4 ≡ 1 (𝑚𝑜𝑑 9) 
Các số đồng dư tuyến tính với -2 (mod 9) đều là 
nghịch đảo của 4 (modulo 9) 
Giải thuật nâng cao-Một số giải thuật trên số 
Định lý phần dư Trung hoa 
• Định lý: cho 𝑚1,  ,𝑚𝑛 > 1 là nguyên tố cùng nhau, và 
𝑎1,  , 𝑎𝑛 là các số nguyên bất kỳ . Thì hệ phương trình 
𝑥 ≡ 𝑎𝑖 𝑚𝑜𝑑 𝑚𝑖 , 𝑖 = 1 → 𝑛 có lời giải duy nhất modulo 
𝑚 = 𝑚1 · ⋯ · 𝑚𝑛. Nghĩa là 0 ≤ 𝑥 < 𝑚, và nếu có y thỏa hệ 
phương trình trên thì 𝑥 ≡ 𝑦 (𝑚𝑜𝑑 𝑚). 
Đặt: 𝑀𝑖 = 𝑚/𝑚𝑖 thì gcd 𝑀𝑖 , 𝑚𝑖 = 1 ⇒ ∃! 𝑦𝑖: 𝑦𝑖𝑀𝑖 ≡
1 (𝑚𝑜𝑑 𝑚𝑖) (định lý về đồng dư nghịch đảo) 
Đặt 𝒙 = 𝒂𝒊𝒚𝒊𝑴𝒊𝒊 . 
Vì: 𝑚𝑖|𝑀𝑘 , 𝑘 ≠ 𝑖, nên 𝑀𝑘 ≡ 0 (𝑚𝑜𝑑 𝑚𝑖) 
Nên: 𝑥 𝑚𝑜𝑑 𝑚𝑖 = 𝑎𝑙𝑦𝑙𝑀𝑙𝑙 𝑚𝑜𝑑 𝑚𝑖 = 𝑎𝑖𝑦𝑖𝑀𝑖 𝑚𝑜𝑑 𝑚𝑖 =
𝑎𝑖 𝑚𝑜𝑑 𝑚𝑖 
Vậy: 𝑥 ≡ 𝑎𝑖 𝑚𝑜𝑑 𝑚𝑖 , ∀𝑖 = 1 → 𝑛. Và x là lời giải cần tìm. 
Giải thuật nâng cao-Một số giải thuật trên số 
Định lý phần dư Trung hoa-ví dụ 
Tìm x sao cho: 𝑥 ≡ 2 (𝑚𝑜𝑑 3), 𝑥 ≡ 3 (𝑚𝑜𝑑 7), 
 𝑥 ≡ 2 (𝑚𝑜𝑑 7) 
Giải thuật nâng cao-Một số giải thuật trên số 
m = 357 = 105 
M1 = m/3 = 105/3 = 35 
 2 là nghịch đảo của M1 = 35 (mod 3) (vì 35x2 ≡ 1 (mod 3)) 
M2 = m/5 = 105/5 = 21 
 1 là nghịch đảo của M2 = 21 (mod 5) (vì 21x1 ≡ 1 (mod 5)) 
M3 = m/7 = 15 
 1 là nghịch đảo của M3 = 15 (mod 7) (vì 15x1 ≡ 1 (mod 7)) 
Vậy , x ≡ 2  2  35 + 3  1  21 + 2  1  15 = 233 ≡ 23 (mod 105) 
Lời giải: x ≡ 23 (mod 105) 
Dựa trên định lý phần dư Trung hoa 
x = ∑i ai yi Mi 
m = m1··mn. 
Mi = m/mi 
yi Mi ≡ 1 (mod mi). a1 = 2, a2 = 3, a3 = 2 
m1 = 3, m2 = 5, m3 = 7 
Định lý phần dư Trung hoa-MATLAB 
function x=CRT(r,p) 
if (length(r)==length(p)) 
 l=length(r); 
 CM=1; 
 for i=1:l 
 CM=CM*p(i); 
 end 
 M=zeros(1,l); 
 for i=1:l 
 M(i)=CM/p(i); 
 end 
 IM=zeros(1,l); 
 x=0; 
 for i=1:l 
 IM(i)=invmodan(M(i),p(i)); x=x+r(i)*M(i)*IM(i); 
 end 
 display('Value of x: '); x=mod(x,CM); 
else display('Length of r and p matrices must be same'); 
end 
Giải thuật nâng cao-Một số giải thuật trên số 
Định lý phần dư Trung hoa-MATLAB 
function y=invmodn(x,p) 
n=eulerphi(p); 
% Compute Euler's totient function of p 
b=dec2bin(n-1); 
len=length(b); 
a=ones(1,len); 
a(1)=rem(x,p); 
for i=1:(len-1) 
 a(i+1)=rem((a(i))^2,p); 
end 
b=fliplr(b); mul=1; 
for i=1:len 
 if b(i)=='0' a(i)=1; 
 end 
 mul=mul*a(i); mul=rem(mul,p); 
end 
y=rem(mul,p); 
Giải thuật nâng cao-Một số giải thuật trên số 
Định lý phần dư Trung hoa-MATLAB 
function phi=eulerphi(n) 
if (n>1 && mod(n,1)==0) 
 f=factor(n); l=length(f); phi=1; 
 for i=1:l 
 phi=phi*(f(i)-1); 
 end 
elseif (n==1) 
 phi=1; 
else display('Invalid number entered'); 
end 
Giải thuật nâng cao-Một số giải thuật trên số 
Tính toán số nguyên lớn 
• Cho số nguyên a bất kỳ, 0 ≤ 𝑎 < 𝑚 , với 𝑚 =
 𝑚𝑖 , gcd 𝑚𝑖 , 𝑚𝑗≠𝑖 = 1 thì a có thể được biểu diễn 
bởi các phần dư của a với mi. Nghĩa là bộ n 
𝑎 𝑚𝑜𝑑 𝑚1, 𝑎 𝑚𝑜𝑑 𝑚2,  , 𝑎 𝑚𝑜𝑑 𝑚𝑛 . 
• Xét hệ phương trình: 
 𝑥 ≡ 𝑎𝑖 𝑚𝑜𝑑 𝑚𝑖 , với 𝑎𝑖 = 𝑎 𝑚𝑜𝑑 𝑚𝑖 . Thì tồn 
tại duy nhất nghiệm x. 
• Xét: 𝑥 = 𝑎 𝑚𝑜𝑑 𝑚, thì x là nghiệm của hệ phương 
trình trên. 
Giải thuật nâng cao-Một số giải thuật trên số 
Tính toán số nguyên lớn 
Hãy biểu diễn số nguyên x nhỏ hơn 12 bởi một cặp. Chọn 
cặp là hai số nguyên tố cùng nhau. Ví dụ 3 và 4. 
Biểu diễn x theo các bộ (𝑥 𝑚𝑜𝑑 3, 𝑥 𝑚𝑜𝑑 4). Xác định 
phần dư của các số chia cho 3 và 4. 
0=(0,0); 1=(1,1); 2=(2,2); 3=(0,3); 4=(1,0); 5=(2,1); 
6=(0,2); 7=(1,3); 8=(2,0); 9= (0,1); 10 = (1,2); 11= 
(2,3) 
• 
Ví dụ: 11 = (11 mod 3, 11 mod 4) = (2, 3) 
Vậy: có thể sử dụng hai số nguyên nhỏ để biểu diễn số 
nguyên nhỏ hơn 12. 
Giải thuật nâng cao-Một số giải thuật trên số 
Tính toán số nguyên lớn 
•Để thực hiện tính toán trên số nguyên lớn, 
thực hiện theo các bước sau 
• Thực hiện trên các phép toán trên các phần 
dư! 
• Có thể thực hiện song song. 
• Hay thực hiện tuần tự trên máy đơn. 
• Tiếp tục đến khi desired result < m. 
Giải thuật nâng cao-Một số giải thuật trên số 
Tính toán số nguyên lớn 
Ví dụ: giả sử có thể tính toán dễ với các số nhỏ hơn 100; Khi đó có thể 
giới hạn tính toán các số nguyên thành tính các số nhỏ hơn 100, nếu 
có thể biểu diễn ở dạng phần dư đôi một nguyên tố cùng nhau, ví dụ: 
99, 98, 97, 95. 
Theo định lý phần dư Trung Hoa, mọi số nhỏ hơn 9998 9795 = 
89.403.930 có thể biểu diễn duy nhất theo các phần dư của chúng với 
các số 99, 98 , 97 , 95. 
Ví dụ, số 123684 có thể biểu diễn bởi 
(123684 mod 99; 123684 mod 98; 123684 mod 97; 123684 mod 95) = 
(33,8,9,89) 
 413456 có thể biểu diễn bởi 
(413456 mod 99; 413456 mod 98; 413456 mod 97; 413456 mod 95)= 
(32,92,42,16) 
Giải thuật nâng cao-Một số giải thuật trên số 
Tính toán số nguyên lớn 
Để cộng hai số 123.684, và 413456. 
(33, 8, 9, 89)+(32, 92 , 42, 16) 
= (65 mod 99, 100 mod 98, 51 mod 97, 105 mod 95) 
= (65, 2, 51, 10) 
Để tìm tổng: giải hệ phương trình đồng dư tuyến tính 
sau 
 x ≡ 65 (mod 99) 
 x ≡ 2 (mod 98) 
 x ≡ 51 (mod 97) 
 x ≡ 10 (mod 95) 
 Lời giải: x= 537,140 
Giải thuật nâng cao-Một số giải thuật trên số 
Tính toán số nguyên lớn 
• Ví dụ, các số sau là nguyên tố cùng nhau: 
 m1 = 2
25−1 = 33,554,431 = 31 · 601 · 1,801 
 m2 = 2
27−1 = 134,217,727 = 7 · 73 · 262,657 
 m3 = 2
28−1 = 268,435,455 = 3 · 5 · 29 · 43 · 113 · 127 
 m4 = 2
29−1 = 536,870,911 = 233 · 1,103 · 2,089 
 m5 = 2
31−1 = 2,147,483,647 (prime) 
• Vậy, có thể biểu diễn số nguyên lớn 
• m = ∏mi ≈ 1.4×10
42 ≈ 2139.5 theo các phần dư ri modulo với các mi trên. 
• Vd:. 1030 = (r1 = 20900945; r2 = 18304,504; r3 = 65829085; 
r4 = 516865185; r5 = 1234980730) 
• Để cộng hai số theo biểu diễn đồng dư 
• Cộng các phần dư tương ứng. 
• Lấy kết quả mod 2k−1: 
• Nếu ≥ giá trị 2k−1, trừ nó với 2k−1 
• Chú ý: No carries are needed between the different pieces! 
Giải thuật nâng cao-Một số giải thuật trên số 
Pseudoprimes 
• Nếu n nguyên tố thì 2𝑛−1 ≡ 1 (𝑚𝑜𝑑 𝑛), tuy nhiên 
điều ngược lại không đúng [nghĩa là nếu 2𝑛−1 ≡
1 (𝑚𝑜𝑑 𝑛) thì n có thể không nguyên tố]. 
• Ví dụ: 2𝟑𝟒𝟏−1 ≡ 1 (𝑚𝑜𝑑 341) , nhưng 341 = 11 × 31 
không phải là số nguyên tố. 
• Số n với tính chất này được gọi là pseudoprime. 
• Tổng quát, nếu 𝒃𝒏−𝟏 ≡ 𝟏 (𝒎𝒐𝒅 𝒏) và n là số hợp 
nguyên, thì n được gọi là pseudoprime cơ số b. 
Giải thuật nâng cao-Một số giải thuật trên số 
Định lý nhỏ của Fermat 
• Định lý: (Fermat’s Little Theorem.) 
• Nếu p nguyên tố và a nguyên không chia hết p; (𝑎 ∤
𝑝), thì 
𝑎𝑝−1 ≡ 1 (𝑚𝑜𝑑 𝑝) 
• Ngoài ra, với mọi số nguyên a thì 
𝑎𝑝 ≡ 𝑎 (𝑚𝑜𝑑 𝑝) 
• Nhận xét: nếu 𝑎 ∈ 𝑍𝑝 thì 𝑎
𝑝−1 ≡ 1 trong Zp. 
Giải thuật nâng cao-Một số giải thuật trên số 
Các số Carmichael 
• Định nghĩa: số hợp nguyên n thỏa mãn 𝑏𝑛−1 ≡
1 𝑚𝑜𝑑 𝑛 , ∀𝑏: gcd 𝑏, 𝑛 = 1 được gọi là số Carmichael. 
• Ví dụ: 561 là số Carmichael 
• 561=3.11.17 
• Nếu gcd (𝑏, 561) = 1 thì 
gcd (𝑏, 3) = 1, gcd (𝑏, 11) = 1, gcd (𝑏, 17) = 1 
• 𝑏2 ≡ 1 𝑚𝑜𝑑 3 ; 𝑏1 ≡ 1 𝑚𝑜𝑑 11 ; 𝑏16 ≡ 1 𝑚𝑜𝑑 17 ; 
• 𝑏560 = 𝑏2 280 ≡ 1 (𝑚𝑜𝑑 3) 
• 𝑏560 = 𝑏10 56 ≡ 1 (𝑚𝑜𝑑 11) 
• 𝑏560 = 𝑏16 35 ≡ 1 (𝑚𝑜𝑑 16) 
• Các số: 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341 
là số Carmichael 
Giải thuật nâng cao-Một số giải thuật trên số 
Mã RSA 
Phát sinh mã 
1. Chọn hai prime numbers p và q (ngẫu nhiên). 
2. 𝑛 = 𝑝𝑞, dùng làm modulus. 
3. 𝜑(𝑛) = 𝜑(𝑝)𝜑(𝑞) = (𝑝 − 1)(𝑞 − 1) = 𝑛 − (𝑝 + 𝑞 − 1) hàm 
totient), là private key 
4. Chọn số e sao cho 1 < 𝑒 < 𝜑(𝑛), và gcd(e, φ(n)) = 1. 
• e là public key exponent. 
• Giá trị e nhỏ không hiệu quả để bảo mật. 
5. Tìm: d ≡ e−1 (mod φ(n)). 
• d là private key exponent 
• Public key: số n và e. 
• Private key: số d. 
Giải thuật nâng cao-Một số giải thuật trên số 
Mã RSA 
Mã hóa 
1. A gởi 𝑛, 𝑒 (public key - gởi đi) cho B. A giữ bí mật giá trị d. 
2. B cần gởi gói tin M mã với 𝑛, 𝑒 để gởi cho A. 
3. Chuyển M thành giá trị nguyên m. 
4. Tính 𝑐 ≡ 𝑚𝑒 𝑚𝑜𝑑 𝑛 , là gói B gởi cho A. 
Giải mã 
• A cần phục hồi m, M khi nhận được c từ B. 
• 𝑚 ≡ 𝑐𝑑 𝑚𝑜𝑑 𝑛 
Giải thuật nâng cao-Một số giải thuật trên số 
Mã RSA-ví dụ 
• Cho 𝑝 = 61, 𝑞 = 5. 
• 𝑛 = 61 ∗ 53 = 3233 
• 𝜑 3233 = 3120 
• Chọn 1 < 𝑒 < 3120 nguyên tố cùng nhau với 3120. 
Chọn e = 17. 
• 𝑒 × 𝑑 = 1 (𝑚𝑜𝑑 3120)  d = 2753. 
• Public key: 𝑛 = 3233, 3 = 17 
• Private key: 𝑑 = 2753. 
• Cho m = 65 
• Mã hóa m: 𝑐 = 6517 𝑚𝑜𝑑 3233 = 2790. 
• Giải mã c: 𝑚 = 27902753 𝑚𝑜𝑑 3233 = 65. 
Giải thuật nâng cao-Một số giải thuật trên số 
Bài tập 
1. Tìm nghiệm: 2 2
2006
𝑚𝑜𝑑 3 
 2 2
2006
= 2 2.2
2005 = 4 2
2205
≡1 (𝑚𝑜𝑑 3) 
2. Chứng minh: nếu tồn tại số đảo (multiplicative 
inverse hoặc reciprocal) modulo N, thì nó là duy 
nhất. 
Giả sử tồn tại hai số đảo x1, x2 khác nhau của a. 
𝑥1 = 𝑥1. 1 = 𝒙𝟏. 𝒂. 𝑥2 = 1. 𝑥2 = 𝑥2 𝑚𝑜𝑑 𝑁 
Giải thuật nâng cao-Một số giải thuật trên số 
Bài tập 
3. Xét RSA, p=7, q=11. Tìm e và d. 
𝑝 − 1 ∗ 𝑞 − 1 = 60 
Tìm e nguyên tố cùng nhau với 60, và có số 
nghịch đảo. Chọn e=11  d= 11 (mod 60). 
Có thể chọn các cặp (e, d) khác: (7, 43); (13, 37); 
(17, 53); (19, 59); (23, 47); (29, 29); (31, 31); (41, 
41). 
4. Cài đặt và thuyết minh RSA bằng MATLAB. 
Giải thuật nâng cao-Một số giải thuật trên số