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

MỘT SỐ GIẢI THUẬT TRÊN SỐ TS. NGÔ QUỐC VIỆT 2016 Nội dung 1. Giới thiệu 2. Phép chia và số học modular 3. Bài toán đồng dư và ứng dụng 4. Số nguyên tố Giải thuật nâng cao-Một số giải thuật trên số Giới thiệu • Lý thuyết số khảo sát số nguyên, các tính chất và các ứng dụng liên quan. • Khảo sát: một số ký hiệu, thuật ngữ, định lý liên quan • Lý thuyết số ứng dụng trong nhiều giải thuật quan trọng: hàm băm, mã hóa, chữ ký số, online security. Giải thuật nâng cao-Một số giải thuật trên số Phép chia • Cho a, b là số nguyên, 푎 ≠ 0. Nói a chia hết b nếu tồn tại số nguyên c sao cho: 푏 = 푎푐. • • Ký hiệu chia hết: 풂 | 풃. Ví dụ : 3 | 12 • Ký hiệu không chia hết: 풂 ∤ 풃 (ví dụ: 5 ∤ 12) • Định lý: a,b,c  Z: 1. 풂|ퟎ 2. (풂|풃  풂|풄)  풂 | (풃 + 풄) 3. 풂|풃  풂|풃풄 4. (풂|풃  풃|풄)  풂|풄 • Bổ đề: nếu 푎|푏, 푎|푐 thì 푎|푚푏 + 푛푐, 푎, 푏, 푐, 푚, 푛 ∈ 푍. Giải thuật nâng cao-Một số giải thuật trên số Giải thuật “Chia” • Định lý: cho a, d là số nguyên dương, thì tồn tại duy nhất q và r, 0 ≤ 푟 < 푑, sao cho 푎 = 푑푞 + 푟. • q: thương số; a: số bị chia; d: số chia; r: số dư • Cho số dương a và d dương, để xác định r, lặp lại trừ d với a, cho tới khi còn lại r mà nhỏ hơn d • Cho a âm và d dương, để xác định r, lặp lại cộng d với a, cho tới khi còn lại r, là dương (hoặc zero) nhỏ hơn d Giải thuật nâng cao-Một số giải thuật trên số Biểu diễn số nguyên • Cho 푏 > 1 nguyên dương. Có thể biểu diễn số nguyên dương n duy nhất theo dạng 푘 푘−1 푛 = 푎푘푏 + 푎푘−1푏 + ⋯ + 푎1푏 + 푎0, 푘 ∈ 푁, 푎0, , 푎푘 < 푏, 푎푘 ≠ 0 Ví dụ: 풃 = ퟏퟎ 859 = 8. 102 + 5101 + 9 풃 = ퟐ 4 2 1 (10110)2 = 12 + 12 + 12 = (22)10 풃 = ퟏퟔ 3 2 0 (3퐴0퐹)16 = 316 + 1016 + 1516 = (14863)10 Giải thuật nâng cao-Một số giải thuật trên số Số học modular • Cho a là số nguyên, m số nguyên dương. Ký hiệu 푎 푚표푑 푚 biểu diễn phần dư khi a được chia cho m. • Ví dụ: 9 푚표푑 4 = 1 −13 푚표푑 4 = 3 • Cho a, b là số nguyên, m số nguyên dương. Khi đó “a đồng dư b modulo m” nếu: 풎 | 풂 − 풃. Ký hiệu: 푎 ≡ 푏 (푚표푑 푚). • Ký hiệu: 푎 ≢ 푏 (푚표푑 푚), a không đồng dư b mod m. • Chú ý: số dư luôn dương. Giải thuật nâng cao-Một số giải thuật trên số Số học modular • Định lý: Cho a, b là số nguyên, m số nguyên dương. Thì 푎 ≡ 푏 (푚표푑 푚) nếu và chỉ nếu 푎 푚표푑 푚 = 푏 푚표푑 푚. • Định lý: Cho m là số nguyên dương. Hai số nguyên a, b là đồng dư modulo m nếu và chỉ nếu tồn tại số k sao cho: 푎 = 푏 + 푘푚. • Ví dụ: ퟏퟕ = ퟓ + ퟐ ∗ 6 hoặc ퟓ = ퟏퟕ − ퟐ ∗ 6. (17 ≡ 5 (푚표푑 2)) • Định lý: Cho m là số nguyên dương. Nếu 푎 ≡ 푏 (푚표푑 푚) và 푐 ≡ 푑 (푚표푑 푚) thì: (푎 + 푐) ≡ (푏 + 푑) (푚표푑 푚) và 푎푏 ≡ 푐푑 (푚표푑 푚). • Bổ đề: Cho a, b là số nguyên, m số nguyên dương thì 푎 + 푏 푚표푑 푚 = 푎 푚표푑 푚 + 푏 푚표푑 푚 푚표푑 푚 và 푎푏 푚표푑 푚 = 푎 푚표푑 푚 . (푏 푚표푑 푚) 푚표푑 푚 Giải thuật nâng cao-Một số giải thuật trên số Số học modular • Ví dụ: Các lớp đồng dư modulo 5. ≡ 0 (mod 5) 20 -1 15 ≡ 1 10 (mod 5) ≡ 4 19 5 21 14 16 (mod 5) 9 11 4 0 6 1 3 2 8 7 13 12 18 17 ≡ 3 22 ≡ 2 (mod 5) (mod 5) -7 • Hỏi: xác định vị trí của -1 và -7? Giải thuật nâng cao-Một số giải thuật trên số Số học modular • Đặt: 푍푚 = 푖 ∈ 푁 | 푖 < 푚 = 0, 1, , 푚 − 1 . • Ký hiệu +푚: cộng các số trong Zm. 푎 +푚 푏 = 푎 + 푏 푚표푑 푚 • Ký hiệu .푚: nhân các số trong Zm 푎.푚 푏 = 푎. 푏 푚표푑 푚 • Các phép toán +푚 và .푚 được gọi là cộng và nhân modulo. 7 +11 9 = 7 + 9 푚표푑 11 = 5 7.11 9 = 7.9 푚표푑 11 = 8 • Các phép +푚 và .푚 thỏa mãn các tính chất: đóng, kết hợp, giao hoán, phân bố, phần tử đơn vị. • 푍푚 là nhóm giao hoán, và 푍푚 cùng với hai phép +푚, .푚 là vành giao hoán Giải thuật nâng cao-Một số giải thuật trên số Ứng dụng của đồng dư modulo • Hàm băm (xem lại bảng băm – cấu trúc dữ liệu) • Số giả ngẫu nhiên • Kiểm tra chữ số (digit checks) • Mã hóa Giải thuật nâng cao-Một số giải thuật trên số Số giả ngẫu nhiên • Cần mô phỏng trên máy tính để tạo ra số ngẫu nhiên  số giả ngẫu nhiên (P.288-Rosen’s book) • Phương pháp đồng dư tuyến tính: giải thuật phổ biến để sinh số ngẫu nhiên • Chọn 4 số nguyên • Tâm (seed) x0: giá trị khởi đầu 0 ≤ 푥0 < 푚 • Modulus m • Bội số a: 2 ≤ 푎 < 푚 • Gia số c: 0 ≤ 푐 < 푚 • Sinh dãy số ngẫu nhiên, *푥푛 | 0 ≤ 푥푛 < 푚+, theo biểu thức: 푥푛+1 = (푎푥푛 + 푐) 푚표푑 푚 Giải thuật nâng cao-Một số giải thuật trên số Số giả ngẫu nhiên • Công thức: xn+1 = (axn + c) mod m • Ví dụ: Cho x0 = 3, m = 9, a = 7, and c = 4 x1 = 7x0+4 = 7*3+4 = 25 mod 9 = 7 x2 = 7x1+4 = 7*7+4 = 53 mod 9 = 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ố 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) 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 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ố 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: gcd(252,198) = gcd(198,54) = 252 = 1 198 + 54 (252 mod 198 = 54) gcd(54,36) = 198 = 3  54 + 36 (198 mod 54 = 36) gcd(36,18) = 54 = 1  36 +18 etc. gcd(18,0) = 18 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 Giải thuật nâng cao-Một số giải thuật trên số 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 3 푘−1 푏2 푚표푑 푚, 푏2 푚표푑 푚, 푏2 푚표푑 푚, , 푏2 푚표푑 푚 (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 푎2 푎푛 푏1 푏2 푏푛 • 푎 = 푝1 푝2 푝푛 , 푏 = 푝1 푝2 푝푛 . Các số mũ là nguyên không âm min (푎1,푏1) min (푎2,푏2) min (푎푛,푏푛) • Thì 푔푐푑 푎, 푏 = 푝1 푝2 푝푛 • 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 푎1 푎2 푎푛 푏1 푏2 푏푛 • Cho 푎 = 푝1 푝2 푝푛 , 푏 = 푝1 푝2 푝푛 . Các số mũ là nguyên không âm, thì: max (푎1,푏1) max (푎2,푏2) max (푎푛,푏푛) • 푙푐푚 푎, 푏 = 푝1 푝2 푝푛 • 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ì: 푔푐푑 (푎, 푏) = 푔푐푑 푎 푚표푑 푏, 푏 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 nâng cao-Một số giải thuật trên số Giải thuật Euclid-Ví dụ 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. Giải thuật nâng cao-Một số giải thuật trên số Đồ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), m = m1··mn. 푥 ≡ 2 (푚표푑 7) Dựa trên định lý phần dư Trung hoa M = m/m m = 357 = 105 i i a1 = 2, a2 = 3, a3 = 2 yi Mi ≡ 1 (mod mi). m1 = 3, m2 = 5, m3 = 7 M1 = m/3 = 105/3 = 35 x = ∑i ai yi Mi 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) 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 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: 25 m1 = 2 −1 = 33,554,431 = 31 · 601 · 1,801 27 m2 = 2 −1 = 134,217,727 = 7 · 73 · 262,657 28 m3 = 2 −1 = 268,435,455 = 3 · 5 · 29 · 43 · 113 · 127 29 m4 = 2 −1 = 536,870,911 = 233 · 1,103 · 2,089 31 m5 = 2 −1 = 2,147,483,647 (prime) • Vậy, có thể biểu diễn số nguyên lớn 42 139.5 • m = ∏mi ≈ 1.4×10 ≈ 2 theo các phần dư ri modulo với các mi trên. 30 • Vd:. 10 = (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ì 푎푝 ≡ 푎 (푚표푑 푝) 푝−1 • Nhận xét: nếu 푎 ∈ 푍푝 thì 푎 ≡ 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 2006 1. Tìm nghiệm: 2 2 푚표푑 3 2006 2005 22205 2 2 = 2 2.2 = 4 ≡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ố