Bài giảng Giải thuật nâng cao - Một số giải thuật trên số

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 𝒃 = 𝟐 (10110)2 = 12 4 + 122 + 121 = (22)10 𝒃 = 𝟏𝟔 (3𝐴0𝐹)16 = 316 3 + 10162 + 15160 = (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. • 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ố ≡ 3 (mod 5) ≡ 2 (mod 5) ≡ 1 (mod 5) ≡ 0 (mod 5) ≡ 4 (mod 5) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 -1 -7 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ố 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ố