BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

PHẠM THANH LÊ

LÝ THUYẾT SỐ
TRONG MÃ HÓA THÔNG TIN

LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2013


BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

PHẠM THANH LÊ

LÝ THUYẾT SỐ
TRONG MÃ HÓA THÔNG TIN
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số

: 60.46.40

LUẬN VĂN THẠC SĨ KHOA HỌC

Người hướng dẫn khoa học: PGS.TS NGUYỄN GIA ĐỊNH

ĐÀ NẴNG - NĂM 2013

LỜI CAM ĐOAN

Tôi xin cam đoan
Những nội dung được trình bày trong luận văn này là do tôi thực hiện
dưới sự hướng dẫn của thầy giáo PGS.TS Nguyễn Gia Định.
Mọi tài liệu dùng trong luận văn đều được trích dẫn rõ ràng và trung
thực tên tác giả, tên công trình, thời gian và địa điểm công bố.
Nếu có sao chép không hợp lệ, vi phạm qui chế đào tạo tôi xin chịu
hoàn toàn trách nhiệm.

Tác giả

Phạm Thanh Lê


MỤC LỤC
MỞ ĐẦU ............................................................................................................... 1
1. Lý do chọn đề tài ......................................................................................... 1
2. Mục tiêu nghiên cứu .................................................................................... 3
3. Đối tượng và phạm vi nghiên cứu ................................................................ 3
4. Phương pháp nghiên cứu ............................................................................. 3
5. Ý nghĩa khoa học và thực tiễn của đề tài...................................................... 4
6. Cấu trúc luận văn......................................................................................... 4
CHƯƠNG 1. KIẾN THỨC CƠ SỞ ..................................................................... 5
1.1. PHÉP TÍNH ĐỒNG DƯ VÀ CÁC VẤN ĐỀ LIÊN QUAN .............................. 5
1.1.1. Số nguyên tố và định lý cơ bản của số học ............................................. 5
1.1.2. Thuật toán Euclid và mở rộng ................................................................ 6
1.1.3. Phi hàm Euler ........................................................................................ 8
1.1.4. Phép tính đồng dư và phương trình đồng dư .......................................... 9

1.1.5. Định lí Fermat và các mở rộng..............................................................10
1.1.6. Tính toán với đồng dư của lũy thừa bậc lớn ..........................................11
1.1.7. Định lý Phần dư Trung Hoa ..................................................................12
1.1.8. Thặng dư bình phương và kí hiệu Legendre ..........................................13
1.2. LIÊN PHÂN SỐ ..............................................................................................14
1.2.1. Khái niệm liên phân số .........................................................................14
1.2.2. Giản phân ............................................................................................ 15
1.3. TRƯỜNG HỮU HẠN ....................................................................................19
1.3.1. Trường Fp .............................................................................................19
1.3.2. Cách xây dựng trường Fq từ trường Fp ..................................................19
1.4. ĐƯỜNG CONG ELLIPTIC.............................................................................21
1.4.1. Khái niệm đường cong elliptic ..............................................................21
1.4.2. Đường cong elliptic trên trường số thực................................................23
1.4.3. Đường cong elliptic trên trường hữu hạn ..............................................25


CHƯƠNG 2. CÁC KHÁI NIỆM CƠ BẢN CỦA MÃ HÓA VÀ CÁC HỆ MÃ
ĐỐI XỨNG ...........................................................................................................27
2.1. MỘT SỐ THUẬT NGỮ VÀ KHÁI NIỆM .....................................................27
2.1.1. Một số thuật ngữ ...................................................................................27
2.1.2. Hệ mã đối xứng và hệ mã phi đối xứng.................................................28
2.2. LịCH SỬ MẬT MÃ HỌC ...............................................................................29
2.3. NGUYÊN TẮC CHUNG VÀ MỘT SỐ HỆ MÃ ĐƠN GIẢN .........................30
2.3.1. Hệ mã Ceasar........................................................................................30
2.3.2. Hệ mã khối ...........................................................................................32
2.4. HỆ MÃ DỮ LIỆU TIÊU CHUẨN - DES ........................................................33
2.4.1. Phương án thu gọn của DES ................................................................ 34
2.4.2. Mô hình đầy đủ của DES ......................................................................39
2.4.3. Các phương thức sử dụng DES .............................................................47
2.4.4. Độ an toàn của DES..............................................................................48

2.5. THUẬT TOÁN MÃ HÓA DỮ LIỆU QUỐC TẾ IDEA ..................................49
2.5.1. Nhận xét chung .....................................................................................49
2.5.2. Mã hóa và giải mã trong IDEA .............................................................50
2.5.3. Những đặc tính quan trọng....................................................................55
2.6. HỆ MÃ SAFER ...............................................................................................57
2.6.1. Mô tả SAFER .......................................................................................57
2.6.2. Một số biến thể và nâng cấp ..................................................................63
CHƯƠNG 3. CÁC HỆ MÃ MŨ VÀ MÃ PHI ĐỐI XỨNG ................................64
3.1. MỘT SỐ HỆ MÃ MŨ THÔNG DỤNG...........................................................64
3.1.1. Hệ mã mũ Pohlig và Hellman ............................................................. 64
3.1.2. Giao thức trao đổi chìa khóa của Diffie - Hellman ................................68
3.1.3. Hệ mã ElGamal ....................................................................................69
3.1.4. Nguyên tắc chung của mã hóa với khóa công khai ............................... 69
3.2. HỆ MÃ RSA ...................................................................................................70
3.2.1. Nguyên tắc thực hiện ............................................................................70


3.2.2. Độ an toàn ............................................................................................71
3.3. ĐƯỜNG CONG ELLIPTIC VÀ HỆ MÃ PHI ĐỐI XỨNG ............................ 72
3.3.1. Cơ sở Toán học.....................................................................................72
3.3.2. Hệ mã dùng đường cong elliptic trên trường hữu hạn ...........................74
3.3.3. Mật mã khóa công khai dùng đường cong elliptic .................................76
3.3.4. Hệ mã tương tự mã mũ .........................................................................77
3.3.5. Chọn đường cong elliptic......................................................................77
KẾT LUẬN ...........................................................................................................79
DANH MỤC TÀI LIỆU THAM KHẢO
QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN (BẢN SAO).


DANH MỤC CÁC CHỮ VIẾT TẮT


DES – Data Encryption Standard
E-Box – Expansion Box
IDEA – International Encryption Algorihm
IP – Initial Permutation
P-Box – Permutation Box
PC – Permuted Choice
SAFER – Secure And Fast Encryption Routine
S-Box – Substitution Box


DANH MỤC CÁC HÌNH
Số hiệu

Tên hình

hình

Trang

1.1.

Một ví dụ về đường cong elliptic

23

1.2.

Điểm ở vô cùng


23

1.3.

Phép cộng trên đường cong elliptic

24

1.4.

Phép nhân đôi trên đường cong elliptic

24

2.1.

Cấu trúc Multiplication/Additio (MA)

50

2.2.

Cấu trúc IDEA

51

2.3.

Mã hoá và giải mã trong IDEA


53

2.4.

Cấu trúc một vòng của SAFER

61


1

MỞ ĐẦU
1. Lý do chọn đề tài
Khoa học mật mã đã ra đời cách đây hàng nghìn năm và người đầu tiên
áp dụng mật mã một cách có hệ thống để đảm bảo bí mật thông tin quân sự là
nhà quân sự thiên tài của La Mã cổ đại, Julius Caesar. Mật mã là một ngành
khoa học nghiên cứu các kỹ thuật toán học nhằm cung cấp các dịch vụ bảo vệ
thông tin. Đây là ngành khoa học quan trọng, có nhiều ứng dụng trong đời
sống – xã hội. Tuy nhiên, trong suốt nhiều thế kỷ, các kết quả của lĩnh vực
này hầu như không được ứng dụng trong các lĩnh vực dân sự thông thường
của đời sống – xã hội mà chủ yếu được sử dụng trong lĩnh vực quân sự, chính
trị, ngoại giao... Ngày nay, với sự phát triển ngày càng nhanh chóng của
Internet và các ứng dụng giao dịch điện tử trên mạng, nhu cầu bảo vệ thông
tin trong các hệ thống và ứng dụng điện tử ngày càng được quan tâm và có ý
nghĩa hết sức quan trọng. Vì vậy, các ứng dụng mã hóa và bảo mật thông tin
đang được sử dụng ngày càng phổ biến trong các lĩnh vực khác nhau trên thế
giới, từ các lĩnh vực an ninh, quân sự, quốc phòng…, cho đến các lĩnh vực
dân sự như thương mại điện tử, ngân hàng… Do ý nghĩa quan trọng đó mà đề
tài này thu hút được sự quan tâm của đông đảo các chuyên gia trên khắp thế
giới và luôn được xem là trọng tâm nghiên cứu của mỗi quốc gia, nhất là ở

những nước phát triển.
Một điểm đặc biệt của công nghệ mã hóa hiện đại là không dựa vào khả
năng giữ bí mật về phương pháp mã hóa, vì nó thường không chỉ do một
người nắm giữ, mà nói chung thường có một nhóm người biết. Ngày nay,
người ta không tin vào khả năng giữ được bí mật tuyệt đối của cả một nhóm
người, mà cho rằng bí mật chỉ có thể được giữ bởi một người có lợi ích được
gắn liền với bí mật đó.


2

Mật mã hiện đại có những đòi hỏi mới mang tính nguyên tắc hơn so với
mật mã thường dùng trước đây. Những hệ thống mật mã cũ khi biết được
khoá lập mã của họ ta dễ dàng tìm ra khoá giải mã. Hiển nhiên muốn gửi một
thông báo mật cho một đối tượng nào đó ta cần phải biết khóa lập mã của họ,
vì vậy những người cùng một hệ mã đều biết bí mật của nhau. Nhiều người
cùng sử dụng một hệ mã thì không còn là bí mật nữa. Các hệ thống mật mã
hiện đại đã khắc phục được những nhược điểm đó: công nghệ mã hóa mà
phương pháp chung (thuật toán) là công khai, còn việc triển khai thì cho phép
thay đổi được theo một tham số do từng người sử dụng tự ấn định (mỗi giá trị
của tham số sẽ xác định một cách mã hóa riêng), việc lập mã và giải mã chỉ
có thể được thực hiện khi biết được tham số đó. Tham số như vậy thường
được gọi là “chìa khóa” và nó là thông tin duy nhất cần phải giữ bí mật. Tóm
lại, một hệ mã hiện đại cần phải dựa trên nguyên tắc: chốt tính bảo mật vào
chìa khóa, mà không phải vào phương pháp (thuật toán) mã hóa. Một hệ mã
như vậy không chỉ đáp ứng được đòi hỏi của những chuyên gia về bảo mật
thông tin, mà còn rất phù hợp cho các ứng dụng mang tính toàn dân nơi mà
người sử dụng không hề có một chút nghiệp vụ về bảo mật và an toàn thông
tin nói chung.
Để có được những hệ mã đáp ứng các yêu cầu trên, người ta dựa vào

các công cụ Toán học, đặc biệt là các phương pháp của Lý thuyết số. Có thể
nói, lý thuyết số là một trong những kiến thức toán học lâu đời nhất. Từ trước
tới nay, người ta thường coi lý thuyết số như một lĩnh vực đẹp, nhưng thuần
túy lý thuyết của toán học. Với sự phát triển của khoa học máy tính và công
nghệ thông tin, lý thuyết số đã đóng góp những ứng dụng thực tế bất ngờ và
quan trọng, đặc biệt trong lĩnh vực mã hóa thông tin. Chính nhờ các kết quả
nghiên cứu sâu sắc của toán học, người ta đã có những phương pháp mới


3

trong công nghệ mã hóa, có khả năng chống lại sức bẻ khóa của các siêu máy
tính cực mạnh.
Xuất phát từ tính thời sự của mã hóa thông tin và nhu cầu muốn tìm
hiểu về vai trò của lý thuyết số trong mã hóa thông tin, chúng tôi quyết định
chọn đề tài với tên gọi “Lý thuyết số trong mã hóa thông tin” để tiến hành
nghiên cứu. Ngày nay, công nghệ mã hóa đã phát triển đến mức vượt ra ngoài
khả năng thâu tóm của bất cứ một tài liệu nào, cho nên đề tài này cũng chỉ có
thể trình bày những khía cạnh cơ bản nhất trong lĩnh vực mã hóa thông tin
hiện nay, cùng với những kiến thức toán học làm cơ sở cho nó. Chúng tôi hy
vọng đây là một tài liệu tham khảo tốt cho những người bắt đầu tìm hiểu về
Mã hóa thông tin và hy vọng một số ví dụ minh hoạ đặc sắc góp phần làm
phong phú thêm các kết quả trong lĩnh vực này.
2. Mục tiêu nghiên cứu
Nghiên cứu mã hóa thông tin qua các phương pháp mã hóa dựa trên
công cụ lý thuyết số.
3. Đối tượng và phạm vi nghiên cứu
3.1. Đối tượng nghiên cứu
Mã hóa thông tin và vai trò của lý thuyết số trong các phương pháp mã
hóa.

3.2. Phạm vi nghiên cứu
Mật mã học và các ứng dụng.
4. Phương pháp nghiên cứu

Đề tài này đã sử dụng các phương pháp nghiên cứu sau:
- Phương pháp nghiên cứu tư liệu gồm: Các tài liệu tham khảo, các bài

báo khoa học, các đề tài nghiên cứu có liên quan…
- Phương pháp tiếp cận lịch sử: Sưu tầm, phân tích và tổng hợp tư liệu.
- Phương pháp tiếp cận hệ thống.


4

5. Ý nghĩa khoa học và thực tiễn của đề tài
- Đề tài đã tổng quan các kết quả của các tác giả đã nghiên cứu liên
quan đến mã hóa thông tin và vai trò của lý thuyết số trong các phương pháp
mã hóa nhằm xây dựng một tài liệu tham khảo cho những ai muốn nghiên cứu
về mã hóa thông tin.
- Đề tài đã chứng minh chi tiết và làm rõ một số mệnh đề, cũng như
đưa ra một số ví dụ minh họa đặc sắc nhằm làm cho người đọc dễ dàng tiếp
cận vấn đề được đề cập.
6. Cấu trúc luận văn
Mở đầu
Chương 1: Kiến thức cơ sở
Trong chương này nêu đầy đủ kiến thức cơ sở về phép tính đồng dư,
liên phân số, trường hữu hạn và đường cong elliptic.
Chương 2: Các khái niệm cơ bản của mã hóa và các hệ mã đối xứng
Trong chương này trình bày một số thuật ngữ, khái niệm của mã hóa và
các hệ mã đối xứng. Giới thiệu về hệ mã Caesar, mã khối, hệ mã DES, thuật

toán mã hóa dữ liệu quốc tế IDEA, hệ mã SAFER.
Chương 3: Các hệ mã mũ và mã phi đối xứng.
Trong chương này trình bày một số hệ mã mũ thông dụng, hệ mã RSA,
đường cong elliptic và hệ mã phi đối xứng.
Kết luận.


5

CHƯƠNG 1

KIẾN THỨC CƠ SỞ
Trong chương này chúng tôi trình bày một số kiến thức chuẩn bị. Để tiện theo
dõi, chúng tôi trình bày trong mục 1.1 là một số kiến thức về phép tính đồng
dư và các vấn đề liên quan, trong mục 1.2 là một số kiến thức về liên phân số,
trong mục 1.3 là một số kiến thức về trường hữu hạn, trong mục 1.4 là một số
kiến thức về đường cong elliptic.
1.1 . PHÉP TÍNH ĐỒNG DƯ VÀ CÁC VẤN ĐỀ LIÊN QUAN
1.1.1. Số nguyên tố và định lý cơ bản của Số học
Định nghĩa 1.1. Số nguyên tố là số tự nhiên lớn hơn 1, không chia hết
cho số tự nhiên nào khác ngoài 1 và chính nó. Số tự nhiên lớn hơn 1 không
phải là số nguyên tố được gọi là hợp số.
Định lý 1.1. Mọi hợp số n đều có ước nguyên tố nhỏ hơn

n.

Chứng minh. Vì n là một hợp số nên ta có thể viết n = a.b, trong đó a và
b là các số nguyên với 1  a  b  n . Khi đó, a 2  ab  n nên a  n . Ngoài
ra, ước nguyên tố của a cũng đồng thời là ước nguyên tố của n.
Từ định lý này, ta có sàng Eratosthenes tìm các số nguyên tố nhỏ hơn

hoặc bằng số n cho trước.
Định lý 1.2 (Định lý cơ bản của số học). Mọi số nguyên lớn hơn 1 đều
phân tích được một cách duy nhất dưới dạng tích các lũy thừa của các số
nguyên tố khác nhau, trong đó các thừa số được viết theo thứ tự không giảm.
Chứng minh. Giả sử tồn tại những số không viết được thành tích các số
nguyên tố. Gọi n là số bé nhất trong các số đó. Như vậy, n phải là hợp số,

n  a.b , với 1 < a, b < n. Do định nghĩa của n, các số a và b phân tích đưa
thành tích của các số nguyên tố, nghĩa là n cũng phân tích được. Mâu thuẫn
với giả thiết. Vậy mọi số đều phân tích được thành tích của các số nguyên tố.


6

Chúng ta còn phải chứng minh phân tích là duy nhất. Giả sử ta có:
n = p 1 p 2 …p r = q 1 q 2 … q s ,
trong đó p1, p2,..., pr , q1, q2,..., qs là các số nguyên tố. Giản ước những số
nguyên tố bằng nhau có mặt trong hai vế, ta được đẳng thức

pi1 pi2 ...piu  q j1 q j2 ...q jv , trong đó không có số nguyên tố nào có mặt cả ở hai
vế. Như vậy, vế trái chia hết cho q j1 và do đó phải tồn tại một thừa số của tích
chia hết cho q j1 : điều đó vô lý, vì đây là tích của các số nguyên tố khác với

q j1 . Ta gọi phân tích số nguyên ra thừa số nguyên tố là phân tích số nguyên.
Như vậy, với mọi số nguyên n > 1, ta luôn tìm được các số nguyên tố


khác nhau và các số tự nhiên 1 ,..., r sao cho n  p1 1 ...pr r . Dễ dàng thấy

rằng (1  1)...(r  1) là số lượng các ước số dương của n.

Hệ quả 1.1. Nếu p là một số nguyên tố và p | ab thì ít nhất một trong 2
số a, b phải chia hết cho p.
Ước chung lớn nhất của 2 số tự nhiên a, b là số lớn nhất trong tập các
ước chung của 2 số đó, được kí hiệu là UCLN(a, b) hay đơn giản là (a, b).
Như vậy, nếu d | a và d | b thì d | UCLN(a, b).
Khi 2 số tự nhiên có ước chung lớn nhất là 1 thì chúng được gọi là
nguyên tố cùng nhau.
1.1.2. Thuật toán Euclid và mở rộng
a. Thuật toán Euclid
El. (Kết thúc?) Nếu b = 0, in ra a và kết thúc thuật toán.
E2. (Chia Euclid) Đặt r ← a mod b, a ← b, b ← r, và quay về bước El.
Ví dụ 1.1. Ta tính UCLN(345,1127) bằng thuật toán Euclid.
Ta có: d = (345,1127) = (92,345) = (69,92) = (23,69) =(0,23) = 23.
Như vậy, UCLN(345,1127) = 23.


7

b. Thuật toán Euclid mở rộng
Cho hai số nguyên không âm u, v. Tìm (u 1 ,u 2 ,u 3 ) sao cho
(u, v) = u3 = uu 1 + vu2
Trong tính toán, ta thêm vào các ẩn phụ (v 1 ,v 2,v3), (t 1 ,t 2 ,t 3 ) và luôn có
trong mọi bước các đẳng thức sau đây:
ut1 + vt2 = t3, uv 1 + vv2 = v3, uu 1 + vu2 = u3
Edl. (Xuất phát) Đặt (u1,u2,u 3) ← (1, 0, u), (v1,v2,v3) ← (0, 1, v).
Ed2. (Kiểm tra v3 = 0 ?) Nếu v3 = 0, thuật toán kết thúc.

u 
Ed3. (Chia, trừ). Đặt q ←  3  , và sau đó đặt
 v3 

(t1,t 2 ,t 3 ) ← (u1,u2,u3) - q(v1,v2,v3),
(u1,u2,u3) ← (v1,v2,v3), (v1,v2,v3) ← (t1,t 2 ,t 3 )
và quay về bước Ed2.
Ví dụ 1.2. Cho a = 74, b = 28. Dùng thuật toán Euclid ta có:
- Bước 1: u1 = 1, u2 = 0, u3 = 74, v1 = 0, v2 = 1, v3 = 28.
- Bước 2: q = 2, u 1 = 0, u2 = 1, u3 = 28, v1 = 1, v2 = -2, v3 = 18.
- Bước 3: q = 1, u 1 = 1, u2 = -2, u3 = 18, v1 = -1, v2 = 3, v3 = 10.
- Bước 4: q = 1, u 1 = -1, u2 = 3, u3 = 10, v1 = 2, v2 = -5, v3 = 8.
- Bước 5: q = 1, u 1 = 2, u2 = -5, u3 = 8, v1 = -3, v2 = 8, v3 = 2.
- Bước 6: q = 4, u 1 = -3, u2 = 8, u3 = 2, v1 = 14, v2 = -37, v3 = 0.
Ta có biểu diễn: 2 = (-3).74 + 8.28.
Bằng cách theo dõi thương tìm được trong suốt thuật toán, ta có thể xác
định các số nguyên m và n với UCLN(a,b) = m.a + n.b. Thuật toán tìm m
và n như trên được gọi là thuật toán Euclid mở rộng.


8

1.1.3. Phi - hàm Euler
Định nghĩa 1.2. Hàm Euler φ(n) là hàm xác định với mọi số nguyên
dương n, được định nghĩa là số các số nguyên dương không vượt quá n và
nguyên tố cùng nhau với n.
Ví dụ 1.3.
n

1

2

3


4

5

6

7

8

9

10

11

12

φ(n)

1

1

2

2

4


2

6

4

6

4

10

4

Hệ quả 1.2. Số p là nguyên tố khi và chỉ khi φ(p) = p – 1.
Tổng quát hơn, khi p là số nguyên tố và r là một số nguyên dương bất kì
φ(pr) = pr-1(p-1) = pr(1 – 1/p).

thì:

Định lý 1.3. Hàm Euler là một hàm nhân tính, nghĩa là với m, n là các số
nguyên dương nguyên tố cùng nhau, ta có: φ(m.n) = φ(m). φ(n).
Chứng minh.
Ta viết các số nguyên dương không vượt quá m.n thành bảng sau:
1
2
3
…
r

…
m

m +1
m +2
m +3
…
m+r
…
2m

2m+l
2m+2
2m+3
…
2m+r
…
3m

…
…
…
…
...
…
…

(n - l)m+1
(n - l)m+2
(n - l)m+3

…
(n - l)m+r
…
m.n

Bây giờ giả sử r là một số nguyên không vượt quá m. Giả sử
( m, r )  d  1 . Khi đó, không số nào trong dòng thứ r nguyên tố cùng nhau

với m.n, và mỗi phần tử của dòng đó đều có dạng km + r, 1  k  n  1 ,
d | ( km  r ) vì d | m , d | r .

Vậy để tìm các số trong bảng mà nguyên tố cùng nhau với m.n, ta chỉ cần
xem dòng thứ r với (m,r) = 1. Ta xét một dòng như vậy, nó chứa các số


9

r , m  r ,...(n  1)m  r . Vì (r,m) = 1 nên mỗi số nguyên trong dòng đều
nguyên tố cùng nhau với n.
Vậy, n số nguyên trong dòng lập thành hệ thặng dư đầy đủ modulo m.
Do các số đó cũng nguyên tố cùng nhau với m nên chúng nguyên tố cùng
nhau với m.n, nên ta suy ra φ(m.n) = φ(m). φ(n).
Hệ quả 1.3. Giả sử n  p1a p2a ... pka là phân tích của n thành thừa số
1

2

k



1 
1  
1 
nguyên tố. Khi đó ta có: (n )  n 1   1   ...1   .
p1 
p2  
pk 

1.1.4. Phép tính đồng dư và phương trình đồng dư
Định nghĩa 1.3. Giả sử m là một số nguyên dương. Ta nói, hai số nguyên
a và b là đồng dư với nhau modulo m nếu m chia hết hiệu a - b.
Để chỉ a đồng dư với b modulo m, ta ký hiệu: a  b (mod m) (gọi là
đồng dư thức). Điều này có nghĩa là số dư tìm được trong phép chia a và b
cho m là bằng nhau. Dễ dàng có được các tính chất sau.
Mệnh đề 1.1.
1. a  a (mod m )
2. Nếu a  b (mod m) thì b  a (mod m)

a  b (mod m)
3. Nếu 
thì a  c (mod m)
b  c (mod m)
4. Nếu a  b (mod m), c  d (mod m)
thì a ± c  b ± d (mod m),a.c  b.d (mod m)
Từ đây suy ra quan hệ đồng dư modulo m là một quan hệ tương đương
__

trên  . Lớp tương đương của x∈  là x   x  km | k  . Như vậy, chỉ có n
__ __


________



__ __

________



lớp tương đương là 0, 1,... m  1 , ký hiệu:  m  0, 1,... m  1 .

 m trở thành một vành với hai phép toán:

__

__

________

__ __

____

x  y  x  y , x . y  xy .


10

__


Phần tử x   m là khả nghịch (đối với phép nhân) khi và chỉ khi
( x, m)  1 . Do đó, nhóm nhân Um các phần tử khả nghịch trong  m có

| U m | ( m) .
__

__

__

Nếu U m  {r1 , r2 ,... , r ( m ) } thì r1 , r2 ,..., r ( m )  được gọi là thặng dư thu gọn
modulo m.
Phương trình đồng dư tuyến tính ax  b (mod m) thỏa mãn:
Khi UCLN(a,m) = 1 thì có ngay nghiệm x  a -1b (mod m).
Khi UCLN(a,m) = g thì có hai khả năng xảy ra:
1. Nếu g chia hết b thì phương trình đã cho tương đương với phương
trình (a/g)x  (b/g)(mod m/g) và (a/g, m/g) = 1.
2. Nếu g không chia hết b thì phương trình vô nghiệm.
1.1.5. Định lý Fermat và các mở rộng
Định lý 1.4 (Định lý Fermat nhỏ). Nếu p là một số nguyên tố còn a là
một số nguyên thì ap  a (mod p). Nếu p không chia hết a thì a p- 1  1(mod p).
Chứng minh. Với a không chia hết cho p hay (a, p) = 1, ta có
__

a  Up

(nhóm

__ __


________

các

phần

__ ____

tử

khả

_____________

U p  {1, 2,... p  1}  {a, 2a,... ( p  1) a } ,
__ p 1

nghịch

trong

__ ____

nên

 p ).

_____________


Do
__ __

đó,
________

a .2a ... ( p  1) a  1 .2... p  1

__

 1 hay a p 1  1(mod p ) .

hay a

Định lý 1.5 (Định lý mở rộng (Euler)). Nếu m là số nguyên dương và a
là số nguyên tố cùng nhau với m thì a ( m )  1(mod m)
__

__

__

__

Chứng minh. Giả sử U m  {r1 , r2 ,... , r ( m ) } . Do (a, m) = 1, ta có a U m ,
__ __

__ __

__ __


____ ____

____

__ __

__

nên U m  {a r1 , a r2 ,... , a r ( m ) } . Vì vậy ar1 . ar2 ... ar ( m ) = r1 . r2 ... r ( m ) hay
__  ( m )

a

__

 1 hay a ( m )  1(mod m) .


11

Ví dụ 1.4. Tính 21000000 mod 77.
Ta có 77 = 11.7, φ(11) = 10, φ(7) = 6. Bội chung nhỏ nhất của 10 và 6
là 30. Do 210  1(mod11) và 26  1(mod 7) , ta có 230  1(mod 77) .
Mặt khác, 1000000 = 30.33333 + 10. Vậy 21000000 ≡ 2 10 ≡ 23 (mod 77).
Trong trường hợp riêng, khi m là số nguyên tố thì  (m) = m - 1 và ta có
định lý Fermat nhỏ.
Hệ quả 1.4. Nếu (c, m) = 1 và a  b (mod φ(m)) với a, b là các số tự
nhiên, thì c a  cb (mod m).
Hệ quả 1.5. Nếu e, d là các số nguyên thỏa mãn e.d  1 (mod  (m))

thì với mọi số c nguyên tố cùng nhau với m, ta có (ce)d  c (mod m).
Hệ quả này đóng vai trò then chốt trong việc thiết lập các hệ mã mũ và
hệ mã RSA ở Chương 3.
1.1.6. Tính toán với đồng dư của luỹ thừa bậc lớn
Ngoài việc sử dụng hệ quả của Định lý Euler để tính toán người ta còn
thường hay sử dụng nhất là phương pháp bình phương liên tiếp sau đây. Để
hiểu rõ phương pháp này chỉ cần xem ví dụ sau:
Ví dụ 1.5. Tính 70923 (mod 3137)
Ta có 23 = 1+2+4+16 = 20 + 2 1 + 22 + 24
7091(mod 3137) = 709
7092(mod 3137) = 761
7094(mod 3137) = 761 2 (mod 3137) = 1913
7098(mod 3137) = 19132 (mod 3137) = 1827
70916(mod 3137) = 18272 (mod 3137) = 161.
Ta lấy tích các lũy thừa bậc 24, 22, 21, 20 (rút gọn theo modulo 3137) và
thu được kết quả: 709 23 (mod 3137) = 709.761.1913.161(mod 3137) = 907.


12

1.1.7. Định lý Phần dư Trung Hoa
Định lý 1.6. Giả sử m1, m2,…, m r là các số nguyên dương nguyên tố cùng
nhau từng đôi một. Khi đó, hệ phương trình đồng dư:

x  ai (mod mi ) , i = 1, 2, …, r
có nghiệm duy nhất modulo M = m1m 2…m r .
Chứng minh. Đặt M k 
__

____


___

____
M
, ta có (Mk, mk) = 1 hay M k U mk . Do đó
mk

__

 yk  U mk sao cho M k . yk  1 trong U mk hay M k yk  1(mod mk ) . Đặt
x  a1M 1 y1  a2 M 2 y2  ...  ar M r yr ,
ta có x chính là nghiệm của hệ đang xét.
Giả sử x0, x1 là hai nghiệm của hệ. Khi đó với mỗi k,

x0  x1  ak (mod mk ) , nên mk | ( x0  x1 ) . Vì (mk , m j )  1, k  j , nên ta có
M | ( x0  x1 ) .
Nhận xét. Định lý Phần dư Trung Hoa cho phép tính toán đồng dư theo
modulo của một số lớn (tích của nhiều số nguyên tố cùng nhau) thông qua
tính toán đồng dư theo modulo các số nhỏ (từng thừa số). Điều này sẽ hỗ trợ
trong công việc thám mã sau này.
Ví dụ 1.6. Tìm nghiệm của hệ sau modulo 57057:

 x  2(mod 3)
 x  5(mod 7)

 x  4(mod11)
 x  9(mod13)

 x  6(mod19)


M
M
 19019, M 2 
 8151,
3
7
M
M
M
M3 
 5187, M 4 
 4389, M 5 
 3003 .
11
13
19
M  3.7.11.13.19  57057, M 1 


13

___

____ 1

__

M 1  2(mod3)  y1  M 1  2 trong  3  y1  2
___


____ 1

__

M 2  3(mod 7)  y2  M 2  5 trong  7  y2  5
___

____ 1

__

___

____ 1

__

M 3  6(mod11)  y3  M 3  2 trong  11  y3  2
M 4  8(mod13)  y4  M 4  5 trong  13  y4  5
___

____ 1

__

M 5  1(mod19)  y5  M 5  1 trong  19  y5  1
Đặt x  a1M 1 y1  a2 M 2 y2  a3 M 3 y3  a4 M 4 y4  a5 M 5 y5  536870 .
Vậy hệ phương trình có nghiệm duy nhất:


x  536870(mod57057)  23357(mod57057) .
1.1.8. Thặng dư bình phương và ký hiệu Legendre
Định nghĩa 1.4. Cho số nguyên tố p. Số nguyên a được gọi là thặng dư
bình phương (mod p) nếu như a và p nguyên tố cùng nhau và tồn tại số
nguyên x thỏa mãn phương trình x2 ≡ a (mod p).
Nguyên lý căn bậc 2. Một trong hai "nghiệm" của thặng dư bình phương
cũng là một thặng dư bình phương.
Ví dụ 1.7. Lấy p = 11 ta có a = 4 là một thặng dư bình phương. Nó có
hai nghiệm là 2 và 9, trong đó 9 là một thặng dư bình phương (dễ dàng kiểm
tra 32  9 (mod 11) hoặc 82  9 (mod 11)).
Định nghĩa 1.5 (Ký hiệu Legendre). Với số nguyên tố p > 2 và số
nguyên bất kỳ a, số nguyên sau gọi là ký hiệu Legendre:
a
L(a,p) :=   = a
 p 

p 1
2

0

a
và L(a,p) :=   = 1
 p 


(mod p)
nếu a chia hết cho p
nếu a là một thặng dư bình phương (mod p)


-1 các trường hợp còn lại

Ta có thể mở rộng khái niệm kí hiệu trên cho trường hợp p không phải là
nguyên tố, nhưng chỉ xét những số a trong hệ thặng dư thu gọn của p.


14

Định nghĩa 1.6 (Ký hiệu Jacobi). Với số nguyên n = p1.p2 .. . p k , trong
đó p i (i = 1, k ) là các số nguyên tố còn a nằm trong hệ thặng dư thu gọn của
n, số nguyên sau gọi là ký hiệu Jacobi:
J(a,n) = L(a,p 1 )L(a,p 2 ) . . . L(a,p k )
Như vậy khi n là số nguyên tố thì J(a,n) = L(a,n).
1.2. LIÊN PHÂN SỐ
1.2.1. Khái niệm liên phân số

a
với a, b nguyên và b > 0. Ta thực
b
hiện thuật toán Euclid trên a, b. Giả sử ta được:
Định nghĩa 1.7. Cho một số hữu tỉ

a  ba0  r0 ,

(0  r0  b)

b  r0a1  r1,

(0  r1  r0 )


.......................
rn 3  rn  2an 1  rn 1, (0  rn 1  rn  2 )
rn  2  rn 1an
a
có thể viết:
b
r
a
1
1
 ao  o  ao   ....  ao 
b
1
b
b
a1 
1
ro
  an 1 
an
a
Cách viết như trên được gọi là biểu diễn số hữu tỉ dưới dạng liên phân
b

Như vậy, phân số

số.
Để đơn giản, ta dùng cách viết

a

= [a0;a1,...,an]. Liên phân số
b

a0 ; a1,..., an  được gọi là liên phân số hữu hạn (cấp n).
Như vậy, dùng thuật toán Euclid có thể biểu diễn mọi số hữu tỉ dưới
dạng liên phân số hữu hạn. Ngược lại, rõ ràng mỗi liên phân số hữu hạn là
một số hữu tỉ.


15

Giả sử x là một số thực tuỳ ý. Đặt ao = [x], phần nguyên của x, và
1
1
- a1.
 , x1 =
xo
 xo 

x0  x  a0 là phần lẻ của x. Tiếp theo đó ta đặt a1 = 

 1 
1
Với mỗi i = 2,... , đặt a i = 
- ai. Nếu ở bước thứ i nào
 , xi =
xi 1
 xi 1 

đó, xi = 0 thì quá trình kết thúc (điều này xảy ra khi và chỉ khi x là số hữu tỷ ).

Ngược lại, ta có x biểu diễn dưới dạng phân số liên tục vô hạn:

1

x  ao 
a1 

1


1
an  

Để thuận tiện, ta còn có thể dùng cách viết sau đây:

x  ao 

1
1
1

 ... 
 ...
a1  a2 
an 

Các liên phân số định nghĩa như trên với các số a i nguyên gọi là các liên
phân số đơn giản. Khi không đòi hỏi a i là các số nguyên, mà có thể là số thực
tuỳ ý, ta dùng cách viết


x   ao ;a1 ,...,an   ao 

1
1
1

 ... 
a1  a2 
an

1.2.2. Giản phân
Định nghĩa 1.8. Cho liên phân số (hữu hạn hoặc vô hạn)

  [a0 ; a1 , a2 ,...] .
Ta gọi giản phân thứ k (hay cấp k) của liên phân số δ là phân số  k 
trong đó pk và qk được xác định bởi:

 p0  a0
,

q0  1

 p1  a1a0  1
,

 q1  a1

 pk  ak pk 1  pk 2
, k = 2, 3, …


 qk  ak qk 1  qk  2

pk
,
qk


16

Mệnh đề 1.2. Ta có  k  [ a0 ; a1 , a2 ,..., ak ] với mọi k = 0, 1, 2, … Đẳng
thức trên có nghĩa là số hữu tỉ biểu diễn bởi phân số  k bằng số hữu tỉ biểu thị
bởi biểu thức [a0 ; a1 , a2 ,..., ak ] . Trong trường hợp δ là liên phân số hữu hạn cấp
n thì ta có k ≤ n.
Chứng minh. Ta chứng minh bằng quy nạp theo k.

0 
2 

a0
a a 1
1
 a0  [a0 ], 1  1 0
 a0   [a0 ; a1 ] ,
1
a1
a1
p2 a2 p1  p0 a2 ( a1a0  1)  a0
a2
1
.



 a0 
 a0 +
1
q2 a2 q1  q0
a2 a1  1
a2 a1  1
a1 
a2

Giả sử mệnh đề đúng đến k ≥ 2. Theo giả thiết quy nạp, ta có:

k 

pk ak pk  pk 2
1
.

 [ a0 ;a1 ,..., ak ] = a0 
1
qk ak qk 1  qk  2
a1 
1

ak
1

Xét biểu thức: [a0 ;a1 ,..., ak , ak 1 ] = a0 


a1 

1


1
ak 

1
ak 1

Ta thấy hai biểu thức trên chỉ khác nhau số hạng cuối cùng ak 

1
.
ak 1

Do đó:


1 
 ak 
 pk 1  pk  2
ak 1 
a p  pk 1 pk 1

[a0 ;a1 ,..., ak , ak 1 ] =
 k 1 k

 k 1 .

ak 1qk  qk 1 qk 1

1 
 ak 
 qk 1  qk  2
ak 1 



17

Ví dụ 1.8.
1)

5544
  4;1,1,1,1,1,2,2 và ta có bảng giản phân
1200

k

0

1

2

3

4


5

6

7

ak

4

1

1

1

1

1

2

2

pk

4

5


9

14

23

37

97

231

qk

1

1

2

3

5

8

21

50


2) Hãy tìm liên phân số biểu diễn số   2 .

1
Ta có a0   2   1. Từ đó, 1 
 2  1, a1   1   2 . Tương
2 1
tự, ak  2, k  1 . Vậy

2  1;2,2,2,... .

Bảng sau đây cho một số giản phân đầu tiên
k

0

1

2

3

4

5

6

7

…


ak

1

2

2

2

2

2

2

2

…

pk

1

3

7

17


41

99

239

577

…

qk

1

2

5

12

29

70

169

408

…


Mệnh đề 1.3. Trong hai giản phân liên tiếp δk-1, δk thì giản phân cấp lẻ
lớn hơn giản phân cấp chẵn.
Chứng minh.  k 1   k 

pk 1 pk pk 1qk  pk qk 1


qk 1 qk
qk 1qk

pk 1qk  pk qk 1  pk 1 (ak qk 1  qk  2 )  ( ak pk 1  pk  2 ) qk 1  ( pk 2 qk 1  pk 1qk  2 )
Do đó, pk 1qk  pk qk 1  ( 1) k 1 ( p0 q1  p1q0 )  ( 1) k .
Vậy

(1) k
( 1) k
 k 1   k 
. Vì qk nguyên dương với mọi k nên
là
qk 1qk
qk 1qk

dương khi k chẵn và âm khi k lẻ.