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

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

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

9 1.2. Số học mô-đun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

iii

1.5.6. Thuật toán mã hóa bất đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

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ố .

Trích dẫn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

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í

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

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

1.1. Tính chia hết và ước chung lớn nhất

việc mô tả và chứng minh các kết quả cơ bản từ đại số và lý thuyết số.

Ở 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 3 2. 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 (cid:54)= 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 (cid:45) a.

Ví dụ 1.1.2. Ta có 5 | 20, vì 20 = 5 · 4, 6 (cid:45) 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(a1b1), 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(b1a1). Do đó a1b1 = 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.

Đị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 = riqi + 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.

a = b · q1 + r2 b = r2 · q2 + r3 r2 = r3 · q3 + r4 r3 = r4 · q4 + r5 ...

rt−2 = rt−1 · qt−1 + rt

với 0 ≤ r2 < b, với 0 ≤ r3 < r2, với 0 ≤ r4 < r3, với 0 ≤ r5 < r4, ... với 0 ≤ rt < rt−1,

rt−1 = rt · qt. Thì rt = gcd(a, b).

Bảng 1.1: *

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).

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 đó

với mọi i ∈ N gcd(ri−1, ri) = gcd(ri, ri+1)

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.

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.

2 ri

với mọi i ∈ N Bổ đề: ri+2 < 1

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 ≤ 1 2ri. Vì giá trị ri giảm dần, nên

2ri

ri+2 < ri+1 ≤ ri. 1 2

2 ri.

Trường hợp 2: ri+1 > 1 Vì giá trị của ri+1 > 1

2 ri nên ri = ri+1 · 1 + ri+2. Do đó 2ri = 1 ri+2 = ri − ri+1 < ri − 1 2ri với mọi i ∈ N.

Ta đã chứng minh được bổ đề trên là ri+2 < 1

Áp dụng bổ đề này lặp đi lặp lại, ta có

2r2k−1 < 1

4r2k−3 < 1

8r2k−5 < · · · < 1

2k r1 = 1

2k b.

r2k+1 < 1

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.

Đị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

và với k ∈ Z u = u0 + v = v0 − b · k gcd(a, b) a · k 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 + q1q2).

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 + q1q2))q3 + r4.

Sau khi tính toán ta được

r4 = a · (1 + q2q3) − 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à

và với k ∈ Z u = u0 + v = v0 − b · k gcd(a, b) a · k gcd(a, b)

thì ta có

) + b · (v0 − ) = a · u0 + b · v0 = gcd(a, b). a · (u0 + b · k gcd(a, b) a · k gcd(a, b)

Do đó

và với k ∈ Z u = u0 + v = v0 − b · k gcd(a, b) a · k 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:

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 đó

· u + · v = 1. A gcd(A, B) B gcd(A, B)

Với

và b = a = A gcd(A, B) 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.

1.2. Số học mô-đun

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.

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 (cid:54)= 6 (mod 11) vì 11 không chia hết 13 = 19 − 6.

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) =

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 đó a1a2 = b1b2 + m(b1v + b2u) + m2uv và m | (a1a2 − b1b2) = m(b1v + b2u) + m2uv. Vậy a1a2 ≡ b1b2 (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 · 7−1 ≡ 5 · 8 ≡ 40 ≡ 7 (mod 11). 5 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à

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.

Z/mZ = {0, 1, 2, · · · , m − 1}

Định nghĩa 1.2.5. Ta viết

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ì a1a2 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.

+ 0

Bảng 1.2: Bảng phép cộng và phép nhân mô-đun 5

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.

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:

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}

Bảng 1.4: Nhóm các phần tử khả nghịch mô-đun 7

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.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ụ

C I

S Q V N F O W A X M

gán

m n

v w x

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ã

l m

toán học bằng cách gán mỗi số cho mỗi thư như ở bảng sau

Ví dụ chúng ta mã hóa như sau

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ó

(cid:124)

(cid:123)(cid:122) giải hóa

. và p ≡ c − k (mod 26) (cid:125) c ≡ p + k (mod 26) (cid:123)(cid:122) (cid:125) (cid:124) mã 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 gA là nhân lặp đi lặp lại bởi g. Do đó

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 ≡ (gA) (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 gA (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 gA 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

3218 = 32+23+24+26+27 = 32 · 323 · 324 · 326 · 327 .

Ta có thể dễ dàng tính các giá trị của dãy

, · · · , , 324 , 323 3, 32, 322

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

32i

561

721

841

241

961

(mod 1000)

7 phép nhân.

Mặc dù thực tế rằng số 327 = 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

≡ 9 · 561 · 721 · 281 · 961 ≡ 489 (mod 1000) · 327 · 326 · 324 3218 = 32 · 323

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

(mod N ) với 0 ≤ i ≤ r bởi bình phương liên tiếp,

(mod N ),

0 ≡ g2 (mod N ), 1 ≡ g22 (mod N ), 2 ≡ g23 ... r−1 ≡ g2r

(mod N ). Bước 1:. Tính khai triển nhị phân của A như sau A = A0 + A1 · 2 + A2 · 22 + A3 · 23 + · · · + Ar · 2r với A0, A1, · · · , Ar ∈ {0, 1}, với Ar = 1. Bước 2:. Tính lũy thừa g2i a0 ≡ g (mod N ), a1 ≡ a2 a2 ≡ a2 a3 ≡ a2 ... ar ≡ a2

Mỗi số hạng bằng bình phương của số liền trước, vì vậy có r phép nhân. Bước 3.Tính gA (mod N ) sử dụng công thức gA = gA0+A1·2+A2·22+A3·23+···+Ar·2r )A2 · · · (g2r

A0 · a1

A1 · a2

A2 · · · ar

)Ar Ar (mod N ). = gA0 · (g2)A1 · (g22 ≡ a0

Thuật toán đến đây kết thúc.

Thời gian chạy. Chúng ta chỉ cần 2r phép nhân môđun N để tính gA. Vì A ≥ 2r nên chúng ta chỉ mất nhiều nhất 2 log2(A) [1] phép nhân môđun N để tính gA. Do đó nếu A là rất lớn, ví dụ A ≈ 21000, thuật toán vẫn dễ dàng cho một máy tính để thực hiện khoảng 2000 phép nhân cần để tính toán 2A môđun N.

Vấn đề hiệu quả. Có nhiều cách khác nhau trong thuật toán bình phương và nhân có thể được thực hiện phần nào hiệu quả hơn, đặc biệt đối với việc loại bỏ sự

1.3. Số nguyên tố, sự phân tích duy nhất và trường hữu hạn

tích lũy các điều kiện tất yếu.

Trong phần 1.2, chúng ta đã đề cập đến số học mô-đun và đã chỉ ra rằng lý thuyết

số học mô-đun có ý nghĩa đối với phép cộng, trừ và nhân số nguyên m. Chúng ta chỉ có thể chia bởi a trong Z/mZ khi gcd(a, m) = 1. Nhưng nếu số m là nguyên tố thì ta có thể chia bởi mỗi phần tử khác không của Z/mZ.

Định nghĩa 1.3.1. Số p được gọi là số nguyên tố nếu p ≥ 2 và p chỉ chia hết cho 1 và

Ví dụ 1.3.2. Mười số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 trong khi số

nguyên tố thứ hàng trăm nghìn là 1299709 và thứ một triệu là 15485863. Có vô hạn

các số nguyên tố, thực tế đó đã được biết đến trong thời Hi lạp cổ đại và xuất hiện như là một định lý trong thời Euclid.

Số nguyên tố p được xác định theo những số chia p. Vì vậy mệnh đề sau đây mô tả tính chất của những số mà chia hết bởi p. Chú ý rằng mệnh đề nay là sai đối với

hợp số. Ví dụ 6 | 3 · 10 nhưng 6 không chia hết 3 hay 10.

Mệnh đề 1.3.3. Cho p là số nguyên tố, và giả sử p chia hết tích ab của hai số nguyên

a và b. Khi đó, p chia hết ít nhất một trong hai số a và b. Tổng quát, nếu p chia hết một tích của các số nguyên p | a1a2 · · · an thì p chia hết ít nhất một trong các ai. với i = 1, · · · n.

Chứng minh. Cho g = gcd(a, p), thì g | p. Vì p nguyên tố nên g = 1 hoặc g = p. Nếu g = p thì p | a, ta có điều phải chứng minh. Nếu không, g = 1 thì chúng ta tìm được

số nguyên u và v thỏa mãn au + pv = 1. Chúng ta nhân cả hai vế của phương trình

với b, ta có

abu + pbv = b.

Từ giả thiết, p chia hết tích ab, và chắc chắn p chia hết pbv, vì vậy p chia hết cả hai vế của phương trình abu + pbv = b. Do đó p chia hết b. Để chứng minh trường hợp tổng quát hơn, ta viết tích a1a2 · · · an như là a1(a2 · · · an) và áp dụng trường hợp đầu tiên với a = a1 và b = a2 · · · an. Nếu p | a1, ta có điều phải chứng minh. Nếu không, p | a2 · · · an, vì vậy ta viết a2 · · · an như là a2(a3 · · · an). Trường hợp đầu tiên nói cho chúng ta biết p | a2, hoặc p | a3 · · · an. Tiếp tục quá trình này, chúng ta tìm được ai mà chia hết bởi p.

Như một ứng dụng của mệnh đề 1.3.3, chúng ta chứng minh được mỗi số nguyên

2 · · · per

1 pe2

dương đều có một phân tích duy nhất thành tích của các số nguyên tố.

Định lý 1.3.4. (Định lý cơ bản của số học). Cho a ≥ 2 là một số nguyên, khi đó a có thể được phân tích thành tích của các số nguyên tố a = pe1 r . Hơn nữa, không kể thứ tự của các số nguyên tố thì sự phân tích này là duy nhất.

Chứng minh. Giả sử a ≥ 2 là một số nguyên, thì a phải có một ước nguyên tố , chẳng hạn là p1 và ta có a = p1a1 trong đó 1 ≤ a1 < a. Nếu a1 = 1 thì ta được a = p1 và đó là sự phân tích của a thành thừa số nguyên tố. Nếu a1 > 1 thì a1 phải có một ước nguyên tố p2, và ta có a = p1p2a2 với 1 ≤ a2 < a1. Nếu a2 = 1 thì ta được a = p1p2 là dạng phân tích của a thành tích của các số nguyên tố. Nếu a2 > 1 thì lặp lại lý luận ở trên, ta được thừa số nguyên tố p3, ... Quá trình này phải kết thúc vì ta có a > a1 > a2 > · · · nên phải có một an = 1. Vậy ta được

a = p1p2 · · · pr

là dạng phân tích của a thành tích các số nguyên tố.

Giả sử a có hai sự phân tích thành tích của các số nguyên tố,

a = p1p2p3 · · · ps = q1q2q3 · · · qt,

với pi và qj là các số nguyên tố, không nhất thiết phải phân biệt, và s không nhất thiết bằng t. Không mất tính tổng quát giả sử t ≥ s. Vì p1 | a, nên p1 | q1q2q3 · · · qt. Do đó, từ dạng tổng quát của mệnh đề 1.3.3, ta có p1 chia hết một trong các qi. Sắp xếp lại thứ tự của các qi (nếu cần thiết), chúng ta có thể giả sử p1 | q1. Nhưng p1 và q1 đều là số nguyên tố, do đó ta có p1 = q1. Giản ước hai vế của a = p1p2p3 · · · ps = q1q2q3 · · · qt, ta được

p2p3 · · · ps = q2q3 · · · qt.

Lặp lại quá trình này s lần, cuối cùng chúng ta được một phương trình có dạng

1 = qt−sqt−s+1 · · · qt. vì t ≥ s

Vì thế ta có s = t và các sự phân tích ban đầu của a là giống nhau không kể đến việc

sắp xếp lại thứ tự của các thừa số.

Nếu p là số nguyên tố, thì mỗi số khác không mô-đun p có một nghịch đảo nhân

môđun p. Điều này có nghĩa là khi chúng ta đề cập đến các số khác không môđun p

với p là số nguyên tố, chúng ta không chỉ cộng, trừ, nhân mà chúng ta còn có thể chia

bởi các số khác không, cũng giống như chia các số thực.

Mệnh đề 1.3.5. Cho p là số nguyên tố. Khi đó, mỗi phần tử a khác không trong Z/pZ có một nghịch đảo nhân, nghĩa là có một số b thỏa mãn

ab ≡ 1 (mod p).

Chúng ta kí hiệu giá trị b này bởi a−1 (mod p), hay nếu p đã được xác định thì ta chỉ cần kí hiệu bằng a−1.

Chứng minh. Mệnh đề này là trường hợp đặc biệt của mênh đề 1.2.3 sử dụng số nguyên tố môđun p, vì nếu a ∈ Z/pZ là khác không thì gcd(a, p) = 1.

Nhận xét 1.3.6. Thuật toán Euclid đưa ra cho chúng ta một phương pháp hiệu quả cho việc tính a−1 (mod p). Chúng ta chỉ đơn giản là giải các phương trình

au + pv = 1 với số nguyên u và v,

khi đó u = a−1 (mod p), thay thế cho việc tính a−1 (mod p). Định nghĩa 1.2.7 có thể được điều chỉnh lại bằng cách nói rằng nếu p nguyên tố, thì

(Z/pZ)∗ = {1, 2, 3, 4, · · · , p − 1}.

Nói cách khác, khi bỏ đi phần tử 0 từ Z/pZ, thì các phần tử còn lại là khả nghịch và đóng kín đối với phép nhân.

Định nghĩa 1.3.7. Nếu p là số nguyên tố, thì Z/pZ các số nguyên môđun p cùng với phép cộng, trừ, nhân và quy tắc chia là một ví dụ về trường. Chúng ta biết rằng một

trường là một vành (giao hoán) trong đó mỗi phần tử khác không đều có nghịch đảo nhân, ví dụ trường số thực R, trường các số hữu tỉ Q, và trường số phức C. Trường Z/pZ các số nguyên môđun p chỉ có hữu hạn phần tử. Trường Z/pZ là trường hữu hạn và thường được kí hiệu bởi Fp. Do đó Fp và Z/pZ thực sự chỉ là hai ký hiệu khác nhau cho cùng một đối tượng [2]. Từ giờ trở đi ta sẽ kí hiệu Fp là trường hữu hạn của p phần tử. Tương tự, ta viết F∗ p thay thế cho nhóm các phần tử khả nghịch (Z/pZ)∗.

1.4. Lũy thừa và căn nguyên thủy của trường hữu hạn

Nhận xét 1.3.8. Mặc dù Z/pZ và Fp được sử dụng để kí hiệu cho cùng một khái niệm, nhưng sự bằng nhau của các phần tử trong hai tập hợp này lại khác nhau. Cho a, b ∈ Fp, sự bằng nhau của a và b được kí hiệu bởi a = b, trong khi a, b ∈ Z/pZ, sự bằng nhau của a và b được kí hiệu bởi quan hệ đồng dư môđun p là a ≡ b (mod p).

Ứng dụng của trường hữu hạn trong lý thuyết mật mã là nâng các phần tử của Fp lên lũy thừa mức cao hơn. Trong phần này, chúng ta đề cập đến lũy thừa trong Fp, nhờ có một chứng minh kết quả cơ bản của Fermat, và đó là một tính chất quan trọng của nhóm các phần tử khả nghịch (Fp)∗.

Ví dụ 1.4.1. Chúng ta bắt đầu với một ví dụ đơn giản. Bảng danh sách các lũy thừa

11 ≡ 1 21 ≡ 2 31 ≡ 3 41 ≡ 4 51 ≡ 5 61 ≡ 6

12 ≡ 1 22 ≡ 4 32 ≡ 2 42 ≡ 2 52 ≡ 4 62 ≡ 1

13 ≡ 1 23 ≡ 1 33 ≡ 6 43 ≡ 1 53 ≡ 6 63 ≡ 6

14 ≡ 1 24 ≡ 2 44 ≡ 4 44 ≡ 4 54 ≡ 2 64 ≡ 1

15 ≡ 1 25 ≡ 4 35 ≡ 5 45 ≡ 2 55 ≡ 3 65 ≡ 6

16 ≡ 1 26 ≡ 1 36 ≡ 1 46 ≡ 1 56 ≡ 1 66 ≡ 1

Bảng 1.6: Lũy thừa của các số modun 7

của 1, 2, 3, 4, 5, 6 môđun nguyên tố 7.

Ta thấy trong bảng 1.6, các cột bên phải bao gồm toàn bộ một. Nói cách khác

a6 ≡ 1 (mod 7) với mỗi a = 1, 2, 3, · · · 6.

Điều này có thể không đúng với mọi giá trị của a, vì nếu a là bội của 7, thì an ≡ 0 (mod 7). Mặt khác, nếu a không được chia hết bởi 7, thì a6 là đồng dư với 1, với các

giá trị của a là 1, 2, · · · , 6 mô-đun 7. Do đó

  1

(mod 7) nếu 7 (cid:45) a, a6 ≡

 0

(mod 7) nếu 7 | a.

Định lý 1.4.2. (Định lý Fermat). Cho p là số nguyên tố và a là số nguyên bất kì. Ta có

  1

(mod p) nếu p (cid:45) a, ap−1 ≡

 0

(mod p) nếu p | a.

Chứng minh. Nếu p | a, thì mọi lũy thừa của a đều được chia hết bởi p. Vì vậy chúng ta chỉ cần chứng minh trường hợp p (cid:45) a. Đặt S = {ka (mod p) | k = 1, · · · p − 1}. Ta thấy S có p − 1 phần tử phân biệt khác không. Thật vậy, lấy hai số bất kì trong dãy trên là ja (mod p) và ka (mod p), và giả sử rằng chúng bằng nhau. Điều này có nghĩa

là

ja ≡ ka (mod p) và vì vậy (j − k)a ≡ 0 (mod p).

Do đó p chia hết tích (j − k)a. Từ mệnh đề 1.3.3, ta thấy p chia hết j − k hoặc p chia

hết a. Tuy nhiên chúng ta đã giả sử rằng p không chia hết a, do đó p chia hết j − k. Vì cả j và k đều nằm giữa 1 và p − 1, nên hiệu j − k nằm giữa −(p − 2) và p − 2 và

được chia hết bởi p. Điều này chứng minh j − k = 0, tức là ja = ka. Vậy S có p − 1

phần tử phân biệt khác không và S ⊆ {1, 2, · · · p − 1}.

Vì S có p − 1 phần tử và tập {1, 2, · · · p − 1} nên S = {1, 2, · · · p − 1}. Nếu nhân tất cả các số của dãy a, 2a, 3a, · · · , (p − 1)a với nhau và quy về môđun p. Điều này giống

như nhân tất cả các số 1, 2, 3, · · · , p − 1 với nhau môđun p, vì vậy chúng ta có một

quan hệ đồng dư

a · 2a · 3a · · · (p − 1)a ≡ 1 · 2 · 3 · · · (p − 1) (mod p).

Số a xuất hiện p − 1 lần ở vế trái. Chúng ta đưa ra ngoài và sử dụng kí hiệu giai thừa, ta có (p − 1)! = 1 · 2 · 3 · · · (p − 1). Do đó

ap−1(p − 1)! ≡ (p − 1)! (mod p).

Cuối cùng, khử (p − 1)! từ cả hai vế, vì (p − 1)! không chia hết bởi p. Vậy

ap−1 ≡ 1 (mod p),

điều này hoàn thành chứng minh của định lý Fermat.

Ví dụ 1.4.3. Số p = 15485863 là số nguyên tố, nên từ định lý Fermat ta có

215485862 ≡ 1 (mod 15485863).

Do đó không cần làm bất kỳ phép tính nào, chúng ta vẫn biết số 215485862 − 1 là một số có hơn hai nghìn chữ số, là bội của 15485863.

Nhận xét 1.4.4. Định lý Fermat và thuật toán lũy thừa nhanh cung cấp cho chúng ta một phương pháp hợp lý hiệu quả để tính nghịch đảo môđun p, đó là a−1 ≡ ap−2 (mod p).

Ví dụ 1.4.5. Chúng ta có thể tính nghịch đảo của 7814 modun 17449 bằng hai cách.

Đầu tiên,

7814−1 ≡ 781417447 ≡ 1284 (mod 17449).

Thứ hai, chúng ta sử dụng thuật toán Euclid để giải

7814u + 17449v = 1,

và ta có (u, v) = (1284, −575). Vậy 7814−1 ≡ 1284 (mod 17449).

Ví dụ 1.4.6. Cho số m = 15485207 và sử dụng thuật toán lũy thừa để tính 2m−1 (trên một máy tính)

2m−1 = 215485206 ≡ 4136685 (mod 15485207).

Chúng ta đã không nhận được giá trị 1, vì vậy định lý Fermat dường như là không đúng với m. Nếu m là số nguyên tố, thì từ định lý Fermat ta có 2m−1 ≡ 1 (mod m). Do đó số m = 15485207 không là số nguyên tố. Chỉ bởi một phép tính đơn giản, chúng ta đã chứng minh được m không phải số nguyên tố mà không biết bất kỳ nhân tử nào

của m [3].

Định lý Fermat nói với chúng ta rằng nếu a là một số nguyên không chia hết bởi p, thì ap−1 ≡ 1 (mod p). Tuy nhiên, với những giá trị đặc biệt của a, thì có thể có lũy thừa nhỏ hơn p − 1 của a mà đồng dư với 1. Chúng ta định nghĩa cấp của a môđun p

là số mũ nhỏ nhất k ≥ 1 sao cho [4]

ak ≡ 1 (mod p).

Mệnh đề 1.4.7. Cho p là số nguyên tố và cho a là một số nguyên không chia hết bởi p. Giả sử an ≡ 1 (mod p). Khi đó, cấp của a (mod p) chia hết n. Trong trường hợp đặc biệt, cấp của a (mod p) chia hết p − 1.

Chứng minh. Cho k là cấp của a (mod p), từ định nghĩa ta có ak ≡ 1 (mod p), và k là lũy thừa nguyên dương nhỏ nhất thỏa mãn tính chất này. Chúng ta lại có an ≡ 1 (mod p). Ta chia n bởi k thì thu được

n = kq + r với 0 ≤ r < k.

Do đó

1 ≡ an ≡ akq+r ≡ (ak)q · ar ≡ 1q · ar ≡ ar (mod p).

Tuy nhiên r < k mà vì k là lũy thừa nguyên dương nhỏ nhất của a để ak đồng dư 1, suy ra r = 0. Vì thế n = kq. Vậy k chia hết n.

Áp dụng với n = p − 1 và theo định lý Fermat ta có ap−1 ≡ 1 (mod p). Vậy k

chia hết p − 1.

p có lũy thừa gồm các phần tử thuộc F∗

P , tức là

F∗ p = {1, g, g2, · · · , gp−2}.

Định lý 1.4.8. (Định lý căn nguyên thủy). Cho p là một số nguyên tố. Khi đó tồn tại một phần tử g ∈ F∗

P . Các phần tử này có cấp là p − 1.

Các phần tử với tính chất này được gọi là căn nguyên thủy của Fp hay các phần tử sinh của F∗

Ví dụ 1.4.9. Trường F11 có 2 là căn nguyên thủy vì trong F11 ,

20 = 1, 25 = 10, 21 = 2, 26 = 9, 22 = 4, 27 = 7, 23 = 8, 28 = 3, 24 = 5, 29 = 6.

Do đó mười phần tử khác không của F11 được sinh bởi lũy thừa của 2. Mặt khác, 2 không phải căn nguyên thủy của F17, vì trong F17,

20 = 1, 21 = 2, 22 = 4, 23 = 8, 24 = 16,

25 = 15, 26 = 13, 27 = 9, 28 = 1.

Nhận xét 1.4.10. Nếu p là số lớn, thì trường hữu hạn Fp có thể có nhiều hơn một căn nguyên thủy. Khi đó, Fp có chính xác φ(p − 1) căn nguyên thủy với φ là hàm Euler. Ví dụ, chúng có thể kiểm tra dãy các căn nguyên thủy của F29 là

{2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27}.

p có cấp k.

1.5. Thuật toán mã hóa đối xứng và không đối xứng

Điều này đúng với giá trị φ(28) = 12. Tổng quát hơn, nếu k chia hết p − 1, thì có chính xác φ(k) phần tử của F∗

Chúng ta đã thấy tất cả thuật toán mã hóa đều có một số đặc điểm chung. Bob muốn gửi một thông điệp bí mật đến Alice. Ông sử dụng một khóa bí mật k để đổi tần

số thông điệp m của mình và biến thông điệp đó thành một bản mã c. Khi Alice nhận

được c, cô sử dụng khóa bí mật k để xắp xếp lại c và tái thiết lại m. Nếu thủ tục này

làm việc đúng, thì cả Alice và Bob phải có bản sao của khóa k bí mật. Nếu hệ thống

này là để cung cấp an ninh, thì đối thủ của họ Eve phải không biết k, không phải có khả năng đoán k, và không thể phục hồi m từ c mà không biết k.

Trong phần này chúng ta xây dựng khái niệm về một hệ thống mật mã trong thuật

ngữ toán học trừu tượng. Trong đó, chúng ta có thể phân tích một cách chặt chẽ sự

an toàn của một hệ thống mật mã để chống lại các loại giải mã.

1.5.1. Thuật toán mã hóa đối xứng

Quay trở lại với Bob và Alice, chúng ta nhận thấy rằng họ cần phải chia sẻ kiến thức về khóa bí mật k. Sử dụng khóa bí mật, họ có thể đồng thời mã hóa và giải mã

thông điệp, vì vậy Bob và Alice cần có kiến thức và khả năng bằng nhau (hoặc đối

xứng). Vì lý do đó nên mật mã của loại này được gọi là thuật toán mã hóa đối xứng.

Về mặt toán học, một thuật toán mã hóa đối xứng sử dụng một khóa k được lựa chọn từ một không gian (ví dụ, một bộ) của các khóa K có thể mã hóa một thông điệp gốc

m được lựa chọn từ một không gian thông điệp M, và kết quả của quá trình mã hóa

là một bản mã c thuộc một không gian của bản mã C. Do đó mã hóa bằng mật mã có

thể được xem như một hàm số

e : K × M → C

với miền K × M là tập hợp gồm các cặp (k, m) bao gồm một khóa k và một văn bản

ban đầu m và phạm vi là không gian của bản mã C. Tương tự, giải mã là một hàm số

d : K × C → M.

Tất nhiên, chúng ta muốn tìm các hàm số giải mã thỏa mãn tính chất giúp chúng ta

nhận lại văn bản gốc. Về mặt toán học, điều này được thể hiện bằng công thức

d(k, e(k, m)) = m với mọi k ∈ K và với mọi m ∈ M.

Đôi khi để thuận tiện, ta viết sự phụ thuộc vào k như một chỉ số dưới. Khi đó, với mỗi khóa k, chúng ta nhận được một cặp hàm số

ek : M → C và dk : C → M

thỏa mãn tính chất giải mã

dk(ek(m)) = m với mọi m ∈ M

Nói cách khác, với mỗi khóa k, hàm số dk là nghịch đảo của hàm số ek. Đặc biệt, điều này có nghĩa là ek và dk phải là tương ứng 1 − 1, vì nếu ek(m) = ek(m(cid:48)), thì

m = dk(ek(m)) = dk(ek(m(cid:48))) = m(cid:48).

Khóa k được gọi là an toàn cho Alice và Bob ngay cả khi Eve biết các biện pháp mã

hóa được sử dụng. Trong thuật ngữ toán học, điều này có nghĩa là Eve biết các hàm

số e và d. Ví dụ, nếu Alice và Bob sử dụng mật mã thay thế đơn giản, họ nên giả định Eve có thể biết các hàm số e và d. Điều này cho thấy một tiền đề cơ bản của mật mã

học hiện đại gọi là nguyên tắc Kerckhoff, nói rằng sự an toàn của một hệ thống mật

mã chỉ nên phụ thuộc vào khóa bí mật k.

Nếu (K, M, C, e, d) là một mật mã thành công thì phải có các thuộc tính sau:

1. Với khóa k ∈ K bất kỳ và văn bản gốc m ∈ M, ta phải dễ dàng để tính toán các

bản mã ek(m).

2. Với khóa k ∈ K bất kỳ và một bản mã c ∈ C, ta phải dễ dàng để tính toán các

văn bản gốc dk(c).

3. Cho một hoặc nhiều bản mã c1, c2, · · · , cn ∈ C mã hóa bằng cách sử dụng khóa k ∈ K, ta phải rất khó khăn để tính các văn gốc tương ứng dk(c1), · · · , dk(cn) bất kì mà không biết về k.

4. Cho một hay nhiều cặp văn gốc và bản mã tương ứng là (m1, c1), (m2, c2), · · · , (mn, cn),

ta phải khó khăn để giải mã bản mã c bất kì mà không biết k.

1.5.2. Các chương trình mã hóa

Các chương trình mã hóa thuận lợi để hiển thị các khóa, văn bản gốc, và bản mã

như là số và viết các số của chúng dưới dạng nhị phân. Ví dụ, chúng ta có thể dùng

chuỗi 8 bit [5] , gồm những số từ 1 đến 255 và sử dụng chúng để đại diện cho các chữ cái của hệ thống chữ cái

a = 00000000, b = 00000001, c = 00000010, · · · , z = 00011001.

Để phân biệt chữ thường với chữ hoa, chúng ta đặt A = 00011011, B = 00011100 ...

Phương pháp này kết thúc với 256 kí hiệu riêng biệt để phiên dịch thành hệ nhị phân. Máy tính của chúng ta có thể sử dụng phương pháp này, gọi là mã ASCII [6], để

00100000 A 65

01000001

01100001

(

00101000 B 66

01000010

01100010

)

00101001 C 67

01000011

01100011

00101100 D 68

00101110

... X 88

01000100 ... 01011000

d ... x

100 ... 120

01100100 ... 01111000

Y 89

01011001

121

01111001

01011010

122

01111010

Bảng 1.7: Lược đồ mã hóa ASCII

lưu trữ dữ liệu. Bộ phận của mã ASCII là danh sách trong bảng sau

Định nghĩa 1.5.1. Một lược đồ mã hóa là một phương pháp chuyển đổi một lọai dữ

liệu này thành một lọai dữ liệu khác, ví dụ, chuyển văn bản thành các số. Lược đồ mã

hóa là giả định kiến thức hoàn toàn công khai và được sử dụng bởi tất cả mọi người

cho các mục đích tương tự

Định nghĩa 1.5.2. Chương trình mã hóa là chương trình được thiết kế để dấu thông tin từ bất cứ ai không sử dụng khóa bí mật.

Do đó một lược đồ mã hóa giống như một mã hóa nhưng đối với một lược đồ mã

hóa, cả hai chức năng là kiến thức công khai và được nhanh chóng dễ dàng để tính

toán. Với việc sử dụng của một chương trình mã hóa, một văn bản gốc hay bản mã có thể được xem như một dãy của khối nhị phân, trong đó mỗi khối bao gồm 8 bit tức là

một dãy 8 số 1 và số 0. Một khối 8 bit được gọi là byte. Một byte thường được viết

như là một số thập phân giữa 0 và 255, hay 2 chữ số thập lục phân (cơ sở 16) giữa 00

và FF.

1.5.3. Mã hóa đối xứng của khối mã hóa

Sử dụng lược đồ mã hóa như được mô tả trong phần 1.5.2 rất thích hợp để hiển

thị các phần tử của không gian M bao gồm các chuỗi bit có chiều dài cố định B tức là,

chuỗi 1 và 0. Chúng ta gọi B là cỡ khối của một thuật toán mã hóa. Một thông điệp công khai bao gồm một danh sách các khối thông điệp đươc lựa chọn từ M, và hàm

số mã hóa làm thay đổi khối thông điệp thành danh sách khối bản mã trong C, trong

đó mỗi khối là một chuỗi các bit của B. Nếu kết thúc văn bản gốc với một khối ít hơn

B bit, chúng ta đi đến cuối của khối đó với số không. Hãy nhớ rằng quá trình mã hóa này, chuyển đổi các thông điệp ban đầu thành một chuỗi các khối bit trong B, là kiến

thức công khai.

Mã hóa và giải mã là làm việc với một khối bit tại một thời điểm, vì vậy mã

hóa và giải mã đủ để nghiên cứu một khối văn bản ban đầu duy nhất, tức là cho một m ∈ M duy nhất. Đây là lý do tại sao mã hóa và giải mã là thuận tiện để phá vỡ một

thông điệp thành các khối. Một thông điệp có thể có chiều dài tùy ý, vì vậy thông điệp

đó là tốt đẹp để có thể tập trung quá trình mã hóa trên một mảnh duy nhất có chiều

(cid:123)

số nguyên nằm giữa 0 và 2B − 1 (cid:122) (cid:123) (cid:125)(cid:124) mB−1 · 2B−1 + · · · + m2 · 22 + m1 · 2 + m0 .

danh sách của B bit của m (cid:122) (cid:125)(cid:124) mB−1mb−2 · · · m2m1m0 ←→ Trong đó m0, m1, · · · , mB−1 là mỗi số 0 hay 1.

dài cố định. Khối văn bản ban đầu m là một chuỗi các bit của B, cụ thể, chúng ta có thể xác định các số tương ứng ở dạng nhị phân. Nói cách khác, chúng ta xác định được M với tập số nguyên m thỏa mãn 0 ≤ m ≤ 2B thông qua

Tương tự, chúng ta có thể xác định không gian khóa K và không gian bản mã C

với tập hợp các số nguyên tương ứng với chuỗi bit có một kích cỡ khối nhất định. Để

thuận tiện, chúng ta ký hiệu kích cỡ khối cho các khóa, văn bản gốc và bản mã bởi Bk, Bm, Bc. Do đó chúng ta có thể xác định được K, M và C với tập số nguyên dương

K = {k ∈ Z : 0 ≤ k ≤ 2Bk}, M = {m ∈ Z : 0 ≤ m ≤ 2Bm}, C = {c ∈ Z : 0 ≤ c ≤ 2Bc}.

Làm thế nào để Alice và Bob thực hiện các thiết lập K, hay làm thế nào để họ lựa chọn các kích cỡ khóa Bk. Nếu Bk quá nhỏ, thì Eve có thể kiểm tra mỗi số từ 0 đến 2Bk − 1 cho đến khi cô ấy tìm thấy khóa của Alice và Bob. Chính xác hơn, khi Eve được giả định là biết thuật toán giải mã d (nguyên tắc của Kerckoff), cô ấy lấy mỗi k ∈ K và sử dụng k để tính dk(c). Giả sử rằng Eve có thể phân biệt giữa văn bản gốc hợp lệ và không hợp lệ, cuối cùng cô ấy sẽ phục hồi các thông điệp.

Cuộc giải mã này được biết đến như một cuộc tìm kiếm đầy đủ, từ khi Eve tìm

kiếm toàn diện thông qua không gian khóa. Với sự phát triển công nghệ khoa học, một

tìm kiếm toàn diện được coi như không thực hiện được nếu không gian K có ít nhất 280 phần tử. Do đó Bob và Alice nên chọn Bk ≥ 80.

1.5.4. Các ví dụ về thuật toán mã hóa đối xứng

Cho p là số nguyên tố lớn [7], và 2159 < p < 2160. Alice và Bob có không gian khóa K, không gian văn bản gốc M và không gian bản mã C giống như các tập hợp,

K = M = C = {1, 2, 3, · · · , p − 1}.

Trong thuật ngữ hiện đại, K = M = C = F∗ p bằng nhóm các phần tử khả nghịch của trường hữu hạn Fp. Alice và Bob chọn một khóa k ∈ K ngẫu nhiên, tức là, họ chọn một số nguyên k thỏa mãn 1 ≤ k < p, và họ quyết định sử dụng hàm số mã hóa ek xác định bởi

ek(m) ≡ k · m (mod p).

Điều đó có nghĩa là ek(m) được thiết lập bằng số nguyên dương duy nhất giữa 1 và p, đồng dư với k · m (mod p) (theo định lý Fermat). Các hàm số giải mã tương ứng dk là

(mod p), dk(c) ≡ k(cid:48) · c

với k(cid:48) là nghịch đảo của k môđun p. Điều quan trọng cần lưu ý là mặc dù p là rất lớn, thuật toán Euclid mở rộng cho phép chúng ta tính được k(cid:48) ít hơn 2 log2 p + 2 bước. Do đó tìm k(cid:48) từ k là dễ dàng trong lý thuyết mật mã.

Rõ ràng Eve phải mất nhiều thời gian để tính k, vì thế cô ấy có khoảng 2160 khả năng để lựa chọn. Điều đó có là quá khó đối với Eve để phục hồi k nếu cô ấy biết bản

mã c? Câu trả lời là có, điều đó vẫn còn khó khăn. Chú ý rằng hàm số mã hóa

ek : M → C

là hàm số cho sự lựa chọn khóa k bất kỳ. Điều này có nghĩa là với mỗi c ∈ C và k ∈ K bất kì, tồn tại m ∈ M sao cho ek(m) = c. Hơn nữa, bản mã bất kỳ có thể đại diện cho văn bản gốc bất kỳ, với điều kiện là văn bản gốc đã được mã hóa bằng một khóa

thích hợp. Về mặt toán học, điều này có thể được viết lại bằng cách nói rằng cho bản mã c ∈ C bất kì, văn bản gốc m ∈ M bất kỳ, tồn tại một khóa k sao cho ek(m) = c. Cụ thể điều này là đúng cho khóa

k ≡ m−1 · c (mod p).

Điều này chỉ ra rằng mật mã của Alice và Bob có tính chất 1, 2 và 3, từ đó bất kì ai

biết khóa k có thể dễ dàng mã hóa và giải mã, nhưng điều đó là khó để giải mã nếu chúng ta không biết giá trị của k. Tuy nhiên, mật mã này không có tính chất 4, vì

ngay cả một văn bản gốc cho biết bản mã duy nhất (m, c) cho phép Eve phục hồi lại

riêng khóa k bằng cách sử dụng công thức.

Nếu Alice và Bob xác định hàm số mã hóa của họ là chỉ đơn giản là phép nhân các số nguyên ek(m) = k · m không rút gọn môđun p, thì thuật toán mã hóa của họ vẫn có tính chất 1 và 2. Nếu Eve cố gắng giải mã một bản mã đơn giản c = k · m, cô

ấy vẫn phải đối mặt với nhiệm vụ khó khăn vì hệ số lớn. Tuy nhiên, nếu cô ấy cố gắng để có được nhiều bản mã c1, c2, · · · , cn, thì có cơ hội tốt tức là

gcd(c1, c2, · · · , cn) = gcd(k · m1, k · m2, · · · , k · mn) = k · gcd(m1, m2, · · · , mn)

bằng k hay nhỏ hơn một bội của k. Chú ý rằng đây là một nhiệm vụ dễ dàng để tính

toán ước chung lớn nhất.

Quan sát này cung cấp dấu hiệu đầu tiên của chúng ta về cách rút gọn môđun

p có một hiệu ứng phá hủy các tính chất như là tính chia hết. Hãy xem xét những lỗ hổng của mật mã đế lựa chọn giải mã văn bản gốc. Như đã nói ở trên, nếu Eve có thể

biết một bản mã c và văn gốc m tương ứng, thì cô ấy dễ dàng khôi phục lại khóa bằng

cách tính

k ≡ m−1c (mod p).

Vì vậy hàm số mã hóa ek được đưa ra không có tính chất 4.

Trong ví dụ này, vì phép cộng hiệu quả hơn phép nhân, có một phép cộng môđun

p mã hóa được cho bởi

và ek(m) ≡ m + k (mod p) dk(c) ≡ c − k (mod p),

không khác sự thay đổi hoặc mật mã Caesar mà chúng ta đã biết đến.

Định nghĩa 1.5.3. Mật mã affine, là sự kết hợp của sự thay đổi mật mã và mật mã nhân. Khóa cho một mật mã affine bao gồm hai số nguyên k = (k1, k2) và mã hóa và giải mã được xác định bởi

(mod p), ek(m) ≡ k1 · m + k2

1 · (c − k2)

(mod p), dk(c) ≡ k(cid:48)

Với k(cid:48) là nghịch đảo của k (mod p).

Định nghĩa 1.5.4. Mật mã Hilll là một sự tổng quát hơn của mật mã affine, trong đó văn bản gốc m, bản mã c, và phần thứ hai của khóa được thay thế bằng vectơ cột gồm n số modun p. Phần thứ nhất của khóa k1 được lấy bởi n ma trận với các thành phần số nguyên môđun p. Mã hóa và giải mã một lần nữa được đưa ra bởi

(mod p), ek(m) ≡ k1 · m + k2

1 · (c − k2)

1 là ma trận

(mod p), dk(c) ≡ k(cid:48)

nhưng bây giờ phép nhân k1 · m là tích của một ma trận và vector, và k(cid:48) nghịch đảo của k1 môđun p.

Cả mật mã affine và mật mã Hill đều dễ bị giải mã trong một số trường hợp lựa

chọn giải mã văn bản gốc.

Ví dụ 1.5.5. Như đã đề cập trước đó, phép cộng là nhanh hơn phép nhân, nhưng có

một hoạt động máy tính cơ bản còn nhanh hơn phép cộng được gọi là loại trừ hoặc và

được ký hiệu là XOR hay ⊕. Ở cấp thấp nhất, XOR có hai bit cá nhân β ∈ {0, 1} và β(cid:48) ∈ {0, 1} khi đó

 

0 nếu β và β(cid:48) giống nhau, β ⊕ β(cid:48) =



1nếu β và β(cid:48) khác nhau.

Nếu chúng ta coi một bit như là một số 0 hoặc 1, thì XOR giống như phép cộng mô-đun

Tổng quát hơn, XOR của hai chuỗi bit là một kết quả thực hiện XOR trên mỗi

cặp tương ứng với các bit. Ví dụ,

10110 ⊕ 11010 = [1 ⊕ 1][0 ⊕ 1][1 ⊕ 0][1 ⊕ 1][0 ⊕ 0] = 01100.

Sử dụng phép toán mới này, Alice và Bob có một thuật toán mã hóa cơ bản chưa xử

lý của họ được xác định bởi

ek(m) = k ⊕ m và dk(c) = k ⊕ c.

Ở đây K, M và C là các tập hợp của tất cả các chuỗi nhị phân độ dài B, hay, tập tất cả các số giữa 0 và 2B − 1.

Mật mã này có lợi thế là hiệu quả cao và hoàn toàn đối xứng theo nghĩa là ek và dk là hàm số giống nhau. Nếu k được chọn ngẫu nhiên và được sử dụng một lần duy nhất, thì mã này được biết như là một thời gian đi bộ của Vernam. Thật không may, mật mã này đòi hỏi một khóa dài như là văn bản gốc. Và nếu k được sử dụng để mã

hóa nhiều hơn một văn bản gốc, thì Eve có thể khai thác thực tế là

c ⊕ c(cid:48) = (k ⊕ m) ⊕ (k ⊕ m(cid:48)) = m ⊕ m(cid:48)

để lấy thông tin về m và m(cid:48). Chúng ta không biết Eve sẽ tiến hành như thế nào để tìm thấy k, m hay m(cid:48), nhưng một thực tế đơn giản là khóa k có thể được gỡ bỏ một cách dễ dàng, tiết lộ số lượng ít có khả năng ngẫu nhiên m ⊕ m(cid:48), nên tạo một mật mã phức tạp. Hơn nữa, phương pháp này dễ bị giải mã trong một số trường hợp lựa chọn

giải mã văn bản gốc.

1.5.5. Dãy bit ngẫu nhiên và thuật toán mã hóa đối xứng

Chúng ta có thể sử dụng duy nhất một khóa k tương đối ngắn (bao gồm 160 bit

ngẫu nhiên) để gửi những thông điệp dài tùy ý một cách an toàn và hiệu quả không?

Giả sử chúng ta có thể xây dựng một hàm số

R : K × Z → {0, 1}

với các tính chất sau đây:

Với mọi k ∈ K và mọi j ∈ Z dễ dàng để tính toán R(k, j). Với một chuỗi dài tùy ý các số nguyên j1, j2, · · · , jn và với mọi giá trị R(k, j1), R(k, j2), · · · , R(k, jn),

rất khó để xác định k.

Với dãy bất kì của các số nguyên j1, j2, · · · , jn và với mọi giá trị

R(k, j1), R(k, j2), · · · , R(k, jn),

rất khó để đoán giá trị của R(k, j) với hơn 50% cơ hội thành công với bất kỳ giá trị

của j không có trong danh sách.

Nếu chúng ta có thể tìm được một hàm số R với ba tính chất này, thì chúng ta có thể

sử dụng R để biến một khóa k ban đầu thành một chuỗi các bit

R(k, 1), R(k, 2), R(k, 3), R(k, 4), · · · ,

và sau đó chúng ta có thể sử dụng chuỗi các bit này như một khóa thời gian rời rạc.

Vấn đề cơ bản với phương pháp này là chuỗi các bit là không thực sự ngẫu nhiên vì chuỗi các bit được tạo ra bởi hàm số R. Thay vì, chúng ta nói rằng chuỗi các bit là

một chuỗi giả ngẫu nhiên, chúng ta gọi là R một số giả ngẫu nhiên nguyên âm.

Một số giả ngẫu nhiên nguyên âm có tồn tại không? Nếu tồn tại, chúng sẽ cung

cấp các ví dụ về các hàm số trong những các định nghĩa bởi Diffie và Hellman, nhưng mặc dù đã mất hơn một nửa thế kỷ để nghiên cứu, vẫn chưa có ai chứng minh được

sự tồn tại của giả ngẫu nhiên nguyên âm

Mặc dù chưa có ai chứng minh được rằng một số giả ngẫu nhiên nguyên âm là

có tồn tại, nhiều các ứng cử viên đã được đề xuất. Có hai cách tiếp cận cơ bản để xây dựng các ứng cử viên cho R, và hai phương pháp này cung cấp một ví dụ tốt về sự

xung đột cơ bản trong lý thuyết mật mã giữa an toàn và hiệu quả.

Cách tiếp cận đầu tiên là liên tục áp dụng sự kết hợp đặc biệt của các phép toán

phù hợp tốt để tính toán hiệu quả và có vẻ như là rất khó khăn để gỡ rối. Phương pháp này là cơ bản nhất cho thuật toán mã hóa đối xứng, bao gồm tiêu chuẩn mã hóa

dữ liệu (DES) và tiêu chuẩn mã hóa nâng cao (AES), đó là hai hệ thống sử dụng rộng

rãi nhất hiện nay.

Phương pháp tiếp cận thứ hai để xây dựng R sử dụng hàm số có hiệu quả đảo ngược được biết đến như một vấn đề toán học mà được cho là khó khăn. Cách tiếp

cận này cung cấp một nền tảng lý thuyết thỏa đáng hơn cho một thuật toán mã hóa

đối xứng, không may, tất cả các công trình xây dựng nổi tiếng của loại này không hiệu

quả bằng các công trình đặc biệt, và do đó có ít hấp dẫn hơn với các ứng dụng thực tế.

1.5.6. Thuật toán mã hóa bất đối xứng

Nếu Alice và Bob muốn trao đổi thông tin sử dụng thuật toán mã hóa đối xứng,

đầu tiên họ phải thỏa thuận về một khóa k bí mật. Điều này là tốt nếu họ có một cơ hội để gặp nhau trong bí mật, hoặc nếu họ có thể giao tiếp một lần trên một kênh an

toàn. Tuy nhiên nếu họ không có cơ hội này và nếu tất cả các thông tin liên lạc giữa

họ được giám sát bởi kẻ thù của họ Eve? Điều đó có thể làm cho Alice và Bob trao đổi

khóa bí mật theo các điều kiện không?

Phản ứng đầu tiên của hầu hết mọi người là điều đó là không thể, kể từ khi Eve

thấy tất cả các mảnh thông tin mà Alice và Bob trao đổi. Dưới cái nhìn sâu sắc của

Diffie và Hellman theo giả thuyết nhất định, điều đó có thể. Tìm kiếm các giải pháp

hiệu quả (và chứng minh) cho vấn đề này, được gọi là mật mã khóa công khai (hoặc không đối xứng), tạo thành một trong những phần thú vị nhất của mật mã toán học.

Chúng ta bắt đầu bằng việc mô tả một cách không thuộc toán học để hình dung

mật mã khóa công khai. Alice mua một thiết bị an toàn với một khe hẹp ở đầu và đặt

thiết bị đó ở một vị trí công cộng an toàn. Bob viết thông điệp của ông gửi Alice trên

một mảnh giấy và trượt mảnh giấy đó qua khe ở phía trên cùng của thiết bị an toàn. Bây giờ chỉ có một người có chìa khóa của thiết bị an toàn, có nghĩa là chỉ Alice, có

thể lấy và đọc tin nhắn của Bob. Trong đó, khóa công khai của Alice là an toàn, các

thuật toán mã hóa là quá trình đưa các thông điệp trong khe, và các thuật toán giải

mã là quá trình mở cửa thiết bị an toàn với chìa khóa. Ví dụ, khe tiền gửi qua đêm tại một ngân hàng có hình thức này, mặc dù trong thực tế các khe phải được bảo vệ

tốt để ngăn chặn một người nào đó chèn một cặp dài mỏng kẹp và giải nén các khoản

tiền gửi của người khác.

Một tính năng hữu ích của thiết bị an toàn của chúng ta với khe cắm hệ thống mật mã, mà thiết bị này chia sẻ với hệ thống mã hóa khóa công khai, đó là Alice chỉ

cần phải đặt một thiết bị an toàn tại một địa điểm công cộng, và sau đó tất cả mọi

người trên thế giới có thể sử dụng thiết bị đó liên tục để gửi tin nhắn được mã hóa đến

Alice. Alice không cần cung cấp một thiết bị an toàn riêng biệt cho các phóng viên của mình.Và Alice cũng không cần thiết mở thiết bị an toàn và loại bỏ các thông điệp

của Bob trước khi người khác như Carl hoặc Dave sử dụng thiết bị đó để gửi cho Alice

một thông điệp.

Bây giờ chúng ta đã sẵn sàng cung cấp một công thức toán học về một thuật toán mã hóa bất đối xứng. Như thường lệ, có không gian khóa K, văn bản ban đầu M và bản

mã C. Tuy nhiên, một phần tử k của không gian khóa thực sự là một cặp khóa,

k = (kpriv, kpub),

được gọi là khóa riêng và khóa công khai. Với mỗi khóa công khai kpub có một hàm số mã hóa tương ứng

ekpub : M → C,

và với mỗi khóa riêng kpriv có một hàm số giải mã tương ứng

dkpriv : C → M.

Nếu cặp (kpriv, kpub) ở trong không gian khóa K, thì

dkpriv (ekpub(m)) = m với mọi m ∈ M.

Nếu một thuật toán mã hóa bất đối xứng được cho là an toàn, thì thuật toán đó phải khó khăn đối với Eve để tính toán hàm số giải mã dkpriv (c), ngay cả khi cô ấy biết chìa khóa công khai kpub. Chú ý rằng theo giả định này, Alice có thể gửi kpub để Bob sử dụng một kênh truyền thông không an toàn, và Bob có thể gửi lại bản mã ekpub(m), mà không lo lắng rằng Eve có thể giải mã thông điệp. Để dễ dàng giải mã, Eve phải biết khóa riêng kpriv, và có lẽ Alice là người duy nhất biết thông tin đó. Các khóa riêng đôi khi được gọi là thông tin cửa sập của Alice, vì khóa riêng cung cấp một cửa sập (tức

là, một phím tắt) cho hàm số nghịch đảo của ekpub. Thực tế là các mã hóa và giải mã các khóa kpub và kpriv khác nhau làm cho các thuật toán mã hóa bất đối xứng. Diffie và Hellman đã tạo ra khái niệm này mà không tìm thấy một ứng cử viên thực tế nào

cho một cặp hàm số, mặc dù họ đã đề xuất một phương pháp tương tự mà Alice và

Bob có thể trao đổi một cách an toàn một mảnh ngẫu nhiên các dữ liệu.

Chương 2

Logarit rời rạc và Diffie-Hellman

2.1. Các bài toán logarit rời rạc

Các bài toán logarit rời rạc là bài toán phát sinh ở nhiều nơi, bao gồm cả phiên

bản mod p mô tả trong phần này. Các nghiên cứu đầu tiên xây dựng khóa công khai,

là do Diffie và Hellman [8], dựa trên bài toán logarit rời rạc trong một trường hữu hạn Fp, nhớ lại rằng Fp là một trường với số phần tử là một số nguyên tố. Để thuận tiện, chúng ta sử dụng đồng thời kí hiệu Fp và Z/pZ cho trường này, và sử dụng kí hiệu bằng nhau cho các phần tử của Fp và ký hiệu đồng dư cho các phần tử của Z/pZ.

Cho p là một số nguyên tố (lớn). Định lý 1.4.8 nói với chúng ta rằng có một phần tử nguyên thủy g. Điều đó có nghĩa là mỗi phần tử khác không của Fp đều bằng một lũy thừa của g. Đặc biệt, gp−1 = 1 (bởi định lý Fermat). Tương tự, các phần tử

1, g, g2, g3, · · · , gp−2 ∈ F∗ p

là một danh sách đầy đủ của các phần tử của F∗ p.

Định nghĩa 2.1.1. Cho g là một căn nguyên thủy của Fp và h là phần tử khác không của Fp. Bài toán logarit rời rạc, kí hiệu là (DLP) là như sau: Tìm kiếm số mũ x sao cho

gx ≡ h (mod p)

Số x được gọi là logarit rời rạc của h, cơ số g và được kí hiệu là logg(h).

Nhận xét 2.1.2. Các bài toán logarit rời rạc có một vấn đề được đặt ra, cụ thể là làm thế nào để tìm thấy một số mũ nguyên x sao cho gx ≡ h (mod p). Tuy nhiên, nếu ta tìm thấy một nghiệm, thì chúng ta cũng tìm được vô số nghiệm, bởi vì từ định lý Fermat (Định lý 1.4.2), ta có gp−1 ≡ 1 (mod p). Do đó nếu x là một nghiệm của gx ≡ h (mod p) thì x + k(p − 1) cũng là nghiệm với mọi giá trị của k, bởi vì

gx+k(p−1) ≡ gx · (g(p−1)·k) ≡ h · 1k ≡ h (mod p).

Do đó logg(h) được xác định bằng cách cộng thêm hoặc trừ đi bội của p − 1. Nói cách khác, logg(h) được xác định theo môđun p − 1, ta có thể đưa ra một hàm số [9]

p →

Z (p − 1)Z.

logg : Z∗

p và x > x(cid:48) ∈

(p−1)Z sao cho logg(h) = x và logg(h) = x(cid:48). − 1) ≡ 0

được xác định bởi x (cid:55)→ x + k(p − 1).

≡ h (mod p). Do đó gx − gx(cid:48) (gx−x(cid:48) = gx(cid:48)

Chứng minh. Giả sử h ∈ Z∗ Ta có gx ≡ h (mod p) và gx(cid:48) (mod p).

Cụ thể, chúng ta đề cập đến logarit rời rạc như là một số nguyên nằm giữa 0 và

p − 2 thỏa mãn quan hệ đồng dư gx ≡ h (mod p).

Ví dụ 2.1.3. Số p = 56509 là số nguyên tố, và chúng ta có thể kiểm tra g = 2 là căn

nguyên thủy môđun p. Làm thế nào để tính để tính logarit rời rạc của h = 38679?

Phương pháp duy nhất là tính

22, 23, 24, 25, 26, 27, · · · (mod 56509)

cho đến khi tìm thấy một lũy thừa bằng 38679. Điều đó là khó khăn để tính toán bằng tay, nhưng khi sử dụng máy tính, chúng ta dễ thấy logp(h) = 11235.

Nhận xét 2.1.4. Chúng ta thấy rằng logarit rời rạc có tính chất giống như logarit

liên tục được xác định trên tập số thực hay tập số phức. Trong cả hai trường hợp quá

trình lũy thừa là ngược. Nhưng lũy thừa môđun p luôn thay đổi với số mũ, trái với

tính liên tục của logarit liên tục. Chúng ta liệt kê một vài lũy thừa đầu tiên và một vài logarit rời rạc đầu tiên cho số nguyên tố p = 941 và cơ số g = 627 (để thấy được

gnmodp 627

gnmodp 878

logg(h) 0

logg(h) 429

732

183

835

697

469

279

934

395

366

666

316

182

356

825

522

253

652

732

767

543

483

337

760

549

181

608

374

938

111

189

539

722

904

Bảng 2.1: Lũy thừa và logarit rời rạc của g = 627 môđun p = 941

điều đó.)

Nhận xét 2.1.5. Kết luận của chúng ta về logarit rời rạc bao gồm giả thiết các cơ số

g là một căn nguyên thủy môđun p, nhưng điều này là không cần thiết. Nói chung, với g, h ∈ F∗ p bất kì, bài toán logarit rời rạc được phát biểu lại như sau: xác định số mũ x thỏa mãn gx ≡ h (mod p), giả sử rằng tồn tại một x như vậy.

Tổng quát hơn, thay vì dùng các phần tử khác không của một trường hữu hạn Fp và nhân chúng với nhau, nâng lên lũy thừa. Chúng ta có thể sử dụng các phần tử bất kỳ của nhóm và sử dụng quy tắc nhóm thay vì nhân.

Định nghĩa 2.1.6. Cho G là một nhóm với quy tắc nhóm kí hiệu bởi (cid:63). Các bài toán

logarit rời rạc trong G là: với hai phần tử bất kì g và h trong G, tìm số nguyên x thỏa mãn

= h

2.2. Trao đổi khóa Diffie-Hellman

g (cid:63) g (cid:63) g (cid:63) · · · (cid:63) g (cid:124) (cid:125) (cid:123)(cid:122) x lần

Các thuật toán trao đổi khóa Diffie-Hellman đã giải quyết được vấn đề sau. Alice

và Bob muốn chia sẻ một khóa bí mật để sử dụng trong một thuật toán mã hóa đối

xứng, nhưng các phương tiện truyền thông duy nhất của họ lại không an toàn. Tất cả

các kênh thông tin mà họ trao đổi đều được quan sát bởi đối thủ của họ Eve. Làm thế nào để Alice và Bob có thể cho chia sẻ một khóa mà Eve không có sẵn? Thoạt nhìn có

vẻ như Alice và Bob phải đối mặt với một nhiệm vụ không thể. Dưới cái nhìn sâu sắc của Diffie-Hellman thì những khó khăn của bài toán logarit rời rạc trong F∗ p sẽ cung cấp một giải pháp có thể.

Bước đầu tiên là cho Alice và Bob một số nguyên tố lớn p và một số nguyên khác không g (mod p). Alice và Bob để các giá trị của p và g là tri thức công khai. Ví dụ,

họ có thể gửi các giá trị trên các trang web của họ, vì vậy Eve cũng biết chúng. Tốt nhất họ nên chọn g trong F∗ p có cấp là một nguyên tố lớn.

Bước tiếp theo Alice chọn một số nguyên a bí mật mà cô không tiết lộ cho bất cứ ai, cùng một lúc đó Bob cũng chọn một số nguyên b mà ông giữ bí mật. Bob và

Alice sử dụng số nguyên bí mật của họ để tính toán

(cid:124)

(cid:123)(cid:122) cái mà Bob tính

. và B ≡ gb (mod p) (cid:125) A ≡ ga (mod p) (cid:124) (cid:123)(cid:122) (cid:125) cái mà Alice tính

Tiếp theo họ trao đổi các giá trị đã tính toán, Alice gửi A cho Bob và Bob gửi B cho

Alice. Lưu ý rằng Eve có thể nhìn thấy các giá trị của A và B, khi chúng được gửi qua

các kênh truyền thông không an toàn.

Cuối cùng, Bob và Alice một lần nữa sử dụng số nguyên bí mật của họ để tính

toán

(cid:124)

(cid:123)(cid:122) cái mà Bob tính

. và B(cid:48) ≡ Ab (mod p) (cid:125) A(cid:48) ≡ Ba (mod p) (cid:123)(cid:122) (cid:125) (cid:124) cái mà Alice tính

Các giá trị mà họ tính toán là A(cid:48)và B(cid:48) tương ứng, và giống nhau, vì

A(cid:48) ≡ Ba ≡ (gb)a ≡ gab ≡ (ga)b ≡ Ab ≡ B(cid:48) (mod p).

Giá trị chung này là chìa khóa trao đổi của họ.

Ví dụ 2.2.1. Alice và Bob chọn số nguyên tố p = 941 và căn nguyên thủy g = 627. Alice chọn khóa bí mật a = 347 và tính A = 390 ≡ 627347 (mod 941). Tương tự như vậy, Bob chọn khóa bí mật b = 781 và tính B = 691 ≡ 627781 (mod 941). Alice gửi cho Bob số 390 và Bob gửi cho Alice số 691. Cả hai được truyền tải trên một kênh không an toàn, vì vậy cả hai A = 390 và B = 691 được coi là tri thức công khai. Số a = 347

và b = 781 không truyền tải và được giữ bí mật. Sau đó Alice và Bob đều có thể tính

toán số

470 ≡ 627347·781 ≡ Ab ≡ Ba (mod 941),

vì vậy 470 là chia sẻ bí mật của họ.

Giả sử Eve nhìn thấy toàn bộ trao đổi này. Cô ấy có thể tái thiết lại chia sẻ bí

mật của Alice và Bob nếu cô ấy có thể giải quyết một trong các quan hệ đồng dư

627a ≡ 390 (mod 941) và 627b ≡ 691 (mod 941),

kể từ đó cô sẽ biết một trong số mũ bí mật của họ. Theo như được biết, đây là cách

duy nhất để Eve tìm thấy giá trị chia sẻ bí mật mà không cần hỗ trợ của Alice hoặc

Bob.

Tất nhiên, ví dụ của chúng ta sử dụng con số đó là quá nhỏ không đủ khả năng để bảo mật thực sự, vì Eve mất rất ít thời gian tính toán trên máy tính để kiểm tra

tất cả các lũy thừa có thể của 627 môđun 941. Alice và Bob nên chọn một số nguyên tố p có khoảng 1000 bit (tức là, p ≈ 21000) và phần tử g có cấp là số nguyên tố bằng khoảng p/2. Khi đó, Eve sẽ phải đối mặt với một nhiệm vụ thực sự khó khăn.

Eve biết các giá trị của A và B, vì vậy cô ấy biết giá trị của ga và gb. Cô ấy cũng biết giá trị của g và p, vì vậy nếu cô ấy có thể giải quyết DLP, sau đó cô ấy có thể tìm

a và b, thì Eve có thể dễ dàng tính toán giá trị bí mật mà Alice và Bob đã chia sẻ.

Có vẻ như chia sẻ của Alice và Bob được bảo mật với điều kiện là Eve không thể giải quyết được DLP, nhưng điều này là không hoàn toàn chính xác. Phương pháp tìm giá

trị được chia sẻ của Alice và Bob là giải quyết bài toán DLP, nhưng đó không phải là

vấn đề mà Eve cần phải giải quyết. Sự an toàn của khóa chia sẻ của Alice và Bob dựa

trên những vấn đề khó khăn sau đây.

Định nghĩa 2.2.2. Cho p là một số nguyên tố và g là một số nguyên. Bài toán Diffie- Hellman (kí hiệu là DHP) là như sau: tính giá trị của gab (mod p) từ các giá trị đã biết ga (mod p) và gb (mod p).

Rõ ràng là các bài toán DHP là không có khó khăn hơn so với bài toán DLP. Nếu

Eve có thể giải quyết bài toán DLP, thì cô có thể tính toán số mũ bí mật a và b của Alice và Bob từ các giá trị A = ga và B = gb, và cô ấy dễ dàng tính được khóa chia sẻ của họ gab. Giả sử Eve có một thuật toán hiệu quả giải quyết DHP. Cô ấy có thể sử dụng thuật toán đó để cũng giải quyết hiệu quả DLP không? Câu trả lời là không

2.3. Hệ thống mật mã khóa công khai ElGamal

biết.

Mặc dù thuật toán trao đổi khóa Diffie-Hellman cung cấp một phương pháp chia sẻ công khai khóa bí mật một cách ngẫu nhiên, phương pháp này không đạt được mục

tiêu đầy đủ của một hệ thống mật mã khóa công khai, kể từ khi một hệ thống mật mã

cho phép trao đổi thông tin đầy đủ, không chỉ là một chuỗi ngẫu nhiên của các bit. Hệ

thống mã hóa khóa công khai đầu tiên là RSA của Rivest, Shamir và Adleman [10], được công khai năm 1978. Tuy nhiên, mặc dù RSA là lịch sử đầu tiên, là sự phát triển

tự nhiên nhất của một hệ thống mật mã khóa công khai theo Diffie-Hellman [11], là

một hệ thống được mô tả bởi Taher ElGamal năm 1985 [12]. Các thuật toán mã hóa

khóa công khai ElGamal dựa trên các vấn đề log rời rạc và liên quan chặt chẽ với trao đổi khóa Diffie-Hellman từ phần 2.2. Trong phần này chúng ta mô tả phiên bản của Elgamal PKC dựa trên bài toán logarit rời rạc cho F∗ p, nhưng các công trình xây dựng thường sử dụng DLP trong nhóm bất kỳ.

Các Elgamal PKC là ví dụ đầu tiên về một hệ thống mật mã khóa công khai. Alice bắt đầu bằng việc công khai thông tin bao gồm một khóa công khai và một thuật

toán. Các khóa công khai chỉ đơn giản là một con số, và các thuật toán là phương pháp

mà Bob mã hóa thông điệp của mình bằng cách sử dụng khóa công khai của Alice.

Alice không tiết lộ khóa riêng của mình, đó là một số khác. Các khóa riêng cho phép Alice, và chỉ có Alice, có thể giải mã thông điệp đã được mã hóa bằng khóa công khai

của mình.

Đối với Elgamal PKC, Alice cần một số nguyên tố p lớn mà bài toán logarit rời p là khó khăn, và cô ấy cần một phần tử g môđun p lớn. Cô ấy có thể chọn

rạc trong F∗ p và g của mình hoặc p và g có thể đã được chọn trước bởi một số đáng tin cậy.

Alice chọn số a bí mật để sử dụng như khóa riêng của mình, và cô ấy tính toán

số

A ≡ ga (mod p).

Alice công bố khóa công khai A của cô và cô giữ riêng khóa bí mật a của mình.

Bây giờ giả sử Bob muốn mã hóa thông điệp sử dụng khóa công khai A của Alice. Chúng ta sẽ giả sử rằng thông điệp m của Bob là một số nguyên giữa 2 và p. Để mã

hóa m, đầu tiên Bob chọn ngẫu nhiên một số khác k (mod p). [13] Bob sử dụng k để

mã hóa chính k, và chỉ với một thông điệp, thì ông đã loại bỏ được k. Số k được gọi

là một khóa không bền, vì k chỉ tồn tại cho các mục đích của mã hóa một thông điệp đơn.

Bob có thông điệp gốc m, lựa chọn ngẫu nhiên khóa k không bền và khóa công

khai của Alice và sử dụng chúng để tính toán hai số

c1 ≡ gk (mod p) và c2 ≡ mAk (mod p).

(Hãy nhớ rằng g và p là các thông số công khai, vì vậy Bob cũng biết giá trị của nó.) Bản mã, tức là mã hóa m của ông ấy, là cặp số (c1, c2) mà ông gửi cho Alice.

Vì Alice biết a, nên cô có thể tính toán số lượng

(mod p), x ≡ ca 1

1 (mod p),

x−1 · c2 ≡ (ca do đó tính được x−1 (mod p). Tiếp theo Alice nhân c2 với x−1 và kết quả là thông điệp gốc m. Chúng ta tính giá trị của x−1 · c2 và tìm 1)−1 · c2 (mod p),

vì x ≡ ca ≡ (gak)−1 · (mAk) (mod p) vì c1 ≡ gk, c2 ≡ mAk (mod p), ≡ (gak)−1 · (m(ga)k) (mod p), vì A ≡ ga (mod p), ≡ m (mod p) vì gak là thành phần rút gọn được.

Eve biết các thông số công khai p và g, cô ấy cũng biết giá trị của A ≡ ga (mod p), vì khóa công khai A của Alice là kiến thức công khai. Nếu Eve có thể giải

quyết bài toán logarit rời rạc, cô ấy có thể tìm thấy a và giải mã thông điệp.

Ví dụ 2.3.1. Alice sử dụng số nguyên tố p = 467 và căn nguyên thủy g = 2. Cô ấy

chọn a = 153 làm khóa riêng của cô ấy và tính khóa công khai của cô ấy

A ≡ ga ≡ 2153 ≡ 224 (mod 467).

Bob quyết định gửi cho Alice thông điệp m = 331. Ông chọn khóa không bền một cách

ngẫu nhiên, giả sử ông chọn k = 197, và tính hai giá trị

c1 ≡ 2197 ≡ 87 (mod 467) và c2 ≡ 331 · 224197 ≡ 57 (mod 467).

Cặp (c1, c2) = (87, 57) là bản mã mà Bob gửi cho Alice. Alice, biết a = 153. Đầu tiên, cô tính

1 ≡ 87153 ≡ 367 (mod 467), và sau đó x−1 ≡ 14 (mod 467).

x ≡ ca

Cuối cùng, cô tính

(mod 467) c2x−1 ≡ 57 · 14 ≡ 331

và phục hồi các thông điệp gốc m.

Nhận xét 2.3.2. Trong hệ thống mật mã ElGamal, bản gốc là một số nguyên m nằm giữa 2 và p − 1, trong khi bản mã bao gồm hai số nguyên c1 và c2 trong phạm vi tương tự. Do đó nói chung, chúng ta phải mất hai lần với nhiều bit để viết lại các bản mã

như là số bit để viết lại những văn bản gốc.

Mệnh đề 2.3.3. Xây dựng một số nguyên tố p và cơ số g sử dụng để mã hóa ElGamal. Giả sử rằng Eve có quyền thông qua bởi một lời dự đoán:giải mã bản mã ElGamal tùy

ý được mã hóa bằng cách sử dụng khóa công khai ElGamal tùy ý. Sau đó, cô có thể

sử dụng dự đoán này để giải quyết bài toán Diffie-Hellman đã mô tả ở trên.

Chứng minh. Nhắc lại rằng trong bài toán Diffie-Hellman, Eve được đưa ra hai giá trị

A ≡ ga (mod p) và B ≡ gb (mod p),

và cô cần tính toán giá trị của gab (mod p). Hãy nhớ rằng cô ấy biết cả hai giá trị của A và B, nhưng cô ấy không biết cả hai giá trị a và b.

Bây giờ giả sử Eve có thể tham khảo một lời dự đoán ElGamal. Điều này có nghĩa

là Eve có thể gửi nhà tiên tri một số nguyên tố p, cơ số g, một chìa khóa công khai có mục đích A, và một bản mã có mục đích (c1, c2), sau đó nhà tiên tri gửi lại Eve

1)−1 · c2

(ca (mod p).

Nếu Eve muốn giải quyết bài toán Diffie-Hellman, những giá trị nào của c1 và c2 mà cô nên chọn? Chúng ta thấy rằng c1 = B = gb và c2 = 1 là sự lựa chọn tốt, vì với đầu vào này, với dự đoán (gab)−1 (mod p), và sau đó Eve có thể nghịch đảo môđun p để có được gab (mod p), do đó giải quyết được vấn đề Diffie-Hellman.

Nhưng nhà tiên tri đủ thông minh để biết rằng không thể giải mã bản mã có c2 = 1. Eve vẫn có thể đánh lừa các nhà tiên tri bằng cách gửi bản mã ngẫu nhiên. Cô chọn một giá trị tùy ý cho c2 và dự đoán chìa khóa công khai là A và các bản mã là (B, c2). Nhà tiên tri gửi lại cho cô ấy văn bản gốc m thỏa mãn

1)−1 · c2 ≡ (Ba)−1 · c2 ≡ (gab)−1 · c2

m ≡ (ca (mod p).

Sau khi nhà tiên tri nói với Eve giá trị của m, cô chỉ cần tính

(mod p) m−1 · c2 ≡ gab

để tìm giá trị của gab (mod p). Nhờ có sự giúp đỡ của các nhà tiên tri, Eve đã tính được gab (mod p), mà không cần biết a và b, vì vậy cô chỉ giải quyết bài toán Diffie-Hellman, không phải là bài toán logarit rời rạc.

Nhận xét 2.3.4. Một giải mã, trong đó Eve có quyền thông qua một lời dự đoán để

giải mã bản mã tùy ý được biết đến như một cuộc giải bản mã được lựa chọn. Các đề

xuất trước đó cho thấy hệ thống ElGamal là an toàn để chống lại các cuộc giải mã bản

2.4. Tổng quan về lý thuyết nhóm

mã được lựa chọn. Chính xác hơn, hệ thống ElGamal là an toàn nếu có một giả định rằng vấn đề Diffie-Hellman là khó khăn.

p. Vì lũy thừa chỉ đơn giản là lặp đi lặp lại phép nhân. Những gì chúng ta cần làm là nhấn mạnh một số tính chất quan trọng của phép nhân trong F∗ p và chỉ ra rằng những tính chất này xuất hiện trong nhiều bối cảnh khác nhau.

Chúng ta cần một số tính chất về lũy thừa của các phần tử trong F∗

Các tính chất là:

p thỏa mãn 1 · a = a · 1 = a với mỗi a ∈ F∗ p.

• Có một phần tử 1 ∈ F∗

p có một phần tử nghịch đảo a−1 ∈ F∗

p thỏa mãn a·a−1 = a−1 ·a = 1.

• Với mỗi a ∈ F∗

• Tính chất kết hợp của phép nhân: a · (b · c) = (a · b) · c với mọi a, b, c ∈ F∗ p.

p, chúng ta thay thế bổ sung trong Fp. Chúng ta cũng Giả sử rằng phép nhân trong F∗ sử dụng 0 ở vị trí của −1 và −a ở vị trí của a−1. Khi đó, tất cả bốn tính chất trên vẫn đúng:

• Tính chất giao hoán của phép nhân: a · b = b · a với mọi a, b ∈ F∗ p.

• 0 + a = a + 0 = a với mỗi a ∈ Fp.

• Với mỗi a ∈ Fp có một nghịch đảo −a ∈ Fp thỏa mãn a + (−a) = (−a) + a = 0.

• Tính chất kết hợp của phép cộng, a + (b + c) = (a + b) + c với mọi a, b, c ∈ Fp.

• Tính chất giao hoán của phép cộng, a + b = b + a với mọi a, b ∈ Fp.

Tập hợp và các phép toán tương tự như nhân hoặc cộng là các khái niệm chung đưa

đến khái niệm về một nhóm.

Định nghĩa 2.4.1. Một nhóm bao gồm tập hợp G và một quy tắc, chúng ta kí hiệu

là (cid:63), kết hợp hai phần tử a, b ∈ G để có được phần tử a (cid:63) b ∈ G. Phép toán hợp thành (cid:63) phải có tính chất sau:

Tính chất đơn vị: Có một phần tử e ∈ G sao cho

e (cid:63) a = a (cid:63) e = a với mọi a ∈ G.

Tính chất nghịch đảo: Với mỗi a ∈ G có (duy nhất) một phần tử

a−1 ∈ G thỏa mãn a (cid:63) a−1 = a−1 (cid:63) a = e.

Tính chất kết hợp: a (cid:63) (b (cid:63) c) = (a (cid:63) b) (cid:63) c với mọi a, b, c ∈ G.

Ngoài ra, nhóm có thêm tính chất sau:

Tính chất giao hoán: a (cid:63) b = b (cid:63) a với mọi a, b ∈ G.

thì nhóm đó được gọi là nhóm giao hoán hoặc nhóm Abel.

Nếu G có hữu hạn các phần tử, ta nói G là nhóm hữu hạn. Cấp của G là số phần tử

p và (cid:63) = phép nhân. Phần tử đơn vị là e = 1. Mệnh đề 1.3.7 nói với chúng

trong G, và được kí hiệu bởi |G| hoặc #G.



(cid:40)

Ví dụ 2.4.2. Các nhóm là phổ biến trong toán học và trong các ngành khoa học vật lí. Dưới đây là một vài ví dụ, đầu tiên là hai ví dụ đã đề cập trước đó: (a) G = F∗ ta rằng tồn tại phần tử nghịch đảo. G là nhóm hữu hạn có cấp p − 1. (b) G = Z/NZ và (cid:63) = phép cộng. Phần tử đơn vị là e = 0 và nghịch đảo của a là −a. G là nhóm hữu hạn với cấp N. (c) G = Z và (cid:63) = phép cộng. Phần tử đơn vị là e = 0 và nghịch đảo của a là −a. G là nhóm vô hạn. (d) Chú ý rằng G = Z và (cid:63) = phép nhân không phải là một nhóm, vì nhiều phần tử không có nghịch đảo nhân trong Z, ví dụ 2. (e) Tuy nhiên, G = R∗ và (cid:63) = phép nhân là một nhóm, vì mọi phần tử đều có nghịch đảo nhân trong R∗. (f) Một ví dụ không phải nhóm giao hoán là

 

 (cid:41)  : a, b, c, d ∈ R | ad − bc (cid:54)= 0 

a b G =





c d

 

  và phần tử

1 0 với phép toán (cid:63) = phép nhân ma trận. Phần tử đơn vị là e =

0 1

−1









nghịch đảo được cho bởi công thức quen thuộc

d ad−bc

−b ad−bc

 

 

 

 .

a b =

−c ad−bc

a ad−bc











c d

 

  và

 

 , ta thấy

 

 

 

  =

 

 

Chú ý rằng G không giao hoán, vì từ một ví dụ    1 2 1 1 1 2 1 1 3 3



3 4 3 4 1 1 7 7





 

 

  =

 

  .

1 1  1 1 1 2 4 6 trong khi

1 1 3 4 4 6

(g) Tổng quát hơn, chúng ta có thể sử dụng ma trận kích thước bất kỳ. Điều này cho

ta các nhóm tuyến tính tổng quát

GLn(R) = {ma trận An×n với hệ số thực và det(A) (cid:54)= 0}

với phép toán (cid:63) = phép nhân ma trận. Chúng ta có thể hình thành các nhóm khác bằng cách thay thế R bởi một số trường khác nhau , ví dụ, trường hữu hạn Fp. Nhóm GLn(Fp) là nhóm hữu hạn, nhưng tính toán cấp của nhóm đó là một bài toán hay.

Cho g là một phần tử của một nhóm G và x là một số nguyên dương. Khi đó, gx

(cid:124)

có nghĩa là ta áp dụng phép toán của nhóm x lần phần tử g,

(cid:123)(cid:122) x lặp lại

gx = g (cid:63) g (cid:63) g (cid:63) · · · (cid:63) g (cid:125)

Ví dụ, lũy thừa gx trong nhóm F∗ p theo nghĩa thông thường, nhân g với chính g, x lần. Nhưng "lũy thừa" gx trong nhóm Z/nZ nghĩa là cộng g bởi g, x lần. Phải thừa nhận rằng, phép cộng là phổ biến hơn để viết các lượng "g được cộng thêm bởi chính g, x

lần" như là x · g, nhưng đây chỉ là một vấn đề của ký hiệu.

Kí hiệu đó cũng thuận tiện trong việc đưa ra định nghĩa của gx khi x không phải là số dương. Vì vậy nếu x là số nguyên âm, ta định nghĩa gx bởi (g−1)|x|. Với x = 0, ta có g0 = e, phần tử đơn vị của G.

Bây giờ chúng ta giới thiệu một khái niệm quan trọng được sử dụng trong lý

thuyết nhóm.

Định nghĩa 2.4.3. Cho G là một nhóm và cho a ∈ G là một phần tử của nhóm. Giả sử tồn tại số nguyên dương d có tính chất ad = e. Số d nhỏ nhất như vậy được gọi là cấp của a. Nếu không có số d như vậy, thì a được gọi là có cấp vô hạn.

Mệnh đề 2.4.4. Cho G là một nhóm hữu hạn. Khi đó, mỗi phần tử của G có cấp hữu hạn. Hơn nữa, nếu a ∈ G có cấp d và nếu ak = e, thì d | k.

Chứng minh. Vì G là nhóm hữu hạn, nên dãy

a, a2, a3, a4, · · ·

phải có một sự lặp lại. Thật vậy, giả sử tồn tại số nguyên dương i và j với i < j sao cho ai = aj. Nhân cả hai vế với a−i và áp dụng quy tắc nhóm dẫn đến aj−i = e. Vì j − i > 0, điều này chứng minh rằng có một số lũy thừa của a bằng e. Chúng ta lại có d là số mũ dương nhỏ nhất thỏa mãn ad = e.

Giả sử k ≥ d cũng thỏa mãn ak = e. Chúng ta chia k bởi d thu được

k = dq + r với 0 ≤ r < d.

Sử dụng giả thiết ak = ad = e, chúng ta thấy rằng

e = ak = adq+r = (ad)q (cid:63) ar = eq (cid:63) ar = ar.

Nhưng d là lũy thừa nguyên dương nhỏ nhất của a sao cho ad = e, vì vậy chúng ta phải có r = 0. Do đó k = dq, vì vậy d | k.

Định lý 2.4.5. (Định lý Lagrange). Cho G là một nhóm giao hoán hữu hạn và

a ∈ G. Thì cấp của a chia hết cấp của G. Chính xác hơn, cho n = |G| là cấp của G và cho d là cấp của a, tức là, nếu ad là lũy thừa nhỏ nhất của a bằng e. Thì

an = e và d | n.

Chứng minh. Giả sử G là nhóm giao hoán. Vì G là nhóm hữu hạn nên

G = {g1, g2, · · · , gn}.

Nhân mỗi phần tử của G bởi a ta thu được tập mới, gọi là Sa,

Sa = {a (cid:63) g1, a (cid:63) g2, · · · , a (cid:63) gn}.

Các phần tử của Sa là phân biệt. Thật vậy, giả sử rằng a (cid:63) gi = a (cid:63) gj. Nhân cả hai vế với a−1 ta được gi = gj. [14] Do đó Sa chứa n phần tử phân biệt, giống như số lượng các phần tử của G. Do đó Sa = G, vì vậy chúng ta nhân tất cả các phần tử của Sa với nhau. Do đó ta có

(a (cid:63) g1) (cid:63) (a (cid:63) g2) (cid:63) · · · (cid:63) (a (cid:63) gn) = g1 (cid:63) g2 (cid:63) · · · (cid:63) gn.

Chúng ta có thể sắp xếp lại thứ tự của của tích từ bên trái (lại sử dụng tính chất giao

hoán) ta thu được

an (cid:63) g1 (cid:63) g2 (cid:63) · · · (cid:63) gn = g1 (cid:63) g2 (cid:63) · · · (cid:63) gn.

2.5. Bài toán logarit rời rạc khó như thế nào?

Bây giờ nhân bởi (g1 (cid:63) g2 (cid:63) · · · (cid:63) gn)−1 dẫn đến an = e, điều đó chứng minh điều kiện đầu tiên, và sau đó ta có n được chia hết bởi d được suy ra từ mệnh đề 2.5.4.

Cho một nhóm G và hai phần tử g, h ∈ G, bài toán logarit rời rạc yêu cầu tìm số mũ x sao cho gx = h. Làm thế nào chúng ta có thể định lượng độ khó? Một cách tự nhiên để đo độ khó là số gần đúng các phép toán cần thiết cho một người hoặc một máy tính để giải quyết bài toán. Ví dụ, giả sử rằng chúng ta có thể đếm quá trình tính toán gx như một phép toán đơn lẻ. Sau đó, một cách tiếp cận thử và sai để giải quyết các bài toán logarit rời rạc sẽ được tính toán gx với mỗi x = 1, 2, 3, · · · và so sánh các giá trị với h. Nếu g có cấp n, thì thuật toán có thể tìm ra giải pháp nhiều nhất trong n phép toán, tuy nhiên nếu n lớn, như n > 280 thì thuật toán đó không phải là một thuật toán thực tế với tính toán lũy thừa quá lớn.

Trong thực tế, trừ khi người ta phải xây dựng một máy với mục đích đặc biệt, quá trình tính toán gx không thể được tính bằng một phép toán cơ bản nhất. Sử dụng

phương pháp lũy thừa nhanh mô tả trong phần 1.3.2, phải mất một bội của log2(x) phép nhân môđun để tính gx. Giả sử rằng n và x là k số bit, nghĩa là, chúng là khoảng 2k. Thì các phương pháp thử và sai thực sự đòi hỏi khoảng k · 2k phép nhân. Và nếu chúng ta làm việc trong nhóm F∗ p và nếu chúng ta sử dụng phép cộng môđun như phép toán cơ bản, thì phép nhân môđun của hai k − bit số mất (khoảng) k2 phép toán cơ bản, vì vậy bây giờ giải quyết DLP bằng cách thử và sai mất một bội nhỏ của k2 · 2k phép toán cơ bản.

Chúng ta đang không chính xác khi chúng ta nói về bội của 2k hoặc k · 2k hoặc k2 · 2k. Điều này là tính toán không khả thi, các số lớn chẳng hạn như 3 · 2k và 10 · 2k và 100 · 2k.

Định nghĩa 2.5.1. (Kí hiệu theo cấp). Cho f (x) và g(x) là hàm số của các x lấy giá trị dương. Ta nói rằng "f là vô cùng lớn O của g " và ta viết

f (x) = O(g(x))

nếu có hằng số dương c và C sao cho

f (x) ≤ cg(x) với mọi x ≥ C

Mệnh đề tiếp theo mang đến một phương pháp mà đôi khi có thể được sử dụng

để chứng minh rằng f (x) = O(g(x)).

Mệnh đề 2.5.2. Nếu giới hạn

limx→∞ f (x) g(x)

tồn tại (và là hữu hạn) thì f (x) = O(g(x)).

Chứng minh. Cho L là giới hạn. Bằng định nghĩa giới hạn, với (cid:15) > 0 bất kỳ có một hằng số C(cid:15) sao cho

(cid:12) (cid:12) (cid:12)

(cid:12) (cid:12) (cid:12) < (cid:15) − L

với mọi x > C(cid:15). f (x) g(x)

Đặc biệt, (cid:15) = 1, chúng ta thấy rằng

< L + 1 L − 1 < với mọi x > C1. f (x) g(x)

Do đó, theo định nghĩa, f (x) = O(g(x)) với c = L − 1 và C = C1

Ví dụ 2.5.3. Ta có 2x3 − 3x2 + 7 = O(x3, ) vì

= 2. limx→∞ 2x3 − 3x2 + 7 x3

Tương tự, ta có x2 = O(2x), vì

limx→∞ x2 2x = 0.

x2 2x (x2)(cid:48) (2x)(cid:48) 2x 2x ln 2 (2x)(cid:48) (2x ln 2)(cid:48) 2 2x(ln 2)2 = 0

Vì limx→∞ = limx→∞ = limx→∞ = limx→∞ = limx→∞ Tuy nhiên, lưu ý rằng chúng ta có thể có f (x) = O(g(x)), thậm chí nếu giới hạn của f (x) g(x) không tồn tại. Ví dụ, giới hạn

limx→∞ (x + 2) cos2(x) x

không tồn tại, nhưng (x + 2) cos2(x) = O(x), vì (x + 2) cos2(x) ≤ x + 2 ≤ 2x với mọi x ≥ 2.

Giả sử chúng ta cần giải quyết một số bài toán, mà các đầu vào của bài toán là

một số có thể thay đổi kích thước. Ví dụ, khi xem xét bài toán về số nguyên, mà đầu vào là một số N và đầu ra là một thừa số nguyên tố của N . Chúng ta muốn biết phải

mất bao lâu để giải quyết bài toán về kích thước của đầu vào. Thông thường, một

trong những biện pháp để biết kích thước của đầu vào là biết số lượng các bit.

Định nghĩa 1. (Bài toán giải quyết trong thời gian đa thức).Giả sử có một hằng số A ≥ 0, độc lập với kích thước của đầu vào, như vậy nếu kích thước đầu vào là O(k) bit , thì phải mất O(kA) bước để giải quyết bài toán. Sau đó, các bài toán có thể được giải quyết trong thời gian đa thức. Nếu chúng ta có thể lấy A = 1, thì bài toán có thể

được giải quyết trong thời gian tuyến tính, và nếu chúng ta có thể lấy A = 2, thì bài toán có khả năng được giải quyết trong thời gian bậc hai. Các thuật toán thời gian đa

thức được coi là các thuật toán nhanh.

Định nghĩa 2. (Bài toán giải quyết trong thời gian mũ). nếu có một hằng số c > 0 sao cho với đầu vào có kích cỡ O(k) bit, thì có một thuật toán có thể giải quyết các bài toán trên trong O(eck) bước, và khả năng giải quyết trong thời gian mũ. Các thuật toán hàm số mũ theo thời gian được coi là thuật toán chậm.

Trung gian giữa các thuật toán thời gian đa thức và các thuật toán hàm số mũ

theo thời gian là thuật toán số mũ dưới thời gian. Chúng có các tính chất mỗi (cid:15) > 0, họ giải quyết các bài toán trong O(cid:15)(eck) bước. Ký hiệu này có nghĩa là các hằng số c và C xuất hiện ở trong định nghĩa các kí hiệu theo cấp phụ thuộc vào (cid:15).

Như một quy luật chung trong lý thuyết mật mã, bài toán có thể giải quyết trong

thời gian đa thức được coi là dễ dàng và bài toán giải quyết trong thời gian mũ được xem là khó, với số mũ dưới thời gian đang nằm đâu đó ở giữa. Tùy thuộc vào hằng số vô cùng lớn O và kích thước của đầu vào, một bài toán theo cấp số nhân có thể được dễ dàng hơn một bài toán đa thức. Chúng ta minh họa cho các khái niệm trên bởi các

yêu cầu của bài toán logarit rời rạc trong các nhóm khác nhau.

Ví dụ 2.5.4. Chúng ta bắt đầu với bài toán logarit rời rạc gốc gx = h trong G = F∗ p. Nếu p là số nguyên tố được chọn giữa 2k và 2k+1, thì g, h và p chủ yếu là k bit, vì vậy bài toán có thể được giải quyết trong O(k) − bit. (Chú ý rằng O(k) là giống như O(log2 p).)

Nếu chúng ta giải quyết các bài toán DLP sử dụng phương pháp thử và sai đã được đề cập trước đó, thì phải mất O(p) bước để giải quyết bài toán. Vì O(p) = O(2k), thuật toán này cần mất thời gian theo cấp số nhân.

Tuy nhiên, có những cách nhanh hơn để giải quyết các bài toán DLP trong F∗ p, một trong các cách đó là rất nhanh nhưng chỉ thực hiện với một vài số nguyên tố,

trong khi những cách khác ít nhanh, nhưng lại thực hiện cho tất cả các số nguyên tố.

Ví dụ, các thuật toán Pohlig-Hellman được mô tả trong phần 2.8 cho thấy rằng nếu

√

thừa số p − 1 phân tích thành tích các số nguyên tố nhỏ, thì bài toán DLP là khá dễ dàng. Đối với số nguyên tố tùy ý, các thuật toán được mô tả trong phần 2.6 giải quyết được bài toán DLP trong O( p log p) bước, nhanh hơn nhiều so với O(p), nhưng vẫn theo cấp số nhân.

Ví dụ 2.5.5. Tiếp theo chúng ta xem xét các bài toán DLP trong nhóm G = Fp, với phép toán nhóm là phép cộng. Các bài toán DLP trong nhóm này cần tìm x thỏa mãn

x · g ≡ h (mod p),

với g và h là các phần tử của Z/pZ. Như đã mô tả trong phần 1.2, chúng ta có thể giải quyết quan hệ đồng dư này bằng cách sử dụng thuật toán Euclid mở rộng để tính g−1 (mod p) và tính x ≡ g−1 · h (mod p). Điều này mất O(log p) bước, vì vậy có một thuật toán tuyến tính thời gian để giải quyết bài toán DLP trong nhóm Fp. Đây là một thuật toán rất nhanh, vì vậy các bài toán DLP với phép cộng không phải là một

ứng cử viên tốt cho việc sử dụng như là một hàm một chiều trong mật mã.

p với phép nhân là số mũ dưới.

2.6. Thuật toán gặp gỡ cho bài toán DLP

Các bài toán logarit rời rạc trong nhóm khác nhau có thể hiển thị mức độ khó khăn khác nhau cho thuật toán của họ. Do đó, bài toán DLP trong Fp với phép cộng có một thuật toán tuyến tính thời gian, trong khi các thuật toán chung được biết đến tốt nhất để giải quyết các bài toán DLP trong F∗

Trong phần này, chúng ta mô tả một thuật toán logarit rời rạc của Shanks. Đó

là một ví dụ về một vụ va chạm, hoặc một cuộc gặp gỡ, một thuật toán. Thuật toán của Shanks thực hiện trong nhóm bất kỳ , không chỉ F∗ p. Shanks đã chứng minh được thuật toán đó thực hiện được trong các nhóm tùy ý, vì vậy chúng ta sẽ nêu và chứng

minh điều đó trong trường hợp tổng quát.

Mệnh đề 2.6.1. (Giới hạn nhỏ cho bài toán DLP). Cho G là một nhóm và g ∈ G là một phần tử cấp N. (Nhắc lại điều đó nghĩa là gN = e và không có lũy thừa nguyên dương nhỏ hơn của g bằng phần tử đơn vị e.) Khi đó, bài toán logarit rời rạc

gx = h

có thể được giải quyết trong O(N ) bước, trong đó mỗi bước bao gồm một phép nhân bởi g.

Chứng minh. Chúng ta chỉ cần tạo một danh sách các giá trị gx với x = 0, 1, 2, · · · , N − 1. Lưu ý rằng mỗi giá trị kế tiếp có thể thu được bằng cách nhân giá trị trước đó bởi g. Nếu một nghiệm cho gx = h tồn tại, thì h sẽ xuất hiện trong danh sách của chúng ta.

Nhận xét 2.6.2. Nếu chúng ta thực hiện trong F∗ p, thì để tính gx (mod p) chúng ta cần O((log p)k) phép toán máy tính. Hằng số k và hằng số vô cùng lớn O phụ thuộc vào các máy tính và các thuật toán được sử dụng để nhân môđun. Tổng số các bước để tính, hoặc thời gian chạy là O(N (log p)k). Nói chung, các nhân tử của O(N (log p)k) là không đáng kể, vì vậy chúng ta chỉ cần thời gian chạy là O(N ).

Ý tưởng của thuật toán gặp gỡ là tạo hai danh sách và tìm kiếm một phần tử

√ chung của cả hai danh sách. Đối với các bài toán logarit rời rạc được mô tả trong mệnh đề 2.7.1, thời gian chạy của một thuật toán gặp gỡ ít hơn O( N ) bước.

√

N · log N ) bước. √ √ Mệnh đề 2.6.3. (Thuật toán Shanks’s Babystep-Gianstep). Cho G là một nhóm và g là một phần tử có cấp N ≥ 2. Thuật toán sau đây giải quyết bài toán logarit rời rạc gx = h trong O( (1) Cho n = 1 + (cid:98) N (cid:99), vì vậy đặc biệt, n > N.

(2) Tạo hai danh sách, Danh sách 1: e, g2, g3, · · · , gn, Danh sách 2: h, h · g−n, h · g−2n, h · g−3n, · · · , h · g−n2 (3) Tìm phần tử giống nhau trong hai danh sách, hay gi = h · g−jn. (4) Ta có x = i + jn là một nghiệm của gx = h.

Chứng minh. Đầu tiên, khi tạo danh sách 2, chúng ta cần tính u = g−n và sau đó biên dịch danh sách 2, bằng cách tính h, h · u, h · u2, h · u3, · · · , h · un. Nhờ đó chúng ta tạo ra hai danh sách chỉ mất khoảng 2n phép nhân. [15] Thứ hai, giả sử tồn tại

√ √ phần tử giống nhau trong hai danh sách, chúng ta có thể tìm phần tử chung này trong một bội của log(n) bước sử dụng thuật toán phân loại và các thuật toán tìm kiếm, vì vậy bước (3) mất O(log n) bước. Do đó tổng thời gian chạy cho các thuật toán là O(n log n) = O( N , N log N ). Đối với bước cuối cùng này chúng ta đã sử dụng n ≈

vì vậy √ √ √ n log n ≈ N log N = N log N. 1 2

Chúng ta thấy danh sách 1 và 2 luôn luôn có một sự tương ứng. Để thấy điều này, cho x là nghiệm chưa biết của gx = h và viết x như là

x = nq + r với 0 ≤ r < n.

Chúng ta thấy 1 ≤ x < N, vì vậy

√ < < n vì n > q = N . x − r n N n

Do đó chúng ta có thể viết lại phương trình gx = h như là

gr = h · g−qn với 0 ≤ r < n và 0 ≤ q < n.

gk 9704

h · uk 347

gk 15774

h · uk 16564

gk 10137

h · uk 10230

gk 4970

h · uk 12260

6181

13357

12918

11741

17264

3957

9183

6578

5763

12423

16360

16367

4230

9195

10596

7705

1128

13153

13259

7315

9880

13628

2427

1425

8431

7928

4125

2549

9963

10126

6902

6594

16568

1139

16911

10221

15501

5416

11969

12831

14567

6259

4351

16289

6854

13640

6045

4754

2987

12013

1612

4062

15680

5276

7583

14567

Bảng 2.2: Babystep-giantstep để tính 9704x ≡ 13896 (mod 17389)

Như vậy gr có trong danh sách 1 và h · g−qn có trong danh sách 2, điều đó cho thấy rằng danh sách 1 và 2 có một phần tử chung.

Ví dụ 2.6.4. Chúng tôi minh họa cho phương pháp Babystep-giantstep Shanks bằng cách sử dụng nó để giải quyết các bài toán logarit rời rạc

p với g = 9704, h = 13896, và p = 17389.

gx = h trong F∗

19389. Đặt n = (cid:98)

√

Số 9704 có cấp 1242 trong F∗ 1242(cid:99) + 1 = 36 và u = g−n = 9704−36 = 2494. Bảng trên là danh sách các giá trị của gk và h · uk với k = 1, 2, cdots. Từ bảng đó ta tìm được

97047 = 14567 = 13896 · 249432 trong F17389.

Sử dụng giả thiết 2949 = 9704−36, chúng ta tính

13896 = 97047 · 2494−32 = 97047 · (970436)32 = 97041159 trong F17389.

Do đó x = 1159 giải quyết vấn đề 9704x = 13896 trong F17389.

2.7. Định lý thặng dư Trung Hoa

Định lý thặng dư Trung Hoa mô tả các nghiệm cho một hệ thống đồng dư tuyến

tính tương ứng. Cho một hệ gồm hai quan hệ đồng dư,

x ≡ a (mod m) và x ≡ b (mod n),

với gcd(m, n) = 1, trong trường hợp đó định lý thặng dư Trung Hoa nói rằng có duy

nhất một nghiệm môđun mn.

Định lý thặng dư Trung Hoa và những khái quát của định lý đó có rất nhiều ứng

dụng trong lý thuyết số và các lĩnh vực khác của toán học. Trong phần 2.8 chúng ta

sẽ xem sử dụng định lý đó như thế nào để giải quyết một số trường hợp của bài toán

logarit rời rạc. Chúng ta bắt đầu với một ví dụ mà chúng ta giải quyết hai quan hệ đồng dư tương ứng.

Ví dụ 2.7.1. Chúng ta cần tìm một số nguyên x đồng thời thỏa mãn cả hai quan hệ

đồng dư

x ≡ 1 (mod 5) và x ≡ 9 (mod 11).

Quan hệ đồng dư đầu tiên cho chúng ta biết x ≡ 1 (mod 5), vì vậy toàn bộ các nghiệm

của quan hệ đồng dư đầu tiên là tập hợp các số nguyên

x = 1 + 5y, y ∈ Z.

Thay vào quan hệ đồng dư thứ hai, ta có

1 + 5y ≡ 9 (mod 11).

Do đó 5y ≡ 8 (mod 11). Chúng ta có thể tìm y bằng cách nhân cả hai vế bởi nghịch

đảo của 5 môđun 11. Phần tử nghịch đảo của 5 môđun 11 tồn tại vì gcd(5, 11) = 1

và chúng ta có thể tính bằng cách sử dụng tính chất mô tả trong mệnh đề 1.1.1 Tuy

nhiên, trong trường hợp này môđun là một số nhỏ nên chúng ta có thể tìm thấy nghịch đảo của 5 môđun 11 bằng cách thử và sai. Do đó 9 · 5 = 45 ≡ 1 (mod 11).

Nhân cả hai vế với 9

y ≡ 9 · 8 ≡ 72 ≡ 6 (mod 11).

Cuối cùng, thay thế giá trị này của y vào cho nghiệm

x = 1 + 5 · 6 = 31

của bài toán ban đầu.

Định lý 2.7.2. (Định lý thặng dư Trung Hoa). Cho m1, m2, · · · , mk là tập các số đôi một nguyên tố cùng nhau. Điều đó có nghĩa là

gcd(mi, mj) = 1 với mọi i (cid:54)= j.

Cho a1, a2, · · · , ak là số nguyên tùy ý. Khi đó, các hệ nhiều đồng dư tương ứng tùy ý

x ≡ a1 (mod m1), x ≡ a2 (mod m2), · · · , x ≡ ak (mod mk)

có một nghiệm x = c. Hơn nữa nếu x = c và x = c(cid:48) là đều là nghiệm, thì

c ≡ c(cid:48) (mod m1m2 · · · mk).

Chứng minh. Giả sử có một giá trị của i sao cho x = ci là nghiệm của i quan hệ đồng dư tương ứng đầu tiên,

x ≡ a1 (mod m1), x ≡ a2 (mod m2), · · · , x ≡ ai (mod mi).

Ví dụ , nếu i = 1, thì c1 = a1. Chúng ta cần tìm một nghiệm thỏa mãn nhiều hơn một quan hệ đồng dư,

x ≡ a1 (mod m1), x ≡ a2 (mod m2), · · · , x ≡ ai+1 (mod mi+1).

Ý tưởng là tìm kiếm một nghiệm có dạng

x = ci + m1m2 · · · miy.

Chú ý rằng giá trị này của x vẫn thỏa mãn tất cả các quan hệ đồng dư ở trên vì vậy

chúng ta chỉ cần chọn y sao cho y cũng thỏa mãn

ci + m1m2 · · · miy ≡ ai+1 (mod mi+1).

Ví dụ 2.7.3. Chúng ta giải quyết ba quan hệ đồng dư tương ứng

x ≡ 2 (mod 3), x ≡ 3 (mod 7), x ≡ 4 (mod 16).

Định lý thặng dư Trung Hoa nói rằng có duy nhất một nghiệm môđun 336, vì 336 = 3 · 7 · 16. Chúng ta bắt đầu với nghiệm x = 2 cho quan hệ đồng dư đầu tiên x ≡ 2

(mod 3). Sử dụng x có dạng nghiệm tổng quát x = 2 + 3y và thay thế x vào quan hệ

đồng dư thứ hai, ta thu được

2 + 3y ≡ 3 (mod 7).

Đơn giản hoá điều này được 3y ≡ 1 (mod 7), và chúng ta nhân cả hai vế với 5 (vì 5 là nghịch đảo của 3 môđun 7) thu được y ≡ 5 (mod 7). Điều này cho ta giá trị

x = 2 + 3y = 2 + 3 · 5 = 17

như là nghiệm của hai quan hệ đồng dư đầu tiên.

Nghiệm tổng quát của hai quan hệ đồng dư đầu tiên là x = 17 + 21z. Chúng ta

thay x = 17 + 21z vào quan hệ đồng dư thứ ba để có được

17 + 21z ≡ 4 (mod 16).

Đơn giản hóa ta được 5z ≡ 3 (mod 16). Chúng ta nhân cả hai vế với 13, đó là nghịch

đảo của 5 môđun 16 để có được

z ≡ 3 · 13 ≡ 39 ≡ 7 (mod 16).

Cuối cùng, chúng ta thay z vào x = 17 + 21z để thu được nghiệm

x = 17 + 21 · 7 = 164.

Tất cả các nghiệm khác nhau có thể thu được bằng cách cộng hoặc trừ bội của 336 để

được nghiệm đặc biệt.

Mệnh đề 2.7.4. Cho p là một số nguyên tố thỏa mãn p ≡ 3 (mod 4). Cho a là một số nguyên sao cho quan hệ đồng dư x2 ≡ a (mod p) có một nghiệm, tức là, a có một căn bậc hai môđun p. Khi đó,

b ≡ a(p+1)/4 (mod p)

là một nghiệm và thỏa mãn b2 ≡ a (mod p).

p+1 2

Chứng minh. Cho g là một số nguyên tố môđun p, a bằng một lũy thừa của g và a có một căn bậc hai môđun p nghĩa là a là một lũy thừa chẵn của g, tức là a ≡ g2k (mod p). Bây giờ chúng ta tính

b2 ≡ a

(mod p) theo định nghĩa của p, p+1 2 (mod p) vì a ≡ g2k (mod p),

≡ (g2k) ≡ g(p+1)k (mod p) ≡ g2k+(p−1)k (mod p) ≡ a · (gp−1)k (mod p) vì a ≡ g2k (mod p), ≡ (mod p) vì gp−1 ≡ 1 (mod p). Do đó b thực sự là một căn bậc hai của a môđun p.

Ví dụ 2.7.5. Căn bậc hai của a = 2201 môđun số nguyên tố p = 4127 là

b ≡ a(p+1)/4 = 22014128/4 ≡ 22011032 ≡ 3718 (mod 4125).

Để thấy rằng a thực sự là căn bậc hai môđun 4127, chúng ta đơn giản bình phương b và thấy rằng 37182 = 13823524 ≡ 2201 (mod 4127).

Ví dụ 2.7.6. Chúng ta cần tìm kiếm nghiệm của quan hệ đồng dư

x2 ≡ 197 (mod 437).

Phân tích 437 = 19 · 23, vì vậy chúng ta đầu tiên giải quyết được hai đồng dư đầu tiên

y2 ≡ 197 ≡ 7 (mod 19) và z2 ≡ 197 ≡ 13 (mod 23).

Vì cả hai 19 và 23 đều đồng dư với 3 môđun 4, chúng ta có thể tìm căn bậc hai sử dụng mệnh đề 2.7.1 (hay bằng cách thử và sai). Trong trường hợp bất kỳ, chúng ta có

y ≡ ±8 (mod 19) và z ≡ ±6 (mod 23).

Chúng ta có thể chọn 8 hoặc −8 cho y và 6 hoặc −6 cho z. Lựa chọn hai nghiệm dương,

tiếp theo chúng ta sử dụng định lý thặng dư Trung Hoa để giải quyết các quan hệ đồng

dư tương ứng

y ≡ 8 (mod 19) và z ≡ 6 (mod 23).

Chúng ta tìm được x ≡ 236 (mod 437) là một nghiệm như mong muốn.

Nhận xét 2.7.7. Nghiệm của ví dụ 2.8.3 không phải là duy nhất. Trong phần đầu tiên, chúng ta có thể chọn số âm,

−236 ≡ 201 (mod 437),

để có được một căn bậc hai thứ hai của 197 môđun 437. Nếu các mô đun là số nguyên

tố, sẽ có chỉ có hai căn bậc hai. Tuy nhiên, vì 437 = 19 · 23 là hợp số, có hai ước khác

nhau. Để tìm thấy căn bậc hai, chúng ta thay thế một trong số 8 và 6 bởi số âm. Điều này dẫn đến những giá trị x = 144 và x = 293, vì vậy 197 có bốn căn bậc hai môđun

437.

Nhận xét 2.7.8. Từ ví dụ 2.7.3, ta thấy bài toán là tương đối dễ dàng để tính căn

bậc hai môđun m nếu chúng ta biết phân tích m thành tích của các lũy thừa của các

2.8. Các thuật toán Pohlig-Hellman

số nguyên tố. Tuy nhiên, giả sử m quá lớn thì chúng ta không thể phân tích thành tích các lũy thừa nguyên tố. Bài toán là vấn đề rất khó khăn để tìm căn bậc hai môđun m.

Nếu m = m1 · m2 · · · mt là tích của các cặp số nguyên tố cùng nhau, thì định lý thặng dư Trung Hoa nói rằng việc giải quyết một phương trình môđun m là tương đương với việc giải phương trình môđun mi với mỗi i, vì định lý cho chúng ta biết làm thế nào để đan các nghiệm với nhau để có được một nghiệm môđun m.

Trong các bài toán logarit rời rạc (DLP), chúng ta cần phải giải quyết các phương

trình

gx ≡ h (mod p).

Trong trường hợp này, các môđun p là số nguyên tố, điều đó cho thấy lý thặng dư

Trung Hoa là không thích hợp. Tuy nhiên, nhớ lại rằng các nghiệm x chỉ xác định theo môđun p − 1, do đó chúng ta có thể xét các nghiệm tồn tại trong Z/(p − 1)Z. Điều

này gợi ý phân tích p − 1 thành tích các số nguyên tố đóng vai trò trong việc xác định sự khó khăn của DLP trong F∗ p. Tổng quát hơn, nếu G là một nhóm bất kỳ và g ∈ G một phần tử cấp N , thì nghiệm của gx = h trong G chỉ xác định môđun N . Ý tưởng này là cốt lõi của thuật toán Pohlig-Hellman.

Như trong phần 2.7 chúng ta đã chứng minh kết quả trong phần này cho một

nhóm G tùy ý. Chúng ta cũng có thể thay thế G bởi F∗ p.

Định lý 2.8.1. (Thuật toán Pohling-Hellman). Cho G là một nhóm, và giả sử

chúng ta có một thuật toán để giải quyết bài toán logarit rời rạc trong G cho phần tử bất kỳ mà cấp là lũy thừa của một số nguyên tố. Cụ thể, nếu g ∈ G có cấp qe, chúng ta có thể giải quyết gx = h trong O(Sqe) bước. (Ví dụ, mệnh đề 2.7.2 nói rằng chúng ta có thể mất Sqe là qe/2.)

Bây giờ cho g ∈ G là một phần tử cấp N , và giả sử rằng N phân tích thành tích

lũy thừa các số nguyên tố như là

1 · qe2

2 · · · qet t .

N = qe1

O((cid:80)t

Thì bài toán logarit rời rạc gx = h có thể giải quyết trong

i=1 Sqei

+ log N ) bước

sử dụng các tính chất sau đây:

i và hi = hN/qei i .

(1) Với mỗi 1 ≤ i ≤ t, cho

i , vì vậy sử dụng thuật toán để giải quyết

gi = gN/qei

Chú ý rằng gi có lũy thừa nguyên tố cấp qei các bài toán logarit rời rạc

gy i = hi.

i = hi.

Cho y = yi là nghiệm của gy

1 ), x ≡ y2 (mod qe2

2 ), · · · , x ≡ yt (mod qet t ).

(2) Sử dụng định lý thặng dư Trung Hoa để giải quyết x ≡ y1 (mod qe1

Chứng minh. Bước (1) mất O((cid:80) Sqei ) bước, và bước (2) thông qua định lý thặng dư Trung Hoa, mất O(log N ) bước. Thực tế, định lý thặng dư Trung Hoa tính toán thường không đáng kể so với các tính toán logarit rời rạc.

2 ), · · · , x ≡ yt (mod qet t ).

Định lý vẫn chỉ ra bước (1) và (2) đưa ra một nghiệm cho gx = h. Cho x là một

nghiệm của hệ thống quan hệ đồng dư x ≡ y1 (mod qe1 1 ), x ≡ y2 (mod qe2 Thì với mỗi i chúng ta có thể viết

i zi

x = yi + qei

i vì x = yi + qei

i zi,

với mọt số i. Điều này cho phép chúng ta tính i zi)N/qei (gx)N/qei i )yi · gN zi, i )yi vì gN là phần tử đơn vị,

i = hi

i = (gyi+qei = (gN/qei = (gN/qei = gyi i = hi vì gy = hN/qei

i vì định nghĩa của hi.

từ định nghĩa của gi,

Trong điều kiện của logarit rời rạc cơ sở g, chúng ta có thể viết lại như là

· x ≡ (mod N ), · logg(h) N qei i N qei i

Logarit rời rạc cơ sở g chỉ xác định môđun N, vì gN là phần tử đơn vị.

Tiếp theo, chúng ta nhận thấy rằng các số

, , · · · , N qet t N qe1 1 N qe2 2

không có ước chung tầm thường, tức là, ước chung lớn nhất của chúng bằng 1. Lặp đi lặp lại ứng dụng của định lý Euclid mở rộng, chúng ta có thể tìm số nguyên c1, c2, · · · , ct sao cho

· ct = 1. · c1 + · c2 + · · · + N qet t N qe1 1 N qe2 2

t (cid:88)

Bây giờ nhân cả hai vế với ci với i = 1, 2, · · · , t. Điều này cho phép

i=1

(mod N ), · ci · x ≡ · ci · logg(h) N qei i N qei i

· ct = 1 ta thấy · c2 + · · · + N qet t và từ N qe1 1 · c1 + N qe2 2

(mod N ). x = logg(h)

Điều này hoàn thành chứng minh rằng x thỏa mãn gx ≡ h.

Nhận xét 2.8.2. Các thuật toán Pohlig-Hellman cho chúng ta biết các bài toán logarit

√ √ rời rạc trong một nhóm G không an toàn nếu cấp của nhóm G này là tích của lũy thừa của các số nguyên tố nhỏ. Tổng quát hơn, gx = h dễ dàng được giải quyết nếu cấp của các phần tử g là tích của lũy thừa của các số nguyên tố nhỏ. Điều này áp dụng, đặc biệt là đối với bài toán logarit rời rạc trong Fp nếu p − 1 phân tích thành lũy thừa của các số nguyên tố nhỏ. Vì p − 1 thường là chẵn nên cách tốt nhất mà chúng ta có thể làm là lấy p = 2q + 1 với q là số nguyên tố và sử dụng phần tử g cấp q. Khi đó, thời gian chạy của thuật toán va chạm mô tả trong mệnh đề 2.7.2 là O( q) = O( p).

Hiện tại chúng ta giải thích các thuật toán làm giảm bài toán logarit rời rạc cho

các phần tử có cấp lũy thừa nguyên tố đối với bài toán logarit rời rạc cho các phần tử

có cấp q.

có cấp lũy thừa nguyên tố. Ý tưởng rất đơn giản: nếu g có cấp qe, thì gqe−1 Bí quyết là lặp lại quá trình này nhiều lần và sau đó lắp ráp các thông tin vào các câu

trả lời sau cùng.

Mệnh đề 2.8.3. Cho G là một nhóm. Giả sử rằng q là một số nguyên tố, và giả sử chúng ta biết một thuật toán mà chỉ mất Sq bước để giải quyết bài toán logarit rời rạc gx = h trong G bất cứ khi nào g có cấp q. Bây giờ cho g là một phần tử cấp qe với e ≥ 1. Khi đó, chúng ta có thể giải quyết bài toán logarit rời rạc gx = h trong O(eSq) bước.

Chứng minh. Ý tưởng quan trọng để chứng minh mệnh đề là viết số mũ không biết x

dưới dạng

x = x0 + x1q + x2q2 + · · · + xe−1qe−1 với 0 ≤ xi < q,

và sau đó xác định tiếp x0, x1, x2, · · · Chúng ta bắt đầu bằng cách quan sát phần tử gqe−1

nâng cả hai vế của gx = h lên lũy thừa qe−1 = (gx)qe−1 có cấp q. Điều này cho phép chúng ta tính toán hqe−1

)qe−1

)x1q+x2q2+···+xe−1qe−2

)x0 vì gqe = 1.

= (gx0+x1q+x2q2+···+xe−1qe−1 = gx0qe−1 · (gqe = (gqe−1 có cấp q trong G, nên phương trình Vì gqe−1

(gqe−1 )x0 = hqe−1

là một bài toán logarit rời rạc với cơ sở là một phần tử cấp q. Theo giả thiết, chúng ta có thể giải quyết bài toán này trong Sq bước. Một khi điều này được thực hiện, chúng ta biết một số mũ x0 với tính chất

trong G. = hqe−1 gx0qe−1

Tiếp theo chúng ta làm một tính toán tương tự, lần này nâng cả hai bên của gx = h lên lũy thừa qe−2, trong đó hqe−2 nâng cả hai vế của gx = h lên lũy thừa qe−2

)qe−2

= (gx)qe−2 = (gx0+x1q+x2q2+···+xe−1qe−1 = gx0qe−2 · (gqe−1 = (gqe−2 )x0 · (gqe−1 )x1q+x2q2+···+xe−1qe−3 )x1.

có cấp q trong

Hãy nhớ rằng chúng ta đã xác định được giá trị của x0 và phần tử gqe−1 G. Để tìm x1, chúng ta phải giải quyết bài toán logarit rời rạc

(gqe−1 )x1 = (h · g−x0)qe−2

cho biết số chưa biết x1. Một lần nữa áp dụng thuật toán nhất định, chúng ta có thể giải quyết này trong Sq bước. Do đó trong O(2Sq) bước, chúng ta đã xác định được giá trị của x0 và x1 thỏa mãn

g(x0+x1q)qe−2 = hqe−2 trong G.

Tương tự như vậy, chúng ta tìm x2 bằng cách giải quyết bài toán logarit rời rạc

(gqe−1 )x2 = (h · g−x0−x1q)qe−3 ,

và nói chung, sau khi chúng ta đã xác định được x0, · · · , xi−1, thì các giá trị của xi thu được bằng cách giải quyết

(gqe−1 )xi = (h · g−x0−x1q−···−xi−1qi−1 )qe−i−1 với G.

Mỗi trong số này là một bài toán logarit rời rạc với cơ sở có cấp q, mỗi trong số đó có thể được giải quyết trong Sq bước. Do đó sau O(eSq) bước, chúng ta thu được số mũ x = x0 + x1q + x2q2 + · · · + xe−1qe−1 thỏa mãn gx = h, do đó giải quyết dược bài toán logarit rời rạc ban đầu.

√

Nhận xét 2.8.4. Mệnh đề 2.7.2 nói rằng chúng ta có thể mất Sq = O( q), vì vậy mệnh đề 2.9.1 nói rằng chúng ta có thể giải quyết DLP gx = h trong O(eSq) bước. Nhận thấy rằng nếu chúng ta áp dụng mệnh đề 2.7.2 trực tiếp đến DLP gx = h, thời gian chạy là O(qe/2), mà là chậm hơn nhiều nếu e ≥ 2.

Ví dụ 2.8.5. Chúng ta cùng làm một ví dụ để làm rõ các thuật toán được mô tả trong

chứng minh của mệnh đề 2.8.3 Chúng ta giải phương trình

11251.

5448x = 6909 trong F∗

Số nguyên tố p = 11251 có tính chất p − 1 được chia hết bởi 54, và 5448 có cấp là 54 trong F11251. Bước đầu tiên là giải phương trình

(544853 )x0 = 690953 ,

rút gọn được 11089x0 = 11089. Câu trả lời là x0 = 1, vì vậy giá trị của x là x = 1.

Bước tiếp theo là giải phương trình

(544853 )x1 = (6909 · 5448−x0)52 ,

rút gọn được 11089x1 = 3742. Chú ý rằng chúng ta chỉ cần kiểm tra giá trị của x nằm giữa 1 và 4, mặc dù nếu q quá lớn, chúng ta sẽ sử dụng một thuật toán nhanh hơn mệnh đề 2.7.2 để giải quyết bài toán logarit rời rạc. Trong trường hợp bất kỳ, nghiệm là x1 = 2, vì vậy giá trị của x bây giờ là x = 11 = 1 + 2 · 5.

Tiếp tục, chúng ta giải các bước tiếp theo

(544853 )x2 = (6909 · 5448−x0−x1·5)5 = (6909 · 5448−11)5,

rút gọn được 11089x2 = 1. Do đó x2 = 0, điều đó có nghĩa là giá trị của x là x = 11.

Bước cuối cùng giải

(544853 )x3 = 6909 · 5448−x0−x1·5−x2·52 = 6909 · 5448−11.

Rút gọn điều này để giải quyết 11089x3 = 6320, có nghiệm là x3 = 4. Do đó câu trả lời cuối cùng của chúng ta là

x = 511 = 1 + 2 · 5 + 4 · 53.

Khi kiểm tra, chúng ta tính

√ . 5448511 = 6909 trong F11251

Các thuật toán Pohlig-Hellman (định lý 2.8.1) để giải bài toán logarit rời rạc sử dụng

định lý thặng dư Trung Hoa đan các nghiệm khác nhau với lũy thừa nguyên tố từ định lý 2.7.2. Ví dụ sau đây minh họa các thuật toán Pohlig-Hellman đầy đủ.

Ví dụ 2.8.6. Chúng ta cùng các bài toán logarit rời rạc

23x = 9689 trong F11251.

Cơ sở 23 là một căn nguyên thủy của F11251, tức là, 23 có cấp 11250. Vì 11250 = 2·32·54 là tích các số nguyên tố, các thuật toán Pohlig-Hellman thực hiện hiệu quả hơn. Chúng

ta thiết lập

p = 11251, g = 23, h = 9689, N = p − 1 = 2 · 32 · 54.

Giải (g(p−1)/qe

)x = h(p−1)/qe

với x

g(p−1)/qe 11250

h(p−1)/qe 11250

5029

10724

5448

6909

511

Bước đầu tiên là giải ba bài toán logarit rời rạc phụ, được chỉ ra trong bảng dưới đây.

Bước thứ hai sử dụng định lý thặng dư Trung Hoa để giải ba phương trình đồng dư

x ≡ 1 (mod 2), x ≡ 4 (mod 32), x ≡ 1 (mod 54).

Nghiệm nhỏ nhất là x = 4261. Chúng ta kiểm tra câu trả lời của chúng ta bằng cách

tính

2.9. Vành, vành thương, vành đa thức, và trường hữu hạn

√ . 234261 = 9689 trong F11251

Như chúng ta đã thấy, các nhóm đối tượng cơ bản xuất hiện trong nhiều lĩnh

vực của toán học. Một nhóm G và phép toán cho phép chúng ta "nhân" hai phần tử

thu được phần tử thứ ba. Chúng ta đã đưa ra một cái nhìn tổng quan ngắn gọn về lý thuyết nhóm trong phần 2.4. Một đối tượng cơ bản trong toán học, được gọi là vành,

là một tập hợp có hai phép toán. Hai phép toán này tương tự phép cộng và nhân thông

thường, và chúng liên kết với nhau bởi tính chất phân phối.

2.9.1. Tổng quan về lý thuyết của vành

Chúng ta đã quen thuộc với nhiều vành, ví dụ như vành số nguyên với các phép

toán cộng và phép nhân. Chúng ta tóm tắt các tính chất cơ bản của các phép toán này

và sử dụng chúng để xây dựng định nghĩa cơ bản sau. Định nghĩa. Vành là một tập hợp R có hai phép toán, được kí hiệu bởi + và (cid:63), thỏa

mãn các tính chất sau:

Tính chất của +

[Tính chất đơn vị] Có một phần tử đơn vị cộng 0 ∈ R sao cho

0 + a = a + 0 = a với mọi a ∈ R.

[Tính chất nghịch đảo] Với mỗi a ∈ R có một phần tử nghịch đảo

b ∈ R sao cho a + b = b + a = 0.

[Tính chất kết hợp] a + (b + c) = (a + b) + c với mọi a, b, c ∈ R.

[Tính chất giao hoán] a + b = b + a với mọi a, b ∈ R,

Tóm tắt, nếu chúng ta thấy trong R với chỉ phép toán +, thì R là một nhóm giao hoán

với phần tử đơn vị 0. Tính chất của (cid:63)

[Tính chất đơn vị] Có một phần tử đơn vị nhân 1 ∈ R sao cho

1 (cid:63) a = a (cid:63) 1 = a với mọi a ∈ R.

[Tính chất kết hợp] a (cid:63) (b (cid:63) c) = (a (cid:63) b) (cid:63) c với mọi a, b, c ∈ R.

[Tính chất giao hoán] a (cid:63) b = b (cid:63) a với mọi a, b ∈ R,

Vì vậy, R với chỉ phép toán (cid:63) là một vị nhóm với phần tử đơn vị (nhân) 1, ngoại trừ

các phần tử không bắt buộc phải có như phần tử nghịch đảo nhân.

Tính chất liên kết + và (cid:63)

[Tính chất phân phối] a (cid:63) (b + c) = a (cid:63) b + a (cid:63) c với mọi a, b, c ∈ R.

Nhận xét 2.9.1. Tổng quát hơn, chúng ta đôi khi làm việc với các vành mà không

chứa phần tử đơn vị nhân, và cũng với vành mà (cid:63) là không giao hoán, tức là, a (cid:63) b

không bằng b (cid:63) a. Tuy nhiên vành của chúng ta thường sử dụng là vành giao hoán có

đơn vị (nhân), vì vậy chúng ta sẽ gọi chúng là vành.

Mỗi phần tử của vành có một nghịch đảo cộng, nhưng có nhiều phần tử khác phần tử khác không mà không có phần tử nghịch đảo nhân. Ví dụ trong vành số nguyên Z, chỉ có hai phần tử có nghịch đảo nhân là 1 và −1.

Định nghĩa. Một vành (giao hoán) trong đó mọi phần tử khác không đều có

nghịch đảo nhân được gọi là trường

Ví dụ 2.9.2. Dưới đây là một vài ví dụ về các vành và trường mà chúng ta có lẽ đã quen thuộc.

(a) R = Q, (cid:63) = phép nhân, và cộng thông thường. Phần tử đơn vị nhân là 1. Mọi

phần tử khác không đều có nghịch đảo nhân, vì vậy Q là một trường.

(b) R = Z, (cid:63) = phép nhân, và cộng thông thường. Phần tử đơn vị nhân là 1. Chỉ các phần tử có nghịch đảo nhân là 1 và −1, vì vậy Z là vành, nhưng Z không là trường.

thường. Phần tử đơn vị nhân là 1.

(d) R = Fp, p là số nguyên tố bất kỳ, (cid:63) = phép nhân, và cộng thông thường. Phần tử đơn vị nhân là 1. Mọi phần tử khác không đều có nghịch đảo nhân, vì vậy Fp là một trường.

(e) Tập hợp tất cả các đa thức với hệ số lấy từ Z là một vành đóng kín với phép

Z[x] = {a0 + a1x + a2x2 + · · · + anxn : n ≥ 0 và a0, a1, a2, · · · , an ∈ Z}.

cộng va nhân đa thức thông thường. Vành này ký hiệu là Z[x]. Do đó chúng ta viết

Ví dụ, 1 + x2 và 3 − 7x4 + 23x9 là đa thức của vành Z[x].

(f) Tổng quát hơn, nếu R là vành bất kỳ, chúng ta có thể tạo thành một vành đa thức có hệ số được lấy từ vành R. Ví dụ, vành R có thể là R = Z/nZ hay trường hữu hạn Fp.

2.9.2. Quan hệ chia hết và vành thương

Khái niệm về quan hệ chia hết, ban đầu được giới thiệu cho các số nguyên Z

trong phần 1.2, có thể được tổng quát cho vành bất kỳ.

Định nghĩa. Cho a và b là phân tử của vành R với b (cid:54)= 0. Chúng ta nói rằng b chia hết a, hay a được chia hết bởi b, nếu có một phần tử c ∈ R sao cho

a = b (cid:63) c.

Chúng ta viết b | a để chỉ ra rằng b chia hết a. Nếu b không chia hết a, thì ta viết b (cid:45) a.

Nhận xét 2.9.3. Các tính chất cơ bản của quan hệ chia hết được đưa ra trong mệnh đề 1.4 áp dụng cho vành chung. Chứng minh cho Z để tìm hiểu trong vành bất kỳ.

Tương tự như vậy, quan hệ chia hết cũng đúng trong mọi vành, b | 0 với bất kỳ b (cid:54)= 0. Tuy nhiên, lưu ý rằng không phải mọi vành đều như Z. Ví dụ, có những vành với các phần tử khác không a và b có tích a (cid:63) b bằng 0. Một ví dụ như là vành Z/6Z, trong đó 2 và 3 khác không, nhưng 2 · 3 = 6 = 0.

Nhớ lại rằng một số nguyên được gọi là nguyên tố nếu không có phân tích không tầm thường. Phân tích tầm thường là gì? Chúng ta có thể "phân tích" số nguyên bất

kỳ bằng cách viết số nguyên đó như là a = 1 · a và như là a = (−1)(−a), vì vậy đây

là sự phân tích tầm thường. Nói chung, nếu R là một vành và nếu u ∈ R là một phần tử có một nghịch đảo nhân u−1 ∈ R, thì chúng ta có thể phân tích phần tử a ∈ R bất kỳ bằng cách viết a như là a = u−1 · (ua). Các phần tử mà có nghịch đảo nhân và các phần tử chỉ có một sự phân tích tầm thường là phần tử đặc biệt của vành.

Định nghĩa. Cho R là một vành. Một phần tử u ∈ R được gọi là khả nghịch

nếu u có một nghịch đảo nhân, tức là, nếu có một phần tử v ∈ R sao cho u (cid:63) v = 1.

Một phần tử a của vành R được nói là bất khả quy nếu a không khả nghịch và

nếu a = b (cid:63) c, thì b là khả nghịch hoặc c khả nghịch.

Nhận xét 2.9.4. Các số nguyên có tính chất là mỗi số nguyên phân tích duy nhất thành tích của các số nguyên bất khả quy, không kể thứ tự của các nhân tử và thêm

vào nhân tử của 1 và −1. (Chú ý rằng một số nguyên dương bất khả quy chỉ đơn giản

là tên khác của một số nguyên tố.) Không phải mọi vành đều có tính chất phân tích

duy nhất này, tuy nhiên trong phần tiếp theo chúng ta sẽ chứng minh rằng vành đa thức với hệ số trong một trường là vành phân tích duy nhất.

Chúng ta đã thấy rằng lý thuyết đồng dư là rất quan trọng và là công cụ toán

học cho việc tìm hiểu về các số nguyên. Sử dụng định nghĩa của quan hệ chia hết,

chúng ta có thể mở rộng các khái niệm của lý thuyết đồng dư của vành tùy ý.

Định nghĩa. Cho R là một vành và chọn một phần tử khác không m ∈ R. Chúng

ta nói rằng hai phần tử a và b của R là đồng dư môđun m nếu hiệu của chúng a − b

được chia hết bởi m. Chúng ta viết

a ≡ b (mod m)

thay cho a và b đồng dư môđun m. Quan hệ đồng dư cho vành tùy ý thỏa mãn phương

trình như là các tính chất chúng đã biết trong tập hợp số nguyên.

Mệnh đề 2.9.5. Cho R là một vành và cho m ∈ R với m (cid:54)= 0. Nếu

(mod m), a1 ≡ a2 (mod m) và b1 ≡ b2

thì

(mod m). a1 ± b1 ≡ a2 ± b2 (mod m) và a1 (cid:63) b1 ≡ a2 (cid:63) b2

Nhận xét 2.9.6. Định nghĩa của chúng ta về quan hệ đồng dư gồm tất cả các tính

chất mà chúng ta đã tìm hiểu. Tuy nhiên, chúng ta thấy rằng có tồn tại một khái niệm

tổng quát hơn của quan hệ đồng dư môđun iđêan. Đối với mục đích của chúng ta, điều

đó là đủ để tìm hiểu các quan hệ đồng dư môđun iđêan chính, đó là những iđêan được sinh bởi một phần tử.

Một hệ quả quan trọng của mệnh đề 2.9.1 là phương pháp để tạo vành mới từ

vành cũ, cũng như chúng ta tạo ra Z/qZ từ Z bởi quan hệ đồng dư môđun q.

Định nghĩa.Cho R là một vành và cho m ∈ R với m (cid:54)= 0. Với a ∈ R bất kỳ, chúng ta viết a cho tập hợp tất cả a(cid:48) ∈ R sao cho a ≡ a(cid:48) (mod m). Tập hợp a được gọi là lớp đồng dư của a, và chúng ta ký hiệu tập hợp tất cả các lớp đồng dư bởi R/(m)

hay R/mR. Do đó

R/(m) = R/mR = {a : a ∈ R}.

Chúng ta có thể cộng và nhân các lớp đồng dư sử dụng quy tắc

a + b = a + b và a (cid:63) b = a (cid:63) b.

Chúng ta gọi R/(m) là vành thương của R bởi m.

Mệnh đề 2.9.7. Công thức

a + b = a + b và a (cid:63) b = a (cid:63) b.

đưa ra cách xác định công thức cộng và nhân trên tập các lớp đồng dư R/(m) ,và chúng làm cho R/(m) trở thành một vành.

2.9.3. Vành đa thức và thuật toán Euclid

Trong ví dụ 2.9.2 (f), chúng ta thấy rằng nếu R là vành bất kỳ, thì chúng ta có

thể tạo ra một vành đa thức với hệ số lấy từ R. Vành này được ký hiệu bởi

R[x] = {a0 + a1x + a2x2 + · · · + anxn : n ≥ 1 và a0, a1, · · · , an ∈ R}.

Bậc của đa thức khác không là số mũ của lũy thừa cao nhất của x xuất hiện. Do đó

nếu

a(x) = a0 + a1x + a2x2 + · · · + anxn

với an (cid:54)= 0, thì a(x) có bậc n. Chúng ta ký hiệu bậc của a(x) bởi deg(a), và chúng ta gọi an là hệ số cao nhất của a(x). Đa thức khác không mà có hệ số cao nhất bằng 1 được gọi là đa thức monic. Ví dụ, 3 + x2 là đa thức monic, nhưng 1 + 3x2 không phải đa thức monic.

Đặc biệt những vành đa thức trong đó R là một trường; ví dụ, R có thể là Q hay R hay C hay trường hữu hạn Fp. Ta có thể chọn R là trường F là bởi vì hầu như tất

cả các thuộc tính của Z mà chúng ta đã chứng minh trong phần 1.2 cũng đúng đối với các vành đa thức F[x]. Phần này được dành cho một cuộc thảo luận về các tính chất của F[x].

Quay lại trường phổ thông, chúng ta đã học được cách chia một đa thức bởi cách

khác nhau.Ví dụ

x5 + 2x4 + 7 = (x2 + 2x) · (x3 − 5) + (5x2 + 10x + 7).

Chú ý rằng bậc của phần dư 5x2 + 10x + 7 nhỏ hơn thức sự bậc của số chia x3 − 5.

Chúng ta có thể làm điều tương tự cho vành đa thức F[x] bất kỳ giống như F là

một trường. Vành kiểu này có thuật toán chia với dư gọi là vành Euclid.

Mệnh đề 2.9.8. (Vành F[x] là Euclid). Cho F là một trường và cho a và b là đa thức trong F[x] với b (cid:54)= 0. Chúng ta có thể viết

a = b · k + r

với k và r là đa thức, và hoặc là r = 0 hoặc là deg r < deg b.

Chúng ta có thể nói a chia b có thương k và phần dư r.

Chứng minh. Chúng ta bắt đầu với giá trị của k và r thỏa mãn

a = b · k + r.

(Ví dụ, chúng ta có thể bắt đầu với k = 0 và r = a.) Nếu deg r < deg b, thì bài toán được chứng minh. Nếu không, chúng ta viết b = b0 + b1x + · · · + bdxd và r = r0 + r1x + · · · + rexe Với bd (cid:54)= 0 và re (cid:54)= 0 và e ≥ d. Chúng ta viết lại phương trình a = b · k + r như là

a = b · (k + xe−d) + (r − xe−d · b) = b · k’ + r’. re bd re bd

Chú ý rằng chúng ta đã mặc định bậc của số hạng cao nhất r, vì vậy deg r’ < deg r.

Nếu deg r’ < deg b, thì bài toán được chứng minh. Nếu không, chúng ta lặp lại quá trình này. Chúng ta tiếp tục chứng minh với số hạng r thỏa mãn deg r ≥ deg b và

mỗi lần chúng ta áp dụng quá trình này, bậc của số hạng r của chúng ta nhỏ hơn. Vì

vậy cuối cùng chúng ta đi đến một giới hạn r mà bậc của nó nhỏ hơn thực sự bậc của

Chúng ta có thể định nghĩa ước chung và ước chung lớn nhất trong F[x]. Định nghĩa. Ước chung của hai phần tử a,b ∈ F[x] là phần tử d ∈ F[x] mà chia hết cả a và b. Chúng ta nói rằng d là ước chung lớn nhất của hai phần tử a,b nếu mọi

ước chung của a và b đều chia hết d.

Ví dụ 2.9.9. Ước chung lớn nhất của x2 − 1 và x3 + 1 là x + 1. Chú ý rằng x2 − 1 = (x + 1)(x − 1) và x3 + 1 = (x + 1)(x2 − x + 1), vì vậy x + 1 là ước chung. Chúng ta thấy x + 1 là ước chung lớn nhất.

Có rất nhiều vành, trong đó các ước chung lớn nhất không tồn tại, ví dụ như trong vành F[x]. Nhưng ước chung lớn nhất tồn tại trong vành đa thức F[x] khi F là một trường. Mệnh đề 2.9.10. (Thuật toán Euclid mở rộng trong F[x]). Cho F là một trường và cho a và b là đa thức của F[x] với b (cid:54)= 0. Khi đó, ước chung lớn nhất d của a và b tồn tại, và có đa thức u và v trong F[x] sao cho

a · u + b · v = d.

Chứng minh. Cũng như trong chứng minh của định lý 1.1.1, đa thức gcd(a,b) có thể

được tính bằng cách áp dụng lặp đi lặp lại của mệnh đề 2.9.3, cũng như mô tả trong bảng dưới đây. Tương tự như vậy, các đa thức u và v có thể được tính bằng cách thay

thế một phương trình vào trong bảng bên dưới, chính xác như mô tả trong chứng minh

a = b · k1 + r2 b = r2 · k2 + r3 r2 = r3 · k3 + r4 r3 = r4 · k4 + r5

với 0 ≤ deg(r2) < deg(b), với 0 ≤ deg(r3) < deg(r2), với 0 ≤ deg(r4) < deg(r3), với 0 ≤ deg(r5) < deg(r4),

...

... rt−2 = rt−1 · kt−1 + rt

với 0 ≤ deg(rt) < deg(rt−1),

rt−1 = rt · kt. Thì d = rt = gcd(a,b).

Bảng 2.3: Thuật toán Euclid cho đa thức

của định lý 1.1.2

Ví dụ 2.9.11. Chúng ta sử dụng thuật toán Euclid trong vành F13[x] để tính

gcd(x5 − 1, x3 + 2x − 3) :

x5 − 1 = (x3 + 2x − 3) · (x2 + 11) + (3x2 + 4x + 6) x3 + 2x − 3 = (3x2 + 4x + 6) · (9x + 1) + (9x + 4) 3x2 + 4x + 6 = (9x + 4) · (9x + 8) + 0 gcd = 9x + 4 Do đó 9x + 4 là ước chung lớn nhất của x5 − 1 và x3 + 2x − 3 trong F13[x]. Để có được một đa thức monic, chúng ta nhân bởi 3 ≡ 9−1 (mod 13). Điều này cho

gcd(x5 − 1, x3 + 2x − 3) = x − 1 trong F13[x].

Trong phần 2.9.2 ta thấy một phần tử u của vành là khả nghịch nếu phần tử đó có nghịch đảo nhân u−1. Và một phần tử a của vành là bất khả quy nếu a không khả nghịch và có một sự phân tích duy nhất thành a = bc thì b hoặc c khả nghịch. Ta cũng thấy rằng các phần tử khả nghịch của vành đa thức F[x] là chính xác là các đa thức hằng số khác không, ví dụ, các phần tử khác không trong F.

Ví dụ 2.9.12. Đa thức x5 − 4x3 + 3x2 − x + 2 là bất khả quy như một đa thức trong Z[x], nhưng nếu chúng ta xem đa thức đó như là một phần tử của F3[x], thì có phân tích như là

x5 − 4x3 + 3x2 − x + 2 ≡ (x + 1)(x4 + 2x3 + 2) (mod 3).

Đa thức đó cũng phân tích được nếu chúng ta xem xét trong F5[x], nhưng lần này là tích của một đa thức bậc hai và một đa thức bậc ba,

(mod 5). x5 − 4x3 + 3x2 − x + 2 ≡ (x2 + 4x + 2)(x3 + x2 + 1)

Mặt khác, nếu chúng ta làm việc trong F13[x], thì x5 − 4x3 + 3x2 − x + 2 là bất khả quy.

Mỗi số nguyên có một phân tích duy nhất thành tích các số nguyên tố. Điều này

đúng cho đa thức với hệ số trong một trường. Và cũng giống như đối với các số nguyên,

chìa khóa cho việc chứng minh duy nhất là thuật toán Euclid mở rộng.

Mệnh đề 2.9.13. Cho F là trường. Khi đó, mỗi đa thức khác không của F[x] có thể phân tích duy nhất thành tích các đa thức monic bất khả quy. Nếu a ∈ F[x] được phân tích như

a = αp1 · p2 · · · pm a = βq1 · q2 · · · qn,

và với α, β ∈ F là hằng số và p1, · · · , pm, q1, · · · , qn, là đa thức monic bất khả quy, thì sau khi sắp xếp lại thứ tự của q1, · · · , qn, ta có

α = β, m = n và pi = qi với mọi 1 ≤ i ≤ m.

Chứng minh. Sự tồn tại của một sự phân tích thành tích các đa thức bất khả quy

được chứng minh nhờ một từ thực tế nếu a = b · c, thì deg(a) = deg(b) + deg(c).

Chứng minh rằng sự phân tích là duy nhất chính xác giống như chứng minh cho các số nguyên. Các bước quan trọng trong việc chứng minh đó là phát biểu nếu p ∈ F[x] là bất khả quy và chia hết tích a · b, thì hoặc là p | a hoặc là p | b. Phát biểu này là

là tương tự đa thức của mệnh đề 1.3.4 và được chứng minh tương tự như vậy, sử dụng

các phiên bản đa thức của thuật toán Euclid mở rộng.

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ố

Trong phần 2.9.3 chúng ta đã tìm hiểu vành đa thức và trong phần 2.9.2 chúng

ta đã biết về vành thương. Trong phần này, chúng ta kết hợp hai vấn đề này và xem

xét thương của vành đa thức.

Ta thấy các số nguyên môđun m, thường được sử dụng để đại diện cho mỗi lớp đồng dư môđun m, các số nằm giữa 0 và m. Thuật toán chia với dư cho phép chúng

ta làm điều gì đó tương tự cho các thương của một vành đa thức.

Mệnh đề 2.9.14. Cho F là một trường và cho m ∈ F[x] là đa thức khác không. Khi đó, với mỗi lớp đồng dư khác không a ∈ F[x]/(m) có duy nhất đại diện r thỏa mãn

deg(r) < deg(m) và a ≡ r (mod m).

Chứng minh. Sử dụng mênh đề 2.9.10 để tìm đa thức k và r sao cho

a = m · k + r

với hoặc là r = 0 hoặc là deg(r) < deg(m. Nếu r = 0, thì a ≡ 0 (mod m), vì vậy

a = 0. Ngược lại, rút gọn môđun m được a ≡ r (mod m) với deg(r) < deg(m). Điều

này chỉ ra rằng r tồn tại. Ta cần chứng minh r là duy nhất. Giả sử rằng có r’ có tính chất giống như vậy. Thì

r − r’ ≡ a − a ≡ 0 (mod m),

vì vậy m chia hết r − r’. Nhưng r − r’ có bậc nhỏ hơn thực sự bậc của m, vì vậy r − r’ = 0 hay r = r(cid:48).

Ví dụ 2.9.15. Ta xét vành F[x]/(x2 + 1). Mệnh đề 2.9.14 nói rằng mỗi phần tử của vành thương này là được biểu diễn duy nhất bởi một đa thức có dạng

α + βx với α, β ∈ F.

Phép cộng được định nghĩa,

α1 + β1x + α2 + β2x = (α1 + α2) + (β1 + β2)x.

Phép nhân được định nghĩa tương tự, nhưng sau đó chúng ta phải chia kết quả bởi x2 + 1 và lấy phần dư. Do đó

α1 + β1x · α2 + β2x = α1α2 + (α1β2 + α2β1)x + β1β2x2

= (α1α2 − β1β2) + (α1β2 + α2β1)x.

Chúng ta sử dụng mệnh đề 2.9.14 để đếm số phần tử trong vành đa thức thương

khi F là trường hữu hạn.

Hệ quả 2.9.16. Cho Fp là trường hữu hạn và cho m ∈ Fp[x] là đa thức khác không có bậc ≥ 1. Khi đó, vành thương Fp[x]/(m) chứa chính xác pd phần tử.

Chứng minh. Từ mệnh đề 2.9.14 chúng ta biết rằng mỗi phần tử của Fp[x]/(m) được đại diện bởi một đa thức duy nhất dạng

a0 + a1x + a2x2 + · · · + ad−1xd−1 với a0, a1, a2, · · · , ad−1 ∈ Fp.

Có p lựa chọn cho a0, và p cách chọn a1, và như vậy, dẫn đến có pd sự lựa chọn cho a0, a1, a2, · · · , ad−1.

Tiếp theo chúng ta đưa ra đưa ra một đặc tính quan trọng của các phần tử khả

nghịch trong thương đa thức thương. Điều này sẽ cho phép chúng ta xây dựng một

trường hữu hạn mới.

Mệnh đề 2.9.17. Cho F là trường và cho a,m ∈ F[x] là đa thức với với m (cid:54)= 0. Thì a là khả nghịch trong vành thương Fp[x]/(m) nếu và chỉ nếu

gcd(a, m) = 1.

Chứng minh. Đầu tiên giả sử a là khả nghịch trong Fp[x]/(m). Bằng định nghĩa, điều này có nghĩa là chúng ta phải tìm b ∈ Fp[x](m) thỏa mãn a · b = 1. Trong điều kiện của đồng dư, điều này có nghĩa a · b ≡ 1 (mod m), do đó, có một số c ∈ F[x] sao cho

a · b − 1 = c · m.

Thì bất kỳ ước chung của của a và m phải chia hết 1. Cho nên gcd(a, m) = 1. Thì mệnh đề 2.10.10 nói với chúng ta rằng có đa thức u, v ∈ F[x] sao cho

a · u + m · v = 1.

Rút gọn môđun m

a · u ≡ 1 (mod m),

vì vậy u là nghịch đảo của a trong F[x]/(m).

Một ví dụ quan trọng của mệnh đề 2.10.7 là trường hợp mà các môđun là một

đa thức bất khả quy.

Hệ quả 2.9.18. Cho F là trường và cho m ∈ F[x] là đa thức bất khả quy. Thì vành thương F[x]/(m) là một trường, tức là, mội phần tử khác không của F[x]/(m) đều có nghịch đảo nhân.

Chứng minh. Thay m bởi một hằng số bội, chúng ta có thể giả sử rằng m là đa thức monic. Cho a ∈ F[x]/(m). Có hai trường hợp để xem xét. Đầu tiên, giả sử

gcd(a, m) = 1. Thì mệnh đề 2.9.7 nói với chúng ta rằng a là khả nghịch, vì vậy chúng ta đã làm được. Thứ hai, giả sử d = gcd(a, m) (cid:54)= 1. Thì đặc biệt, chúng ta biết rằng

d | m. Nhưng m là monic và bất khả quy, và d (cid:54)= 1, vì vậy chúng ta phải có d = m. Chúng ta d | a, vì vậy m | a. Do đó, a = 0 trong F[x]/(m). Điều này hoàn thành chứng minh rằng mọi phần tử khác không của F[x]/(m) đều có nghịch đảo nhân.

√ Ví dụ 2.9.19. Đa thức x2 + 1 là bất khả quy trong R[x]. Vành thương R[x]/(x2 + 1) là một trường. Thật vậy, nó là trường của các số phức C, nơi các "biến" x đóng vai trò của i = −1, vì trong vành R[x]/(x2 + 1) chúng ta có x2 = −1.

R[x]/(x2 − 1) không phải là trường. Thật sự,

Trái lại, các đa thức x2 − 1 roàng không bất khả quy trong R[x]. Vành thương

(x − 1)(x + 1) = 0 trong R[x]/(x2 − 1).

Do đó vành thương R[x]/(x2 − 1) có những phần tử khác không mà tích của nó bằng không, điều đó có nghĩa là chúng chắc chắn không là phần tử khả nghịch. (Các phần

tử khác không của vành mà tích của chúng bằng không được gọi là ước của không.)

Nếu chúng ta áp dụng hệ quả 2.9.18 vào vành đa thức với hệ số trong trường hữu hạn Fp, chúng ta có thể tạo ra một trường hữu hạn mới với một số nguyên tố của các phần tử.

Hệ quả 2.9.20. Cho Fp là trường và cho m ∈ Fp[x] là đa thức bất khả quy có bậc d ≥ 1. Thì Fp[x]/(m) là trường với pd phần tử.

Chứng minh. Chúng ta kết hợp hệ quả 2.9.18, trong đó nói rằng Fp[x]/(m) là một trường, với hệ quả 2.10.18, trong đó nói rằng Fp[x]/(m) là trường với pd phần tử.

Ví dụ 2.9.21. Điều đó là không khó khăn để kiểm tra đa thức x3 + x + 1 là bất khả quy trong F2[x], vì vậy Fp[x]/(x3 + x + 1) là một trường với 8 phần tử. Mệnh đề 2.9.14 nói với chúng ta rằng sau đây là đại diện cho tám phần tử trong trường này: 0, 1, x, x2, 1 + x, x + x2, 1 + x + x2. Phép cộng là dễ dàng nếu bạn nhớ điều chỉnh các hệ số môđun 2, vì vậy ví dụ

(1 + x) + (x + x2) = 1 + x2.

Phép nhân cũng dễ dàng, chỉ cần nhân các đa thức, chia cho x3 + x + 1, và lấy phần dư. Ví dụ,

(1 + x) · (x + x2) = x + 2x2 + x3 = 1,

vì vậy 1 + x và x + x2 là nghịch đảo nhân.

Ví dụ 2.9.22. Khi nào thì đa thức x2 + 1 bất khả quy trong vành Fp[x]? Nếu đa thức đó là khả quy, thì đa thức đó được phân tích như là

x2 + 1 = (x + α)(x + β) với một vài α, β ∈ Fp.

So sánh các hệ số, ta tìm được α + β = 0 và α · β = 1, do đó

α2 = α · (−β) = −1.

Nói cách khác, trường Fp có một phần tử có bình phương bằng −1. Ngược lại, nếu α ∈ Fp thỏa mãn α2 = −1, thì x2 + 1 = (x + α)(x − α) trong Fp[x]. Điều này chứng minh rằng x2 + 1 là bất khả quy trong Fp[x] nếu và chỉ nếu −1 không phải là bình phương trong Fp. hay x2 + 1 là bất khả quy trong Fp[x] nếu và chỉ nếu p ≡ 3 (mod 4). Cho p là một số nguyê tố thỏa mãn p ≡ 3 (mod 4). Thì trường thương Fp[x]/(x2+ 1) là trường chứa p2 phần tử. Ntrường đó chứa một phần tử x là căn bậc hai của −1. Vì vậy chúng ta có thể xem Fp[x]/(x2 + 1) như là tương tự của các số phức và có thể viết dưới dạng

a + bi với a, b ∈ Fp,

trong đó i đơn giản là một ký hiệu với tính chất i2 = −1. Phép cộng, phép trừ, phép nhân, và phép chia được thực hiện giống như các số phức, với sự hiểu biết rằng thay

vì các số thực như chúng ta sử dụng số nguyên môđun p. Vì vậy ví dụ, phép chia được thực hiện bằng cách thông thường "hợp lý hoá mẫu số",

= · = . a + bi c + di a + bi c + di c − di c − di (ac + bd) + (bc − ad)i c2 + d2

Chú ý rằng không bao giờ mẫu số bằng 0, vì giả sử p ≡ 3 (mod 4) đảm bảo rằng c2 + d2 (cid:54)= 0 (miễn là ít nhất một trong những c và d là khác không).

Trích dẫn

[1] Chú ý rằng log2(A) có nghĩa là logarit thông thường cơ số 2, không phải logarit

rời rạc.

[2] Trường hữu hạn còn được gọi là trường Galois, sau khi Evariste Galois đã nghiên cứu về vấn đề này vào thế kỉ 19. Kí hiệu khác cho Fp là GF (p). Và chưa có thêm kí hiệu cho Fp, chúng ta có thể chạy trên Zp, mặc dù trong lý thuyết số kí hiệu Zp là phổ biến hơn dành riêng cho các số nguyên p.

[3] Phân tích nguyên tố của m là m = 15485207 = 3853 · 4019. [4] Chúng ta đã sớm định nghĩa cấp của p trong a là số mũ của p khi a được phân

tích thành tích các số nguyên tố. Do đó không may, từ ’cấp’ có hai nghĩa khác nhau.

Chúng ta sẽ cần phải đánh giá nghĩa của từ đó trong từng ngữ cảnh.

[5] Một bit là 0 hoặc 1. Từ bit là một chữ viết tắt của con số nhị phân. [6] ASCII là viết tắt của American Standard Code for Information Interchange. [7] Trong thực tế có nhiều các số nguyên tố nằm trong khoảng từ 2159 < p < 2160. Định lý số nguyên tố suy ra rằng có nhiều nhất 1% các số nằm trong khoảng đó là

nguyên tố. Tất nhiên, cũng có những câu hỏi về việc xác định một số là nguyên tố hay hợp số. Có những cách kiểm tra hiệu quả để làm điều này, ngay cả đối với các số lớn.

[8] W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans.Information

Theory, IT−22(6) : 644 − 654, 1976.

[9] Nếu chúng ta nghiên cứu những phân tích phức tạp, chúng ta sẽ nhận thấy nét tương tự với logarit phức tạp, không thực sự được định nghĩa trên C∗. Đây là do thực tế e2πi vì vậy log(z) được định nghĩa tốt để cộng hay trừ bội của 2πi. Logarit phức tạp được xác định là một đẳng cấu từ C∗ đến nhóm thương C/2πiZ.

[10] R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital

signatures and public-key cryptosystems. Comm. ACM, 21(2) : 120 − 126, 1978.

[11] W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans.Information

Theory, IT−22(6) : 644 − 654, 1976.

[12] T. ElGamal. A public key cryptosystem and a signature scheme based on

discrete logarithms. IEEE Trans. Inform. Theory, 31(4) : 469 − 472, 1985.

[13] Đa số hệ thống khóa công khai yêu cầu sử dụng các số ngẫu nhiên trong thứ

tự hoạt động một cách an toàn . Các hệ sinh ngẫu nhiên hay tìm kiếm ngẫu nhiên các

số nguyên là vấn đề thực sự khó khăn.

[14] Giả sử a (cid:63) gi = a (cid:63) gj. Chúng ta sử dụng giả thiết này và các quy tắc nhóm

để tính

gi = e (cid:63) gi = (a−1 (cid:63) a) (cid:63) gi = a−1 (cid:63) (a (cid:63) gi) = (a−1 (cid:63) a) (cid:63) gj = e (cid:63) gj = gj

[15] Phép nhân với g là một "bước nhỏ" và phép nhân bởi u = g−n là một "bước

tiến khổng lồ," từ tên của thuật toán.

[16] Để thuận tiện kí hiệu, chúng ta bỏ qua (cid:63) cho phép nhân và chỉ viết a · b, hoặc

thậm chí chỉ đơn giản là ab.

KẾT LUẬN

Những vấn đề chính của luận văn

• 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...

• Phần trọng tâm của luận văn trình bày các kiến thức về mật mã khoa 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ã khoa công khai ElGamal,

thuật toán Pohlig-Hellman và thuật toán gặp gỡ...

• Phần cuối của luận văn, 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í thặng

dư Trung Hoa.

Tài liệu tham khảo

[A] Tài liệu tiếng Việt

[1] Nguyễn Tự Cường, "Giáo trình đại số hiện đại 2003"

[2] Hoàng Xuân Sính, " Giáo trình đại số đại cương"

[3] Lại Đức Thịnh, " Giáo trình số học"

[B] Tài liệu tiếng Anh

[4] W. Diffie and M. E. Helman, "New directions in cryptography". IEEE

Trans.Information Theory, IT−22(6) : 644 − 654, 1976

[5] T. ElGamal, "A public key cryptosystem and a signature scheme based on discrete

logarithms" IEEE Trans. Inform. Theory, 31(4) : 469 − 472, 1985

[6] Jeffrey Hoffstein-Jill Pipher-Joseph H.Silverman,"An Introduction to Mathemati-

cal Cryptography"

[7] R.L.Rivest, A. Shamir, and L.Adleman, "A method for obtaining digital signatures

and public-key cryptosystems. Comm. ACM, 21(2) : 120 − 126, 1978"

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

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.

LÝ THUYẾT VÀNH TRONG MÁY TÍNH

LÝ THUYẾT VÀNH TRONG MÁY TÍNH

Mục lục

Chương 1

Giới thiệu về mật mã

Chương 2

Logarit rời rạc và Diffie-Hellman

Tài liệu tham khảo

Có thể bạn quan tâm

Luận văn Thạc sĩ: Chế tạo và nghiên cứu tính chất điện, từ của vật liệu multiferroic Ba₀.₇Ca₀.₃TiO₃/ NiFe₂O₄

Luận văn Thạc sĩ: Nghiên cứu vật liệu biến hóa dạng chuỗi một chiều chế tạo từ kim loại đồng trên đế FR-4 hoạt động tại tần số MHz ứng dụng trong truyền năng lượng không dây

Luận văn Thạc sĩ: Đánh giá khả năng tác động tới môi trường biển của việc xả nước thải từ sự cố nhà máy điện hạt nhân Fukushima sử dụng công cụ ERICA

Luận văn Thạc sĩ: Xây dựng mô hình đầu dò nơtron và gamma sử dụng nhấp nháy EJ-276 ghép nối với mảng nhân quang silicon

Luận văn Thạc sĩ: Đánh giá khả năng ảnh hưởng của bức xạ ion hóa đến sức khỏe cư dân khu vực mỏ đất hiếm Đông Pao, xã Bản Hon, huyện Tam Đường, tỉnh Lai Châu

Luận văn Thạc sĩ: Sử dụng phương pháp nhiễu xạ neutron khảo sát cấu trúc tinh thể và pha trật tự từ trong vật liệu Pr2FeCrO6

Luận văn Thạc sĩ: Nghiên cứu phân lập, xác định cấu trúc và hoạt tính ức chế NO của các hợp chất thứ cấp từ chủng vi nấm biển Aspergillus sp. CL251

Luận văn Thạc sĩ: Phân tích một số hợp chất bisphenol thôi nhiễm từ bao bì nhựa lên một số mẫu thực phẩm nền tinh bột

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá hoạt tính kháng khuẩn, kháng nấm của loài hoa mộc (Osmanthus fragrans (Thunb.) Lour.) ở Việt Nam

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá tác dụng kháng viêm của loài côi Turpinia montana (Blume) Kurz

Luận văn Thạc sĩ: Tổng hợp và đặc trưng tính chất vật liệu composite có cấu trúc nano chitosan–cyclodextrin/TiO₂–Ag

Luận văn Thạc sĩ: Nghiên cứu chế tạo và khảo sát một số tính chất của màng phủ trên cơ sở nhựa epoxy gốc nước và khung cơ kim - ZIF

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất napthoquinone chứa nguyên tố flo bằng phản ứng đa thành phần

Luận văn Thạc sĩ: Nghiên cứu điều chế vật liệu Bioglass và tổ hợp lai với polymer ALG-F127 định hướng ứng dụng trong điều trị nội nha

Luận văn Thạc sĩ: Khảo sát thành phần hóa học và hoạt tính ức chế enzyme α-glucosidase trên một số hợp chất phân lập từ thịt quả bình bát nước (Annona glabra L.).

Luận văn Thạc sĩ: Tổng hợp và đánh giá hoạt tính chống ung thư của hợp chất lai chứa khung tetrahydro-β-carboline và imidazo[1,5-a]pyridine

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất của benzazole

Luận văn Thạc sĩ: Nghiên cứu chiết tách lignin từ vỏ sầu riêng Ri6 (Durio zibethinus Murr.) và tổng hợp vật liệu biocomposite định hướng ứng dụng trong bảo quản sau thu hoạch

Luận văn Thạc sĩ: Nghiên cứu tổng hợp hạt nano bạc phủ acid hyaluronic mang doxorubicin định hướng ứng dụng trong điều trị ung thư

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và hoạt tính kháng viêm của loài rau dừa nước (Ludwigia adscendens)

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok