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

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.
Nội dung trích xuất từ tài liệu:
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ệtMỘT SỐ GIẢI THUẬT TRÊN SỐ TS. NGÔ QUỐC VIỆT 2016Nội dung1. Giới thiệu2. Phép chia và số học modular3. Bài toán đồng dư và ứng dụng4. 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 ...