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

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

Thêm vào BST

Báo xấu

16
lượt xem 7
download

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

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!

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 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ˆ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 < 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 < 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ính gcd(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 / 53
Thu™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 ph¶n t˚ ngh‡ch £o trong sË hÂc modun. 15 / 53
Thu™t toán Euclid m rÎng • Input : C∞p sË nguyên d˜Ïng (a, b) • Output: BÎ ba (d, x, y) th‰a mãn d = gcd(a, b) = a x + b y. EXTENDED-EUCLID(a, b) if b == 0 return (a, 1, 0) else (d 0 , x 0 , y 0 ) = EXTENDED-EUCLID(b, a mod b) (d, x, y) = (d 0 , y 0 , x 0 ba/bc y 0 ) return (d, x, y) 16 / 53
Tính úng ≠n cıa thu™t toán • Thu™t toán tìm (d, x, y) th‰a mãn d = gcd(a, b) = a x + b y • N∏u b = 0, v™y thì d = a = a · 1 + b · 0. • N∏u b 6= 0, thu™t toán EXTENDED-EUCLID s≥ tính (d 0 , x 0 , y 0 ) th‰a mãn d 0 = d = gcd(b, a mod b) = b x 0 + (a mod b) y 0 • Và v™y thì d = b0 x 0 + (a bba/bc) y 0 = a y 0 + b(x 0 ba/bc y 0 ) 17 / 53
Ví dˆ a b ba/bc d x y 99 78 1 3 11 14 78 21 3 3 3 11 21 15 1 3 2 3 15 6 2 3 1 2 6 3 2 3 0 1 3 0 3 1 0 • MÈi dòng cıa b£ng mô t£ mÎt m˘c ª quy: các giá tr‡ ¶u vào a và b, giá tr‡ tính ba/bc, và giá tr‡ tr£ v∑ d, x, y. • d, x, y tr£ v∑ tr thành bÎ ba d 0 , x 0 , y 0 cıa m˘c ti∏p theo. • LÌi gÂi thı tˆc EXTENDED-EUCLID(99,78) tr£ v∑ (3, 11, 4) th‰a mãn gcd(99, 78) = 3 = 99 · ( 11) + 78 · 14. 18 / 53