Luận văn tốt nghiệp Thạc sĩ: Lý thuyết vành trong máy tính

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

Thêm vào BST

Báo xấu

23
lượt xem 5
download

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

Mục tiêu của luận văn là bước đầu giới thiệu lý thuyết về mật mã khóa công khai và những ý tưởng toán học cơ bản của lý thuyết đó. Để hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung luận văn này.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn tốt nghiệp Thạc sĩ: Lý thuyết vành trong máy tính

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM LƯƠNG THÚY NGA LÝ THUYẾT VÀNH TRONG MÁY TÍNH LUẬN VĂN TỐT NGHIỆP THẠC SĨ Thái Nguyên, năm 2015
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM LƯƠNG THÚY NGA LÝ THUYẾT VÀNH TRONG MÁY TÍNH Chuyên ngành: Đại số và Lý thuyết số Mã số:62.46.01.04 LUẬN VĂN TỐT NGHIỆP THẠC SĨ Người hướng dẫn khoa học TS. HOÀNG LÊ TRƯỜNG Thái Nguyên, năm 2015
LỜI CAM ĐOAN Tôi xin cam đoan rằng các kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Thái Nguyên, ngày 10 tháng 4 năm 2015 Người viết luận văn Lương Thúy Nga Xác nhận của khoa Toán Xác nhận của người hướng dẫn khoa học TS. Hoàng Lê Trường i
LỜI CẢM ƠN Luận văn này được hoàn thành tại trường Đại học sư phạm - Đại học Thái Nguyên. Trước khi trình bày nội dung chính của luận văn, tôi xin gửi lời cảm ơn chân thành, sâu sắc tới TS. Hoàng Lê Trường (Viện Toán học Việt Nam), thầy là người trực tiếp hướng dẫn, tận tình chỉ bảo, giúp đỡ và động viên tôi trong suốt quá trình nghiên cứu và hoàn thành luận văn. Tôi cũng xin chân thành cảm ơn ban lãnh đạo phòng sau Đại học, quý thầy cô trong khoa Toán, các bạn học viên lớp cao học Toán k21b đã tạo điều kiện thuận lợi, giúp đỡ, động viên tôi trong suốt quá trình học tập và nghiên cứu tại trường. Qua đây, tôi xin bày tỏ lòng biết ơn sâu sắc tới người thân trong gia đình, bạn bè đã luôn động viên khích lệ tôi trong suốt quá trình hoàn thành khóa học Mặc dù có nhiều cố gắng nhưng luận văn vẫn không tránh khỏi những sai sót và hạn chế. Tôi rất mong nhận được những ý kiến đóng góp quý báu của thầy cô và bạn bè để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn! Thái Nguyên, ngày 10 tháng 4 năm 2015 Người viết luận văn Lương Thúy Nga ii
Mục lục Lời cam đoan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Mục lục. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chương 1. Giới thiệu về mật mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Tính chia hết và ước chung lớn nhất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Số học mô-đun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1. Số học mô-đun và thay đổi mật mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.2. Thuật toán lũy thừa nhanh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3. Số nguyên tố, sự phân tích duy nhất và trường hữu hạn . . . . . . . . . . . . . . . . . . 15 1.4. Lũy thừa và căn nguyên thủy của trường hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5. Thuật toán mã hóa đối xứng và không đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.5.1. Thuật toán mã hóa đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.5.2. Các chương trình mã hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.5.3. Mã hóa đối xứng của khối mã hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.5.4. Các ví dụ về thuật toán mã hóa đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.5.5. Dãy bit ngẫu nhiên và thuật toán mã hóa đối xứng. . . . . . . . . . . . . . . . . . . 28 1.5.6. Thuật toán mã hóa bất đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 iii
Chương 2. Logarit rời rạc và Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.1. Các bài toán logarit rời rạc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.2. Trao đổi khóa Diffie-Hellman. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3. Hệ thống mật mã khóa công khai ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.4. Tổng quan về lý thuyết nhóm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.5. Bài toán logarit rời rạc khó như thế nào?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.6. Thuật toán gặp gỡ cho bài toán DLP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.7. Định lý thặng dư Trung Hoa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.8. Các thuật toán Pohlig-Hellman. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.9. Vành, vành thương, vành đa thức, và trường hữu hạn . . . . . . . . . . . . . . . . . . . . 56 2.9.1. Tổng quan về lý thuyết của vành . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.9.2. Quan hệ chia hết và vành thương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.9.3. Vành đa thức và thuật toán Euclid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.9.4. Thương của vành đa thức và trường hữu hạn của cấp lũy thừa nguyên tố . 64 Trích dẫn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 iv
MỞ ĐẦU Mật mã khóa công khai cho phép hai người trao đổi thông tin bí mật, ngay cả khi họ chưa bao giờ gặp nhau và chỉ có thể giao tiếp thông qua một kênh thông tin không an toàn bị theo dõi bởi kẻ thù của họ. Trong hàng nghìn năm trước đó, tất cả các mã và thuật toán mã hóa đều dựa trên giả định Bob và Alice cố gắng để trao đổi một khóa bí mật mà đối thủ của họ Eve không biết. Bob sử dụng khóa bí mật để mã hóa thông điệp của mình. Alice sẽ sử dụng khóa bí mật tương tự để giải mã thông điệp đó. Eve không biết khóa bí mật nên cô không thực hiện được việc giải mã. Một bất lợi của hệ thống mã hóa bí mật là Bob và Alice cần trao đổi khóa bí mật trước khi họ bắt đầu mã hóa và giải mã thông điệp. Trong những năm 1970, một ý tưởng đáng kinh ngạc về mật mã khóa công khai bùng nổ. Việc tạo ra các mật mã khóa công khai bởi bởi Diffie và Hellman vào năm 1976 và những phát minh tiếp theo của hệ thống mật mã khóa công khai RSA bởi Rivest, Shamir và Adleman năm 1978 là sự kiện bước ngoặt trong lịch sử của thông tin liên lạc bí mật. Trong một hệ thống mật mã khóa công khai, Alice có hai khóa là khóa công khai Kpup và khóa riêng Kpri . Alice công khai khóa Kpup của cô ấy và Adam, Bob, Carl và mọi người đều có thể sử Kpup để mã hóa thông điệp, sau đó gửi thông điệp đã mã hóa cho Alice. Ý tưởng cơ bản của mật mã khóa công khai là mặc dù tất cả mọi người trên thế giới đều biết Kpup và có thể sử dụng Kpup để mã hóa thông điệp nhưng chỉ Alice biết khóa riêng Kpri mới có thể giải mã thông điệp. Bob có thể gửi một thông điệp mã hóa cho Alice ngay cả khi họ không bao giờ được tiếp xúc trực tiếp. Mật mã khóa công khai dựa trên nhiều lĩnh vực của toán học, trong đó đặc biệt là lý thuyết số và đại số trừu tượng (nhóm, vành, trường...). Mục tiêu của luận văn là bước đầu giới thiệu lý thuyết về mật mã khóa công khai và những ý tưởng toán học cơ bản của lý thuyết đó. Luận văn được chia làm hai chương. Trong chương một, chúng tôi trình bày một số kiến thức cơ sở về tính chia hết, ước chung lớn nhất, môđun số học, số nguyên tố, phân tích duy nhất, lũy thừa và căn nguyên thủy trong trường hữu hạn, mật mã đối xứng và bất đối xứng... Đây là những công cụ cơ bản dùng cho các định nghĩa và chứng minh ở chương hai. Chương hai được dành để trình bày về mật mã khóa công khai với các bài toán logarit rời rạc và bài toán trao đổi khóa Deffine-Hellman. Trong phần này chúng tôi còn giới thiệu về hệ thống mật mã khóa công khai ElGamal, thuật toán Pohlig-Hellman và thuật toán gặp gỡ... Phần cuối của chương chúng tôi trình bày lại một số tính chất vành, vành thương, vành đa thức và trường hữu hạn cùng với các bài toán về định lí 1
thặng dư Trung Hoa. Vì điều kiện thời gian có hạn nên luận văn vẫn còn nhiều những thiếu sót. Tác giả mong nhận được sự góp ý của thầy cô, các bạn học viên , độc giả quan tâm để luận văn được hoàn thiện hơn. Thái Nguyên, ngày 10 tháng 4 năm 2015 Người viết luận văn Lương Thúy Nga 2
Chương 1 Giới thiệu về mật mã Nhiều ngành mật mã học hiện đại được xây dựng trên cơ sở nền móng của đại số và lý thuyết số. Vì vậy trước khi tìm hiểu lý thuyết mật mã, chúng ta cần phát triển một số công cụ quan trọng. Trong chương một, chúng ta bắt đầu sự phát triển này bởi việc mô tả và chứng minh các kết quả cơ bản từ đại số và lý thuyết số. 1.1. Tính chia hết và ước chung lớn nhất Ở mức độ cơ sở nhất, Lý thuyết số là việc nghiên cứu về các số tự nhiên 1, 2, 3, 4, 5, 6, · · · , hay tổng quát hơn là nghiên cứu về các số nguyên · · · , −5, −4, −3, −2, −1, 0, 1, 2, 3, 4, 5, · · · Tập hợp các số nguyên được ký hiệu là Z. Các số nguyên có thể cộng, trừ và nhân theo cách thông thường, và thỏa mãn tất cả các tính chất thông thường của số học (tính chất giao hoán, tính chất kết hợp, tính chất phân phối,..). Tập hợp các số nguyên với các tính chất của phép cộng và phép nhân là một ví dụ về vành. Nếu a và b là số nguyên, ta có thể cộng a + b, trừ a − b và nhân a · b. Trong mỗi trường hợp, chúng ta được kết quả là một số nguyên. Tuy nhiên, nếu chúng ta muốn kết quả là số nguyên, chúng ta không thể luôn luôn chia một số nguyên bởi số nguyên khác. Ví dụ, chúng ta không thể chia 3 bởi 2, vì không có số nguyên bằng 32 . Từ đó dẫn đến các khái niệm cơ bản của tính chia hết. Định nghĩa 1.1.1. Cho a và b là số nguyên với b 6= 0. Ta nói rằng b chia hết a, hay a được chia hết bởi b, nếu có một số nguyên c sao cho a = bc. Ta viết b | a thay cho b chia hết a. Nếu b không chia hết a, thì ta viết b - a. 3
Ví dụ 1.1.2. Ta có 5 | 20, vì 20 = 5 · 4, 6 - 20, vì 20 = 6 · 3 + 2, vì vậy 20 không phải là bội của 6. Nhận xét 1.1.3. Mỗi số nguyên đều được chia hết bởi 1. Những số nguyên được chia hết bởi 2 được gọi là số chẵn, và những số nguyên không được chia hết bởi 2 được gọi là số lẻ. Mệnh đề 1.1.4. Cho a, b, c là số nguyên. Khi đó, các mệnh đề sau là đúng. 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). Chứng minh. 1. Vì a | b và b | c nên tồn tại a1 ∈ Z và b1 ∈ Z sao cho b = aa1 và c = bb1 . Ta có c = (aa1 )b1 = a(a1 b1 ), do đó a | c. 2. Vì a | b và b | a nên tồn tại a1 , b1 ∈ Z sao cho b = aa1 và a = bb1 . Ta có b = (bb1 )a1 = b(b1 a1 ). Do đó a1 b1 = 1 và a1 = b1 = ±1. Vậy a = ±b. 3. Vì a | b và b | c nên tồn tại a1 , a2 ∈ Z sao cho b = aa1 và c = aa2 . Do đó b + c = a(a1 + a2 ) và b − c = a(a1 − a2 ). Vậy a | (b + c) và a | (b − c). Định nghĩa 1.1.5. Ước chung của hai số nguyên a và b là số nguyên dương d chia hết cả a và b. Ước chung lớn nhất của a và b là số nguyên dương lớn nhất d sao cho d | a và d | b. Ước chung lớn nhất của a và b được kí hiệu là gcd(a, b) hay (a, b). (Nếu a và b bằng 0, thì gcd(a, b) không xác định.) Ví dụ 1.1.6. Ước chung lớn nhất của 12 và 18 là 6.Tương tự ta có, ước chung lớn nhất của 748 và 2024 là 24. Một cách kiểm tra là liệt kê tất cả các ước nguyên dương của 748 và 2024. Ước của 748 = {1, 2, 4, 11, 17, 22, 34, 44, 68, 187, 374, 748}. Ước của 2024 = {1, 2, 4, 8, 11, 22, 23, 44, 46, 88, 92, 184, 253, 506, 1012, 2024}. Kiểm tra hai dãy trên, ta thấy ước chung lớn nhất của 748 và 2024 là 44. Từ ví dụ này ta thấy, đây không phải là phương pháp hiệu quả. Nếu cần tính ước chung lớn nhất của các số lớn, ta sẽ phải tìm phương pháp khác hiệu quả hơn. Chìa khóa để tìm thuật toán hiệu quả hơn cho việc tính ước chung lớn nhất là phép chia có dư. Do đó nếu a và b là số nguyên dương và nếu chia a bởi b, chúng ta sẽ được thương q và số dư r, phần dư r nhỏ hơn b. Ví dụ 230 được chia bởi 17, ta được thương là 13 với số dư là 9, tức là 230 = 17 · 13 + 9, với số dư 9 nhỏ thực sự hơn số chia 17. 4
Định nghĩa 1.1.7. (Thuật toán chia) Cho a và b là hai số nguyên dương. a được chia bởi b có thương q và số dư r nghĩa là a=b·q+r với 0 ≤ r < b. Giá trị của q và r là duy nhất được xác định bởi a và b. Định lý 1.1.8. (Thuật toán Euclid). Cho a và b là số nguyên dương với a ≥ b. Thuật toán dưới đây tính gcd(a, b) trong một số hữu hạn bước. Bước 1: Cho r0 = a và r1 = b. Bước 2: Đặt i = 1. Bước 3: Chia ri−1 bởi ri nhận được thương qi và số dư ri+1 , ri−1 = ri qi + ri+1 với 0 ≤ ri+1 < ri . Bước 4: Nếu số dư ri+1 = 0, thì ri = gcd(a, b) và thuật toán kết thúc. Bước 5: Nếu ri+1 > 0, ta đặt i = i + 1 và bắt đầu bước 3. Các bước của phép chia được thực hiện nhiều nhất 2 log2 (b) + 1 lần. Chứng minh. Thuật toán Euclid bao gồm một dãy của phép chia với dư được minh họa như sau (ta đặt r0 = a và r1 = b). a = b · q1 + r2 với 0 ≤ r2 < b, b = r2 · q2 + r3 với 0 ≤ r3 < r2 , r2 = r3 · q3 + r4 với 0 ≤ r4 < r3 , r3 = r4 · q4 + r5 với 0 ≤ r5 < r4 , .. .. . . rt−2 = rt−1 · qt−1 + rt với 0 ≤ rt < rt−1 , rt−1 = rt · qt . Thì rt = gcd(a, b). Bảng 1.1: * Giá trị ri giảm dần, và ngay sau khi ri bằng 0 thì thuật toán kết thúc, điều này chứng minh rằng thuật toán kết thúc sau hữu hạn bước. Hơn nữa, tại mỗi lần lặp lại bước 3, ta có một phương trình có dạng ri−1 = ri · qi + ri+1 . Phương trình này suy ra rằng bất kỳ ước chung của ri−1 và ri đều là ước của ri+1 , tương tự ta cũng có bất kỳ ước chung của ri và ri+1 cũng là ước của ri−1 . Do đó gcd(ri−1 , ri ) = gcd(ri , ri+1 ) với mọi i ∈ N Tuy nhiên, như đã nói ở trên, cuối cùng chúng ta cũng có một ri = 0. Giả sử rt+1 = 0 khi đó rt−1 = rt · qt , vì vậy gcd(rt−1 , rt ) = gcd(rt · qt , rt ) = rt . 5
Ta cần chứng minh số dư cuối cùng khác không trong thuật toán Euclid bằng ước chung lớn nhất của a và b. Vì giá trị ri là giảm dần, và r1 = b. Do đó thuật toán sẽ kết thúc tại nhiều nhất là b bước. Ta thấy điều ràng buộc trên là không xác thực. Vì sau mỗi lần lặp lại bước 3, giá trị của ri giảm ít nhất một nửa. Nói cách khác, ta có bổ đề sau. Bổ đề: ri+2 < 12 ri với mọi i ∈ N Chứng minh. Để chứng minh bổ đề này, ta cần xem xét hai trường hợp. Trường hợp 1: ri+1 ≤ 12 ri . Vì giá trị ri giảm dần, nên 1 ri+2 < ri+1 ≤ ri . 2 Trường hợp 2: ri+1 > 12 ri Vì giá trị của ri+1 > 12 ri nên ri = ri+1 · 1 + ri+2 . Do đó ri+2 = ri − ri+1 < ri − 12 ri = 12 ri . Ta đã chứng minh được bổ đề trên là ri+2 < 12 ri với mọi i ∈ N. Áp dụng bổ đề này lặp đi lặp lại, ta có r2k+1 < 21 r2k−1 < 41 r2k−3 < 18 r2k−5 < · · · < 1 r 2k 1 = 1 2k b. Do đó, nếu 2k ≥ b, thì r2k+1 < 1, suy ra r2k+1 = 0 và thuật toán kết thúc. Giá trị của rt+1 = 0, vì vậy ta có t + 1 ≤ 2k + 1, và do đó t ≤ 2k. Thêm vào đó, có t phép chia, vì vậy thuật toán Euclid kết thúc sau 2k lần lặp lại. Chọn số k nhỏ nhất sao cho 2k ≥ b > 2k−1 , thì: số lần lặp lại ≤ 2k = 2(k − 1) + 2 < 2 log2 (b) + 2, từ đó định lý được chứng minh. Chúng ta cùng minh họa thuật toán Euclid bằng một ví dụ. Ví dụ 1.1.9. Tìm gcd(2024, 748) sử dụng thuật toán Euclid, đó là việc lặp đi lặp lại nhiều lần phép chia có dư. 2024 = 748 · 2 + 528, 748 = 528 · 1 + 220, 528 = 220 · 2 + 88, 220 = 88 · 2 + 44, 88 = 44 · 2 + 0. Vậy gcd(2024, 748) = 44. 6
Định lý 1.1.10. (Thuật toán Euclid mở rộng). Cho a và b là số nguyên dương. Phương trình au + bv = gcd(a, b) luôn tìm được nghiệm nguyên u và v. Nếu (u0 , v0 ) là nghiệm bất kỳ, thì mỗi nghiệm của phương trình au + bv = gcd(a, b) đều có dạng b·k a·k u = u0 + và v = v0 − với k ∈ Z gcd(a, b) gcd(a, b) . Chứng minh. Từ bảng 1.1, ta có thể giải quyết dòng đầu tiên với r2 = a − b · q1 và thay thế nó vào dòng thứ hai được b = (a − b · q1 ) · q2 + r3 , vì vậy r3 = −aq2 + b(1 + q1 q2 ). Thay vào biểu thức tiếp theo với r2 và r3 vào dòng thứ ba ta được a − b · q1 = (−a · q2 + b · (1 + q1 q2 ))q3 + r4 . Sau khi tính toán ta được r4 = a · (1 + q2 q3 ) − b · (q1 + q2 + q1 · q2 · q3 ). Điểm quan trọng là r4 = a · u + b · v, với u và v là số nguyên. Tiếp tục quá trình này, ở mỗi bước ta tìm được ri là tổng một bội của a và một bội của b. Cuối cùng, ta đặt rt = a.u + b.v, với số nguyên u và v. Nhưng rt = gcd(a, b), do đó hoàn thành việc chứng minh phần đầu tiên của định lý. Nếu (u0 , v0 ) là nghiệm nguyên bất kỳ của phương trình au + bv = gcd(a, b) và b·k a·k u = u0 + và v = v0 − với k ∈ Z gcd(a, b) gcd(a, b) thì ta có b·k a·k a · (u0 + ) + b · (v0 − ) = a · u0 + b · v0 = gcd(a, b). gcd(a, b) gcd(a, b) Do đó b·k a·k u = u0 + và v = v0 − với k ∈ Z gcd(a, b) gcd(a, b) cũng là nghiệm của phương trình au + bv = gcd(a, b). Ví dụ 1.1.11. Quay về ví dụ 1.1.9, ta sử dụng thuật toán Euclid để tính gcd(2024, 748) như sau: 7
2024 = 748 · 2 + 528, 748 = 528 · 1 + 220, 528 = 220 · 2 + 88, 220 = 88 · 2 + 44, 88 = 44 · 2 + 0. Vậy gcd(2024, 748) = 44. Đặt a = 2024 và b = 748, vì vậy dòng đầu tiên nói rằng 528 = a − 2b. Thay thế điều này vào dòng thứ hai ta được b = (a − 2b) · 1 + 220 vì vậy 220 = −a + 3b. Tiếp tục thay thế các biểu thức 528 = a − 2b và 220 = −a + 3b vào dòng thứ ba ta được a − 2b = (−a + 3b) · 2 + 88 vì vậy 88 = 3a − 8b. Cuối cùng, thay biểu thức 220 = −a + 3b và 88 = 3a − 8b vào dòng cuối cùng ta được −a + 3b = (3a − 8b) · 2 + 44 vì vậy 44 = −7a + 19b. Nói cách khác, −7 · 2024 + 19 · 748 = 44 = gcd(2024, 748). Từ đó, chúng ta đã tìm thấy thấy một cách viết gcd(a, b) như một biểu thức tuyến tính của các số nguyên a và b, đó là kết quả đơn giản với nhiều hệ quả quan trọng. Trường hợp đặc biệt của thuật toán Euclid mở rộng là ước chung lớn nhất của a và b bằng 1. Định nghĩa 1.1.12. Cho a và b là số nguyên. Chúng ta nói rằng a và b là nguyên tố cùng nhau nếu gcd(a, b) = 1. Tổng quát hơn, phương trình A · u + B · v = gcd(A, B) có thể đưa về trường hợp các số nguyên tố cùng nhau bằng cách chia cả hai vế cho gcd(A, B). Do đó A B ·u+ · v = 1. gcd(A, B) gcd(A, B) 8
Với A B a= và b= gcd(A, B) gcd(A, B) là nguyên tố cùng nhau và thỏa mãn a · u + b · v = 1. Ví dụ 1.1.13. Chúng ta đã tìm được ước chung lớn nhất của 2024 và 748 là 44 thỏa mãn −7 · 2024 + 19 · 748 = 44. Chia cả hai vế cho 44 , ta được −7 · 46 + 19 · 17 = 1. Do đó, 2024/44 = 46 và 748/44 = 17 là nguyên tố cùng nhau, với u = −7 và v = 19 là hệ số của một biểu thức tuyến tính của 46 và 17. 1.2. Số học mô-đun Chúng ta đã gặp ”đồng hồ số học” ở trường lớp, khi đến số 12, thì số tiếp theo là số 1. Từ đó dẫn đến phương trình 6+9=3 và 2 − 3 = 11. Nhìn điều này lạ, nhưng nó sử dụng đúng với đồng hồ số học, từ ví dụ 11 : 00 là 3 giờ trước của 2 : 00. Vì vậy lần đầu tiên ta tính được 2 − 3 = −1, sau đó cộng thêm 12 để được câu trả lời. Tương tự, 9 giờ sau 6 : 00 là 3 : 00, vì 6 + 9 − 12 = 3. Định lý về đồng dư là một phương pháp trong lý thuyết số, cái mà dựa trên ý tưởng đơn giản của đồng hồ số học. Định nghĩa 1.2.1. Cho m ≥ 1 là một số nguyên. Ta nói rằng số nguyên a và b là đồng dư môđun m, nếu hiệu a − b được chia hết bởi m. Ta viết a≡b (mod m) để chỉ ra a và b là đồng dư môđun m. Số m được gọi là môđun. Trong ví dụ về đồng hồ số học, chúng ta có thể viết như quan hệ đồng dư sử dụng môđun m = 12, như 6 + 9 = 15 ≡ 3 (mod 12) và 2 − 3 = −1 ≡ 11 (mod 12). Ví dụ 1.2.2. Ta có 17 ≡ 7 (mod 5) vì 5 chia hết 10 = 17 − 7. Mặt khác, 19 6= 6 (mod 11) vì 11 không chia hết 13 = 19 − 6. 9
Chú ý rằng các số thỏa mãn a ≡ 0 (mod m) là các số được chia hết bởi m hay là bội của m. Mệnh đề 1.2.3. Cho m ≥ 1 là một số nguyên. Khi đó các mệnh đề sau là đúng. 1. Nếu a1 ≡ a2 (mod m) và b1 ≡ b2 (mod m), khi đó chúng ta có a1 ± b1 ≡ a2 ± b2 (mod m) và a1 .b1 ≡ a2 .b2 (mod m). 2. Cho a là số nguyên, ta có a.b ≡ 1 (mod m) với một số b khi và chỉ khi gcd(a, m) = 1. Nếu số nguyên b tồn tại thì ta nói rằng b là nghịch đảo của a môđun m. Chứng minh. 1. Vì a1 ≡ a2 (mod m) và b1 = b2 (mod m), nên m | (a1 − a2 ) và m | (b1 − b2 ). Do đó m | ((a1 − a2 ) ± (b1 − b2 )) và m | ((a1 ± b1 ) − (a2 ± b2 )). Vậy (a1 ± b1 ) ≡ (a2 ± b2 ) (mod m). Vì a1 ≡ a2 (mod m) và b1 = b2 (mod m), nên m | (a1 − a2 ) và m | (b1 − b2 ). Khi đó tồn tại u, v ∈ Z sao cho a1 = b1 + um và a2 = b2 + vm. Do đó a1 a2 = b1 b2 + m(b1 v + b2 u) + m2 uv và m | (a1 a2 − b1 b2 ) = m(b1 v + b2 u) + m2 uv. Vậy a1 a2 ≡ b1 b2 (mod m). 2. Giả sử gcd(a, m) = 1, thì tồn tại số nguyên u, v sao cho au + mv = 1. Do đó au − 1 = −mv và m | (au − 1), vì vậy từ định nghĩa ta có au ≡ 1 (mod m). Nói cách khác, ta có thể đặt b = u. Ngược lại, giả sử a có một nghịch đảo môđun m, tức là a.b ≡ 1 (mod m). Điều đó có nghĩa là m | (ab − 1), khi đó tồn tại số nguyên c sao cho ab − 1 = cm, do đó ab + (−c)m = 1. Vậy gcd(a, m) = 1. Định lý đã chứng minh được a có một nghịch đảo môđun m khi và chỉ khi gcd(a, m) = 1. Ví dụ 1.2.4. Ta có m = 5 và a = 2. Rõ ràng gcd(2, 5) = 1, vì vậy tồn tại một nghịch đảo của 2 môđun 5. Nghịch đảo của 2 môđun 5 là 3 vì 2 · 3 ≡ 1 (mod 5), vì vậy 2−1 ≡ 3 (mod 5). Tương tự gcd(4, 15) = 1 vì vậy tồn tại 4−1 môđun 15. Ta có 4 · 4 ≡ 1 (mod 15), vì vậy 4 là nghịch đảo của riêng nó môđun 15. Chúng ta có thể làm việc với phân số a/d môđun m với điều kiện mẫu số nguyên tố với m. Ví dụ, chúng ta có thể tính 5/7 modun 11. Lưu ý rằng 7 · 8 ≡ 1 (mod 11), vì vậy 7−1 = 8 (mod 11). Do đó ta có 5 = 5 · 7−1 ≡ 5 · 8 ≡ 40 ≡ 7 (mod 11). 7 Chúng ta tiếp tục phát triển lý thuyết số học môđun. Nếu a chia m có thương q và số dư r, nó có thể được viết như là 10
a = mq + r với 0 ≤ r < m. Điều này chỉ ra rằng a ≡ r (mod m) với những số nguyên r ở giữa 0 và m − 1, vì vậy nếu chúng ta muốn làm việc với các số nguyên môđun m, chúng ta chỉ cần sử dụng các số nguyên 0 ≤ r < m. Từ đó ta có định nghĩa sau. Định nghĩa 1.2.5. Ta viết Z/mZ = {0, 1, 2, · · · , m − 1} và gọi Z/mZ là vành các số nguyên môđun m. Bất cứ lúc nào ta cũng có thể thực hiện cộng hoặc nhân trong Z/mZ, và chia kết quả cho m và lấy số dư để có được một phần tử trong Z/mZ. Nhận xét 1.2.6. Nếu chúng ta biết về lý thuyết vành, chúng ta sẽ thừa nhận rằng Z/mZ là vành thương của Z bởi ideal chính mZ, và các số 0, 1, 2, · · · , m − 1 là đại diện cho các lớp đồng dư bao gồm các phần tử của Z/mZ. Định nghĩa 1.2.7. Mệnh đề 1.2.3(2) nói với chúng ta rằng a có một nghịch đảo môđun m khi và chỉ khi gcd(a, m) = 1. Số mà có nghịch đảo được gọi là khả nghịch. Chúng ta kí hiệu tập tất cả các phần tử khả nghịch bởi (Z/mZ)∗ = {a ∈ Z/mZ : gcd(a, m) = 1} = {a ∈ Z/mZ : a có một nghịch đảo modun m}. Tập (Z/mZ)∗ được gọi là nhóm các phần tử khả nghịch môđun m. Chú ý rằng nếu a1 và a2 là khả nghịch môđun m, thì a1 a2 cũng vậy. Nhưng nếu cộng hai phần tử khả nghịch, ta có thể không được một phần tử khả nghịch. Ví dụ 1.2.8. Bảng sau đây minh họa hoàn chỉnh phép cộng và nhân trong vành Z/5Z. + 0 1 2 3 4 · 0 1 2 3 4 0 0 1 2 3 4 0 0 0 0 0 0 1 1 2 3 4 0 1 0 1 2 3 4 2 2 3 4 0 1 2 0 2 4 1 3 3 3 4 0 1 2 3 0 3 1 4 2 4 4 0 1 2 3 4 0 4 3 2 1 Bảng 1.2: Bảng phép cộng và phép nhân mô-đun 5 Ví dụ 1.2.9. Nhóm các phần tử khả nghịch môđun 24 là (Z/24Z)∗ = {1, 5, 7, 11, 13, 17, 19, 23}. Phép nhân trong (Z/24Z)∗ được minh họa trong bảng sau: 11
· 1 5 7 11 13 17 19 23 1 1 5 7 11 13 17 19 23 5 5 1 11 7 17 13 23 19 7 7 11 1 5 19 23 13 17 11 11 7 5 1 23 19 17 13 13 13 17 19 23 1 5 7 11 17 17 13 23 19 5 1 11 7 19 19 23 13 17 7 11 1 5 23 23 19 17 13 11 7 5 1 Bảng 1.3: Nhóm các phần tử khả nghịch mô-đun 24 Ta có định nghĩa sau. Định nghĩa 1.2.10. Hàm số Euler φ là hàm số φ(m) được định nghĩa bởi quy tắc φ(m) = |(Z/mZ)∗ | = |{0 ≤ a < m | gcd(a, m) = 1}|. Ví dụ φ(24) = 8 và φ(7) = 6. Ví dụ 1.2.11. Nhóm các phần tử khả nghịch môđun 7 là (Z/7Z)∗ = {1, 2, 3, 4, 5, 6} vì mỗi số nguyên ở giữa 1 và 6 đều nguyên tố với 7. Phép nhân trong (Z/7Z)∗ được minh họa trong bảng sau. · 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 4 6 1 3 5 3 3 6 2 5 1 4 4 4 1 5 2 6 3 5 5 3 1 6 4 2 6 6 5 4 3 2 1 Bảng 1.4: Nhóm các phần tử khả nghịch mô-đun 7 1.2.1. Số học mô-đun và thay đổi mật mã Nhớ lại rằng Caesar (hay thay đổi) mật mã học trong phần trước hoạt động bằng cách chuyển mỗi chữ cái trong bảng chữ cái bằng một số cố định của các thư. Ví dụ gán a b c d e f g h i j k l C I S Q V N F O W A X M 12
m n o p q r s t u v w x y z T G U H P B K L R E Y D Z J Bảng 1.5: Bảng mã hóa đơn giản Trong đó dòng thứ hai của bảng đã được mã hóa. Chúng ta có thể mô tả một mật mã toán học bằng cách gán mỗi số cho mỗi thư như ở bảng sau a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y z 13 14 15 16 17 18 19 20 21 22 23 24 25 Ví dụ chúng ta mã hóa như sau d a i s o v a l y t h u y e t s o 3 0 8 18 14 21 0 11 24 19 7 20 25 4 19 18 14 Sau khi có mật mã như vậy cùng với sự thay đổi k có một chữ cái ban đầu tương ứng với một số p và gán nó vào thư bản mã tương ứng với số p + k (mod 26). Số lượng thay đổi phải thỏa mãn cả hai khóa mã hóa và khóa giải mã. Mã hóa được đưa ra bởi công thức (Thư bản mã )=(Thư ban đầu)+(Khóa bí mật) (mod 26), và giải mã bằng cách chuyển theo hướng ngược lại, (Thư ban đầu)=(Thư bản mã)-(Khóa bí mật) (mod 26). Ngắn gọn hơn, nếu chúng ta để p= Thư ban đầu, c= Thư bản mã, k= Khóa bí mật, thì ta có c ≡ p + k (mod 26) và p ≡ c − k (mod 26) . | {z } | {z } mã hóa giải hóa 1.2.2. Thuật toán lũy thừa nhanh Trong phần này chúng ta sẽ đề cập đến bài toán tính lũy thừa lớn của một số g môđun một số N , khi N có hàng trăm chữ số. Cách dễ dàng nhất để tính g A là nhân lặp đi lặp lại bởi g. Do đó 13
g1 ≡ g (mod N ), g2 ≡ g.g1 (mod N ), g3 ≡ g.g2 (mod N ), g4 ≡ g.g3 (mod N ), g5 ≡ g.g4 (mod N ), · · · Rõ ràng gA ≡ (g A ) (mod N ), tuy nhiên nếu A lớn, thì thuật toán này hoàn toàn không thực tế. Ví dụ, nếu A ≈ 21000 , thì thuật toán đó sẽ mất thời gian hơn so với ước tính tuổi của vũ trụ. Bài toán của chúng ta sẽ được áp dụng trong một số hệ thống mã hóa mà chúng ta sẽ học, ví dụ hệ thống mã hóa RSA và Difie-Hellman, vì vậy chúng ta cần tìm một cách tốt hơn để tính g A (mod m). Chúng ta có thể sử dụng việc mở rộng hệ nhị phân của số mũ A để chuyển đổi các tính toán của g A sang một loạt các bình phương và phép nhân. Ví dụ 1.2.12. Giả sử ta muốn tính 3218 (mod 1000). Bước đầu tiên là viết 218 như là tổng các lũy thừa của 2, 218 = 2 + 23 + 24 + 26 + 27 . Khi đó 3218 trở thành 3 3218 = 32+2 +24 +26 +27 3 4 = 32 · 32 · 32 · 32 · 32 . 6 7 Ta có thể dễ dàng tính các giá trị của dãy 2 3 4 3, 32 , 32 , 32 , 32 , · · · , vì mỗi số trong dãy là bình phương của số đứng trước. Bảng sau đây yêu cầu chỉ cần 7 phép nhân. i 0 1 2 3 4 5 6 7 2i 3 (mod 1000) 3 9 81 561 721 841 241 961 7 Mặc dù thực tế rằng số 32 = 3128 có một số mũ khá lớn, bởi vì mục tiếp theo trong bảng bằng bình phương của mục trước. Từ đó ta tính được 3218 (mod 1000) như sau 3 4 6 7 3218 = 32 · 32 · 32 · 32 · 32 ≡ 9 · 561 · 721 · 281 · 961 ≡ 489 (mod 1000) Khi tính tích 9 · 561 · 721 · 281 · 961, chúng ta có thể rút gọn mô-đun 1000 sau mỗi phép nhân. Vì thế chúng ta chỉ mất 11 phép nhân để tính 3218 (mod 1000), đây là một phương pháp tiếp cận tiết kiệm thời gian. Phương pháp tiếp cận chung được sử dụng trong ví dụ 1.2.12 có những tên gọi khác nhau, bao gồm thuật toán lũy thừa nhanh và thuật toán bình phương và nhân. Bây giờ chúng ta mô tả thuật toán chính thức hơn. Thuật toán lũy thừa nhanh 14