Bài giảng Mật mã ứng dụng: Nhập môn số học thuật toán - Đại học Bách khoa Hà Nội

Bài giảng "Mật mã ứng dụng: Nhập môn số học thuật toán" trình bày các nội dung chính sau đây: Tính chất của hàm gcd; Thuật toán Euclid mở rộng; Thuật toán tính gcd;... 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 Mật mã ứng dụng: Nhập môn số học thuật toán - Đại học Bách khoa Hà Nội M™t mã ˘ng dˆngNh™p môn sË hÂc thu™t toán 1 / 53 Tài liªu tham kh£o• J. Hoffstein, J. Pipher, J. H. Silverman, An Introduction to Mathematical Cryptography, Springer-Verlag – Undergraduate Texts in Mathematics, 2nd Ed., 2014.• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. 2009.• H. H. Khoái, Nh™p môn sË hÂc thu™t toán 2 / 53 K˛ hiªu• N = {1, 2, 3, . . . }• Z = {. . . , 2, 1, 0, 1, 2, . . . } 3 / 53 ‡nh nghæaXét a, b 2 Z. Ta nói b là ˜Óc cıa a, hay a chia h∏t cho bn∏u có mÎt sË nguyên c sao cho a = bc.Ta vi∏t b | a ∫ chø a chia h∏t cho b. N∏u a không chia h∏t cho b thìta vi∏t b - a. 4 / 53 ‡nh nghæaXét a, b 2 Z. Ta nói b là ˜Óc cıa a, hay a chia h∏t cho bn∏u có mÎt sË nguyên c sao cho a = bc.Ta vi∏t b | a ∫ chø a chia h∏t cho b. N∏u a không chia h∏t cho b thìta vi∏t b - a.Ví dˆ • 847 | 485331 vì 485331 = 847 · 573. • 355 - 259943 vì 259943 = 4 / 53Mªnh ∑Xét a, b, c 2 Z. 1 N∏u a | b và b | c, thì a | c. 2 N∏u a | b và b | a, thì a = ±b. 3 N∏u a | b và a | c, thì a | (b + c) và a | (b c). 5 / 53Bài t™pHãy ch˘ng minh mªnh ∑ tr˜Óc. 6 / 53‡nh nghæa• ◊Óc chung cıa hai sË nguyên a và b là sË nguyên d th‰a mãn: d|a và d | b.• Ta k˛ hiªu gcd(a, b) là ˜Óc chung lÓn nhßt cıa a và b. 7 / 53 ‡nh nghæa • ◊Óc chung cıa hai sË nguyên a và b là sË nguyên d th‰a mãn: d|a và d | b. • Ta k˛ hiªu gcd(a, b) là ˜Óc chung lÓn nhßt cıa a và b.Ví dˆ • gcd(12, 18) = 6 vì 6 | 12 và 6 | 18 và không có sË nào lÓn hÏn có tính chßt này. • gcd(748, 2014) = 44 vì các ˜Óc cıa 748 = {1, 2, 4, 11, 17, 22, 34, 44, 68, 187, 374, 748}, các ˜Óc cıa 2024 = {1, 2, 4, 8, 11, 22, 23, 44, 46, 88, 92, 184, 253, 506, 1012, 2024}. 7 / 53 MÎt sË tính chßt cıa hàm gcd gcd(a, b) = gcd(b, a) gcd(a, b) = gcd( a, b) gcd(a, 0) = |a|gcd(a, ka) = |a| vÓi mÂi k 2 Z. 8 / 53 ‡nh nghæa (Chia lßy d˜)Xét a, b là các sË nguyên d˜Ïng. Ta nói a chia cho b có th˜Ïng là qvà ph¶n d˜ là r n∏u a = b·q+r vÓi 0  r < b.Bài t™pHãy ch˘ng minh r¨ng các sË q và r  trên xác ‡nh duy nhßt bi avà b. 9 / 53 Thu™t toán tính gcd(a, b)• Chia a cho b ta ˜Òc a = b·q+r vÓi 0  r < b.• Áp dˆng Øng th˘c gcd(a, b) = gcd(b, r). 10 / 53 Ví dˆ: Tính gcd(2024, 748)2024 = 748 · 2 + 528 748 = 528 · 1 + 220 528 = 220 · 2 + 88 220 = 88 · 2 + 44 gcd = 44 88 = 44 · 2 + 0 11 / 53 ‡nh l˛ (Thu™t toán Euclid)Xét a, b là hai sË nguyên d˜Ïng vÓi a b. Thu™t toán sau ây tínhgcd(a, b) sau mÎt sË h˙u h§n b˜Óc. 1 ∞t r0 = a và r1 = b. 2 ∞t i = 1. 3 Chia ri 1 cho ri , ta ˜Òc ri 1 = ri · qi + ri+1 vÓi 0  ri+1 < ri . 4 N∏u ri+1 = 0, v™y thì ri = gcd(a, b) và thu™t toán k∏t thúc. 5 Ng˜Òc l§i, ri+1 > 0, v™y thì ∞t i = i + 1 và quay l§i B˜Óc 3. 12 / 53 ‡nh l˛Phép chia (B˜Óc 3) cıa Thu™t toán Euclid th¸c hiªn nhi∑u nhßt log2 (b) + 2 l¶n. 13 / 53Thu™t toán Euclid (d§ng ª quy) EUCLID(a, b) if b == 0 return a else return EUCLID(b, a mod b) 14 / 53 Thu™t toán Euclid m rÎng• Thu™t toán Euclid có th∫ m rÎng ∫ tìm thêm mÎt sË thông tin.• Cˆ th∫, chúng ta m rÎng thu™t toán ∫ tính thêm hª sË x, y th‰a mãn d = gcd(a, b) = a x + b y.• Các hª sË x, y có th∫ âm ho∞c b¨ng 0. Các hª sË này s≥ có ích sau này khi tích ...