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

Chia sẻ: 4584125 4584125 | Ngày: | Loại File: PDF | Số trang:57

Thêm vào BST

Báo xấu

105
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng này cung cấp cho người học những kiến thức về giải thuật trên số. Các nội dung chính cần nắm bắt trong chương này gồm: Giới thiệu, phép chia và số học modular, bài toán đồng dư và ứng dụng, số nguyên tố. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Giải thuật nâng cao: Một số giải thuật trên số - TS. 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 𝒃=𝟐 (10110)2 = 124 + 122 + 121 = (22)10 𝒃 = 𝟏𝟔 (3𝐴0𝐹)16 = 3163 + 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. ≡0 (mod 5) 20 -1 15 ≡1 10 (mod 5) ≡ 4 19 5 21 14 16 (mod 5) 9 4 0 11 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ố