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! | M t mã ng dˆng Nh 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æa Xét a b 2 Z. Ta nói b là Óc cıa a hay a chia h t cho b n 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æa Xét a b 2 Z. Ta nói b là Óc cıa a hay a chia h t cho b n 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 53 Mª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 53 Bài t p Hã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à q và ph n d là r n u a b q r vÓi 0 r lt b. Bài t p Hãy ch ng minh r ng các sË q và r trên xác nh duy nhßt b i a và 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 lt 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
