ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN ĐĂNG HIÊN NGHIÊN CỨU VÀ PHÁT TRIỂN
HỆ MẬT MÃ KHÓA CÔNG KHAI ỨNG DỤNG
TRONG BẢO MẬT DỮ LIỆU VÀ XÁC THỰC
CÁC GIAO DỊCH ĐIỆN TỬ LUẬN VĂN THẠC SĨ
Hà Nội – 2010 3
MỤC LỤC

LỜI CẢM ƠN 1
LỜI CAM ĐOAN 2
MỤC LỤC 3
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT 5
DANH MỤC CÁC BẢNG 6
MỞ ĐẦU 7
Chƣơng 1 - GIỚI THIỆU CHUNG VÀ 10
CƠ SỞ TOÁN HỌC CỦA LÝ THUYẾT MẬT MÃ 10
1.1. Giới thiệu chung về mật mã 10
1.1.1. Sơ lƣợc lịch sử về mật mã 10
1.1.2. Các hệ thống mã hóa 12
1.1.3. Mã hóa khóa đối xứng và mã hóa khóa công khai 14
1.1.4. Các bài toán về an toàn thông tin 15
1.1.5. Thám mã và tính an toàn của các hệ mã hóa 16
1.2. Cơ sở toán học của lý thuyết mật mã 17
1.2.1. Số học các số nguyên, thuật toán Euclid 17
1.2.2. Độ phức tạp tính toán 24
Chƣơng 2 - PHƢƠNG PHÁP 29
KIỂM TRA VÀ SINH SỐ NGUYÊN TỐ 29
2.1. Số nguyên tố và định lý cơ bản của số học 29
2.1.1. Định nghĩa số nguyên tố 29

VÀ CẢI TIẾN HỆ MÃ HÓA RABIN 56
4.1. Sự ra đời của hệ mã hóa khóa công khai 56
4.2. Một số bài toán cơ bản 56
4.3. Một số hệ mã hóa khóa công khai 58
4.3.1. Sơ đồ chung hệ mã hóa khoá công khai 58
4.3.2. Hệ mã hóa RSA 59
4.3.3. Hệ mã hóa ElGamal 64
4.3.4. Hệ mã hóa Rabin 67
4.4. Cải tiến hệ mã hóa Rabin 74
4.4.1. Mở rộng hệ mã hóa Rabin với n=p*q*r 74
4.4.2. Sơ đồ hệ mã hóa Rabin với n = p*q*r 74
4.4.3. Tính đúng đắn 75
4.4.4. Công thức của phép biến đổi ngƣợc (tính x) 75
4.4.5. Quy trình giải mã 77
4.4.6. Ví dụ 79
4.4.7. Nhận xét và đánh giá 81
4.5. Một số ứng dụng của mã hóa khóa công khai 83
4.5.1. Tạo vỏ bọc an toàn cho văn bản mật 83
4.5.2. Vấn đề xác thực chủ thể 83
4.5.3. Kết hợp với kỹ thuật thủy vân 85
KẾT LUẬN 86
TÀI LIỆU THAM KHẢO 88
PHỤ LỤC 91



Bảng 2.1.4. Liết kê một vài số Mersenne và cho biết số nào là nguyên tố 32
Bảng 2.2.1. Mô tả sàng Eratosthenes với 100 chữ số 35
Bảng 2.4.1. Số lƣợng các số nguyên tố r vớ k bít 44
Bảng 2.4.2. Thời gian thực hiện của thuật toán AKS 45
Bảng 2.5.1. Mô tả quá trình tính toán của thuật toán Pollar 46
Bảng 3.1.1. Dùng để lƣu trữ giá trị thập phân của 2
i
49
Bảng 3.7.1. liệt kê thời gian thực hiện phép toán lũy thừa mod 55

trong và ngoài nƣớc.
Luận văn này đƣợc thực hiện nhằm mục đích nghiên cứu bảo mật an toàn thông
tin. Luận văn tập trung đi sâu vào nghiên cứu và phát triển hệ mã hóa khóa công khai và
các vấn đề liên quan nhằm mục đích ứng dụng vào trong bảo mật và xác thực. 8
Nội dung chính của Luận văn:
(i) Trình bày thuật toán kiểm tra và sinh số nguyên tố lớn. Nhằm tìm ra các số
nguyên tố lớn làm khóa cho các hệ mã hóa khóa công khai.
(ii) Đề xuất cấu trúc dữ liệu và thuật toán xử lý số nguyên lớn từ đó có thể xây
dựng thƣ viện lập trình giúp ứng dụng các hệ mã hóa khóa công khai. Thực tế xây dựng
cho thấy khả năng xử lý của thƣ viện lên tới hàng nghìn chữ số và tốc độ thực hiện các
phép toán nhanh nhƣ trong ngôn ngữ lập trình, thƣ viện đã có (nội dung này học viên đã
báo cáo, đƣợc phản biện và đăng trong Kỷ yếu hội thảo quốc gia lần thứ XII “Một số vấn
đề chọn lọc của công nghệ thông tin và truyền thông”, Đồng Nai, 8/2009, NXB KHKT
2010).
(iii) Đặc biệt luận văn đƣa ra hƣớng cải tiến hệ mã hóa khóa công khai Rabin nhằm
nâng cao độ an toàn và đƣa ra hƣớng khắc phục một số nhƣợc điểm trong quá trình giải
mã của hệ mã hóa này. Ngoài ra đƣa ra một số công thức tính nghịch đảo để quy trình giải
mã của hệ mã hóa Rabin và Rabin cải tiến đƣợc dễ dàng.
Ngoài phần mở đầu và kết luận, kết cấu của luận văn gồm 4 chƣơng:
- Chƣơng 1 “Giới thiệu chung và cơ sở toán học của lý thuyết mật mã” nhằm
trình bày các vấn đề chung nhất của mật mã, đƣa ra các khái niệm cơ bản. Phần cơ
sở toán học trình bày các kiến thức toán học làm nền cho các nội dung chính trong
luận văn nhƣ: số học các số nguyên, thuật toán Euclid, thuật toán Euclid mở rộng,
lý thuyết đồng dƣ, thặng dƣ thu gọn, phần tử nguyên thủy, phƣơng trình đồng dƣ
tuyến tình và đồng dƣ bậc hai. Ngoài ra trình bày về độ phức tạp thuật toán, hàm
một phía và cửa sập một phía.
- Chƣơng 2 “Phương pháp kiểm tra và sinh số nguyên tố” trình bày các định
10
Chƣơng 1 - GIỚI THIỆU CHUNG VÀ
CƠ SỞ TOÁN HỌC CỦA LÝ THUYẾT MẬT MÃ
Tóm tắt chương: Trong chương này luận văn giới thiệu lịch sử mật mã, các hệ mã, các
bài toàn an toàn thông tin và bài toán thám mã. Đưa ra được một số khái niệm cơ bản
nhất của mã hóa như: bản rõ, bản mã, hệ mã hóa thám mã, khóa mã, mã hóa khóa công
khai, mã hóa khóa đối xứng, mã theo khối, mã theo dòng.v.v…Ngoài ra nội dung chương
cũng trình bày về số học các số nguyên, thuật toán Eucild, thuật toán Euclid mở rộng, lý
thuyết đồng dư, thặng dư thu gọn, phần tử nguyên thủy, phương trình đồng dư tuyến tình
và đồng dư bậc hai. Ngoài ra trình bày về độ phức tạp thuật toán, hàm một phía và cửa

hệ mật mã Hill ra đời năm 1929 là các hệ mã thực hiện phép chuyển dịch (đối với mã
Vigenère) hay phép thay thế (mã Hill) đồng thời trên một nhóm ký tự chứ không phải trên 11
từng ký tự riêng rẽ. Vấn đề thám mã, ngƣợc lại, khi thành công thƣờng đƣa đến những
cống hiến nổi trội và ấn tƣợng trong những tình huống gay cấn của các cuộc đấu tranh, và
cũng thƣờng đòi hỏi nhiều tài năng phát hiện với những kinh nghiệm và suy luận tinh tế
hơn.
Nhƣ vậy, trƣớc đây mật mã chỉ đƣợc hiểu theo nghĩa hẹp, chủ yếu dùng đề bảo
mật dữ liệu, ngƣời ta quan niệm: mật mã học là khoa học nghiên cứu mật mã: tạo mã và
phân tích mã (thám mã) [16].
Bƣớc sang thế kỷ 20, với những tiến bộ liên tục của kỹ thuật tính toán và truyền
thông, ngành mật mã cũng đã có những tiến bộ to lớn. Vào những thập niên đầu của thế
kỷ, sự phát triển của các kỹ thuật biểu diễn, truyền và xử lý tín hiệu đã có tác động giúp
cho các hoạt động lập và giải mật mã từ thủ công chuyển sang cơ giới hóa rồi điện tử hóa.
Các văn bản, các bản mật mã trƣớc đây đƣợc viết bằng ngôn ngữ thông thƣờng nay đƣợc
chuyển bằng kỹ thuật số thành các dãy tín hiệu nhị phân, tức các dãy bit, và các phép biến
đổi trên các dãy ký tự đƣợc chuyển thành các phép biến đổi trên các dãy bit, hay các dãy
số, việc thực hiện các phép lập mã, giải mã trở thành việc thực hiện các hàm số số học.
Toán học và kỹ thuật tính toán bắt đầu trở thành công cụ cho việc phát triển khoa học về
mật mã. Khái niệm trung tâm của khoa học mật mã là khái niệm bí mật. Đó là một khái
niệm phổ biến trong đời sống, nhƣng liệu có thể cho nó một nội dung có thể định nghĩa
đƣợc một cách toán học không? Khái niệm bí mật thoạt đầu đƣợc gắn với khái niệm ngẫu
nhiên, rồi về sau trong những thập niên gần đây, với khái niệm phức tạp, cụ thể hơn là
khái niệm độ phức tạp tính toán. Việc sử dụng lý thuyết xác suất và ngẫu nhiên làm cơ sở
để nghiên cứu mật mã đã giúp C.Shannon đƣa ra khái niệm bí mật hoàn toàn của một hệ
mật mã từ năm 1948, khởi đầu cho một lý thuyết xác suất về mật mã. Trong thực tiễn làm
mật mã, các dãy bit ngẫu nhiên đƣợc dùng để trộn với bản rõ (dƣới dạng một dãy bit xác
định) thành ra bản mật mã. Làm thế nào để tạo ra các dãy bit ngẫu nhiên? Có thể tạo ra
12
Lý thuyết về độ phức tạp tính toán ra đời từ giữa những năm 1960 đã cho một cách
thích hợp để quy yêu cầu bí mật hoặc ngẫu nhiên về một yêu cầu có thể định nghĩa đƣợc
là yêu cầu về độ phức tạp tính toán. Bây giờ có thể nói: một giải pháp mật mã là bảo đảm
bí mật, nếu mọi thuật toán thám mã, nếu có, đều phải đƣợc thực hiện với độ phức tạp tính
toán cực lớn! Cực lớn là bao nhiêu? Là vƣợt quá giới hạn khả năng tính toán (bao gồm cả
máy tính) mà ngƣời thám mã có thể có. Về lý thuyết, có thể xem đó là những độ phức tạp
tính toán với tốc độ tăng vƣợt quá hàm mũ, hoặc thuộc loại NP-khó. Tuy nhiên, lý thuyết
độ phức tạp tính toán không chỉ cống hiến cho ta một khái niệm để giúp chính xác hóa
tiêu chuẩn bí mật của các giải pháp mật mã, mà còn mở ra một giai đoạn mới của ngành
mật mã, biến ngành mật mã thành một khoa học có nội dung lý luận phong phú và có
những ứng dụng thực tiễn quan trọng trong nhiều lĩnh vực của đời sống hiện đại. Bƣớc
ngoặt có tính cách mạng trong lịch sử khoa học mật mã hiện đại xảy ra vào năm 1976 khi
hai tác giả Diffie và Hellman đƣa ra khái niệm về mã hóa khóa công khai và một phƣơng
pháp trao đổi công khai để tạo ra một khóa bí mật chung mà tính an toàn đƣợc bảo đảm
bởi độ khó của một bài toán học cụ thể (là bài toán tính “logarit rời rạc”). Hai năm sau,
năm 1978, Rivest, Shamir và Adleman tìm ra một hệ mã hóa khóa công khai và một sơ đồ
chữ ký điện tử hoàn toàn có thể ứng dụng trong thực tiễn, tính bảo mật và an toàn của
chúng đƣợc bảo đảm bằng độ phức tạp của một bài toán số học nổi tiếng là bài toán phân
tích số nguyên thành các thừa số nguyên tố. Sau khi phát minh ra hệ mã hóa đó (mà nay ta
thƣờng gọi là hệ RSA), việc nghiên cứu để phát minh ra các hệ mã hóa khóa công khai
khác và ứng dụng các hệ mã hóa khóa công khai vào các bài toán khác nhau của an toàn
thông tin đã đƣợc tiến hành rộng rãi, lý thuyết mật mã và an toàn thông tin trở thành một
lĩnh vực khoa học đƣợc phát triển nhanh trong vài ba thập niên cuối của thế kỷ 20, lôi
cuốn theo sự phát triển của một số bộ môn của toán học và tin học.
Lúc này, mật mã được hiểu theo nghĩa rộng: mật mã là một trong những công cụ
hiệu quả bảo đảm an toàn thông tin nói chúng: bảo mật, bảo toàn, xác thực, chống chối
cãi, …[16]. Để thực hiện đƣợc ngƣời ta sử dụng các ký thuật mật mã: mã hóa, ký số, các

: C →P là hai hàm cho bởi:

x

P. e
k
(x) = E(K,x);

y

C: d
k
(y) = D(K, y).
e
k
và d
k
được gọi lần lượt là hàm lập mã và hàm giải mã ứng với khóa mã hóa K.
Các hàm đó phải thỏa mãn hệ thức:

x

P: d
k
(e
k
(x))= x.
Về sau, để thuận tiện gọi một danh sách (1.1.1) thỏa mãn các tính chất kể trên là
một sơ đồ hệ thống mã hóa, còn khi đã chọn cố định một khóa K, thì danh sách (P, C, e
k

b
c
c
d
d
e
e
f
f
g
g
h
h
i
i
j
j
k
k
l
l
m
m
n
n
o
o
p
p
q

1
6
1
7
1
8
1
9
2
1
0
2
1
1
2
1
2
2
1
3
2
1
4
2
1
5
1
1
6
1

m
, Z
n
m
.
1.1.2.2. Mã theo khối và mã theo dòng [7]
Nhƣ đã nói ở trên, bản rõ của thông báo muốn gửi đi thƣờng là một dãy ký tự,
trong khi theo định nghĩa của sơ đồ mã hóa, hàm lập mã và hàm giải mã đƣợc định nghĩa
cho từng ký tự. Từ các định nghĩa của hàm lập mã và hàm giải mã, mở rộng thành thuật
toán lập mã (và giải mã) xác định cho mọi bản rõ (bản mã) nhƣ sau: 14
Theo cách mã theo khối (block cipher), trƣớc hết xác định một độ dài khối (chẳng
hạn là k), tiếp đó mở rộng không gian khóa từ K thành K* và với mỗi K = K
1
K
k

K*,
mở rộng e
k
và d
k
thành các thuật toán e
k
: P
k
→C
k

); d
k
(y
l
y
k
) = d
kl
(Y
l
) d
kk
(Y
k
)
Giả thử bản rõ muốn lập mã cho nó là dãy ký tự X

P
k
. Ta cắt X thành từng khối,
mỗi khối có độ dài K, khối cuối cùng có thể có độ dài < K, luôn có thể giả thiết là có thể
bổ sung vào phần cuối của khối một số ký tự qui ƣớc nào đó để nó cũng có độ dài k. Do
đó có thể giả thiết X = X
l
X
m
, trong đó mỗi X
l
, ,X
m

(Y
m
)=X
l
X
m
= X.
Cách mã theo khối đơn giản và thông dụng nhất là khi chọn độ dài khối k=1. Khi
đó với mọi bản rõ X-x
l
x
m


P* , có
e
k
(X) = e
k
(x
l
x
m
) = e
k
(x
l
) e
k
(x

m
).
Giải mã Y = y
k
(X) ta đƣợc
d
k
(Y) = d
kl
(e
kl
(x
l
)) d
km
(e
km
(x
m
)) = x
l
x
m
= X
Để sử dụng cách lập mã theo dòng, ngoài sơ đồ mã hóa gốc còn phải có một dòng
khóa, tức là một dãy có độ dài tùy ý các ký tự khóa. Đó thƣờng là các dãy các ký tự khóa
đƣợc sinh ra bởi một bộ “tạo dãy ngẫu nhiên” nào đó xuất phát từ một “mầm” chọn trƣớc.
Trong các ứng dụng thực tế, ngƣời ta thƣờng dùng các mã theo dòng có sơ đồ mã hóa gốc
là sơ đồ Vernam với
P = C = K = {0.1}

), các hàm lập mã và giải mã thỏa mãn hệ thức
d
k
(d
k’
(x)) = x với

x

P,
thì đƣợc một hệ mã hóa khóa phi đối xứng. Nhƣ vậy, trong một hệ mã hóa khóa
phi đối xứng, các khóa lập mã và giải mã (K’ và K’’) là khác nhau, nhƣng tất nhiên có
quan hệ với nhau. Trong hai khóa đó, khóa cần phải giữ bí mật là khóa giải mã K’’, còn
khóa lập mã K’ có thể đƣợc công bố công khai; tuy nhiên điều đó chỉ có ý nghĩa thực tiễn
khi việc biết K’ tìm K’’ là cực kỳ khó khăn đến mức hầu nhƣ không thể thực hiện đƣợc.
Một hệ mã hóa khóa phi đối xứng có tính chất nói trên, trong đó khóa lập mã K’ của mỗi
ngƣời tham gia đều đƣợc công bố công khai, đƣợc gọi là hệ mã hóa khóa công khai. Khái
niệm mã hóa khóa công khai mới đƣợc ra đời vào giữa những năm 1970, và ngay sau đó
đã trở thành một khái niệm trung tâm của khoa học mật mã hiện đại.
1.1.4. Các bài toán về an toàn thông tin [7]
Có nhiều bài toán khác nhau về yêu cầu an toàn thông tin tùy theo những tình
huống cụ thể khác nhau, nhƣng tựu trung có một số bài toán chung nhất thƣờng gặp trong
thực tiễn là những bài toán sau đây:
- Bảo mật: giữ thông tin đƣợc bí mật đối với tất cả mọi ngƣời, trừ một ít ngƣời có
thẩm quyền đƣợc đọc, biết thông tin.
- Toàn vẹn thông tin: bảo đảm thông tin không bị thay đổi hay xuyên tạc bởi những
kẻ không có thẩm quyền hoặc bằng những phƣơng tiện không đƣợc phép.
- Nhận thực một thực thể: xác nhận danh tính của một thực thể chẳng hạn một
ngƣời, một máy tính cuối trong mạng, một thẻ tín dụng….
- Nhận thực một thông báo: xác nhận nguồn gốc của một thông báo đƣợc gửi đến.

toán thám mã cơ bản là bài toán tìm khóa mã hóa K (hay khóa giải mã K’’). Để giải bài
toán đó, giả thiết ngƣời thám mã biết thông tin về sơ đồ hệ mã hóa đƣợc dùng, kể cả các
phép lập mã và giải mã tổng quát E và D. ngoài ra, ngƣời thám mã có thể biết thêm một
số thông tin khác, tùy theo những thông tin đƣợc biết thêm này mà ta có thể phân loại bài
toán thám mã thành các bài toán cụ thể nhƣ sau:
- Bài toán thám mã chỉ biết bản mã: là bài toán phổ biến nhất, khi ngƣời thám mã
chỉ biết một bản mã hóa Y;
- Bài toán thám mã khi biết cả bản rõ: ngƣời thám mã biết một bản mã hóa Y cùng
với bản rõ tƣơng ứng X;
- Bài toán thám mã khi có bản rõ được chọn: ngƣời thám mã có thể chọn một bản
rõ X, và biết bản mã hóa tƣơng ứng Y. Điều này có thể xảy ra khi ngƣời thám mã chiếm
đƣợc (tạm thời) máy lập mã;
- Bài toán thám mã khi có bản mã được chọn: ngƣời thám mã có thể chọn một bản
mã hóa Y, và biết bản rõ tƣơng ứng X. Điều này có thể xảy ra khi ngƣời thám mã chiếm
đƣợc tạm thời máy giải mã.
1.1.5.2. Tính an toàn của một hệ mã hóa
Tính an toàn của một hệ thống mã hóa phụ thuộc vào độ khóa khăn của bài toán
thám mã khi sử dụng hệ mã hóa đó. Ngƣời ta đã đề xuất một số cách hiểu cho khái niệm
an toàn của hệ thống mã hóa, để trên cơ sở các cách hiểu đó nghiên cứu tính an toàn của
nhiều hệ mã hóa khác nhau, sau đây ta giới thiệu vài cách hiểu thông dụng nhất:
- An toàn vô điều kiện: giả thiết ngƣời thám mã có đƣợc thông tin về bản mã. Theo
quan niệm lý thuyết thông tin, nếu những hiểu biết về bản mã không thu hẹp đƣợc độ bất
định về bản rõ đối với ngƣời thám mã, thì hệ mã hóa là an toàn vô điều kiện, hay theo 17
thuật ngữ của C.Shannon, hệ là bí mật hoàn toàn. Nhƣ vậy, hệ là an toàn vô điều kiện,
nếu độ bất định về bản rõ sau khi ngƣời thám mã có đƣợc các thông tin (về bản mã) bằng
độ bất định về bản rõ trƣớc đó. Tính an toàn vô điều kiện đã đƣợc nghiên cứu cho một số
hệ mã hóa khóa đối xứng mà ta sẽ trình bày trong chƣơng 3.

chia hết cho b, b chia hết a, a là bội số của b, b là ước số của a, và ký hiệu là b/a. Dễ thấy
ngay rằng số 1 là ƣớc số của mọi số nguyên bất kỳ, số 0 là bội số của mọi số nguyên bất
kỳ, mọi số nguyên a là ƣớc số, đồng thời là bội số của chính nó.
Định lý 1.2.1. Nếu b > 0 và b/a thì gcd(a,b) = b.
Nếu a = bq + thì gcd(a,b) = gcd(b,r).
Một số nguyên m đƣợc gọi là bội số chung của a và b nếu a/m và b/m. Số m đƣợc
gọi là bội số chung bé nhất của a và b, và đƣợc ký hiệu là lcm(a,b), nếu m>0, m là bội số
chung của a và b, và mọi bội số chung của a và b đều là bội của m. Ví dụ lcm(14,21)= 42.
Với hai số nguyên dƣơng a và b bất kỳ ta có quan hệ 18
lcm(a,b).gcd(a,b) = a.b.
Từ định lý 1.2.1. ta suy ra thuật toán sau đây thực hiện việc tìm ƣớc số chung lớn
nhất của hai số nguyên bất kỳ:
Thuật toán Euclide tìm ƣớc số chung lớn nhất:
INPUT: hai số nguyên không âm a và b, với a≥b.
OUTPUT: ước số chung lớn nhất của a và b
1. Trong khi còn b>0, thực hiện:
1.1. đặt r

a mod b,a

b, b

r.
2. Cho ra kết quả (a).
Ví dụ: Dùng thuật toán Euclide tìm gcd(4864, 3458), lần lƣợt đƣợc các giá trị gán
cho các biến a, b và r nhƣ sau:
Bảng 1.2.1. Mô tả quá trình tính toán của thuật toán Euclid

0
0
Cho hai số nguyên bất kỳ a và b, b > 1. Thực hiện phép chia a cho b ta sẽ đƣợc hai
số q và r sao cho
a = b.q + r, o ≤ r <b.
Số q đƣợc gọi là số thương của phép chia a cho b, ký hiệu a div b và số r đƣợc gọi
là số dư của phép chia a cho b, ký hiệu a mod b. Ví dụ: 25div 7 = 3 và 25 mod 7 = 4, -
25div 7 = -4 và – 25 mod 7 = 3.
Một số nguyên d đƣợc gọi là ước số chung của hai số nguyên a và b nếu d/a và
d/b. Số nguyên d đƣợc gọi là ước số chung lớn nhất của a và b nếu d>0, d là ƣớc số
chung của a và b, và mọi ƣớc chung của a và b đều là ƣớc số của d. Ký hiệu ƣớc số chung
lớn nhất của a và b là gcd (a,b). Ví dụ gcd (12, 18) = 6, gcd (-18, 27) = 3.
Dễ thấy rằng với mọi số nguyên dƣơng a ta có gcd (a, 0) = a, ta cũng sẽ qui ƣớc
xem rằng gcd (0,0) = 0.
Một số nguyên a > 1 đƣợc gọi là số nguyên tố, nếu a không có ƣớc số nào ngoài 1
và chính a; và đƣợc gọi là hợp số, nếu không phải là nguyên tố. Ví dụ các số 2, 3, 5, 7 là
số nguyên tố; các số 6, 8, 10, 12, 14, 15 là hợp số. Hai số a và b đƣợc gọi là nguyên tố với 19
nhau, nếu chúng không có ƣớc số chung nào khác 1, tức là nếu gcd (a,b) = 1. Một số
nguyên n > 1 bất kỳ đều có thể viết dƣới dạng
n = p
1
a1
. p
2
a2
p
k

a, x

1, y

0 và cho ra (d, x, y).
2. Đặt x
2
= 1, x
1
= 0, y
2
= 0, y
1
= 1.
3. Trong khi còn b > 0 thực hiện:
3.1 q

a divb, r

a mod b, x

x
2
– qx
1
, y

y
2
– qy

x2, y

y2, và cho ra kết quả (d, x, y)
Ví dụ: Dùng thuật toán Euclide mở rộng cho các số a = 4864 và b = 3458, lần lƣợt
đƣợc các giá trị sau đây cho các biến a, b, q, r, x, y, x
1
, x
2
, y
1
, y
2
(sau mỗi chu trình thực
hiện hai lệnh 3.1 và 3.2).
Bảng 1.2.2. Mô tả quá trình tính toán của thuật toán Euclid mở rộng
a
b
q
r
x
y
x1
x2
y1
y2
4864
3458

-7
5
-2
-7
3
114
76
5
76
-27
38
-27
5
38
-7
76
38
1
38
32
-45
32
-27
-45
38
38
0
2
0
-91

25
= {0, 1, 2, 24}. Trong Z
25
, 15 +14 = 4, vì 15 + 14 = 29  4 (mod 25).
Tƣơng tự, 15.14  10 trong Z
25
.
Cho a

Z
n
. Một số nguyên x

Z
n
đƣợc gọi là nghịch đảo của a theo modn, nếu a.x
 1 (modn). Nếu có số x nhƣ vậy thì ta nói a là khả nghịch, và ký hiệu x là a
-1
mod n. Thí
dụ 22
-1
mod 25 = 8, vì 22.8 = 186  1 (mod 25). Từ định nghĩa ta có thể suy ra rằng a là
khả nghịch theo mod n khi và chỉ khi gcd (a,n) = 1, tức là khi a và n nguyên tố với nhau.
Dịnh nghĩa phép chia trong Z
n
nhƣ sau:
a : b (mod n) = a.b
-1
mod n.
Phép chia chỉ thực hiện đƣợc khi b là khả nghịch theo mod n. Thí dụ 15 : 22 (mod









)(mod

)(mod
)(mod
222
111
kkk
nax
nax
nax
(1.2.2)
Ký hiệu: n = n
1
.n
2
n
k
, N
i

mod n
i
(có M
i
vì N
i
và n
i
nguyên tố với nhau).
Vídụ: Cặp phƣơng trình x  3 (mod 7) và x  7 (mod 13) có một nghiệm duy nhất x
 59 (mod 91).
Nếu (n
1
, n
2
) = 1, thì cặp phƣơng trình x  a (mod n
1
) và x  a (mod n
2
) có nghiệm
duy nhất x  a (mod n) theo mod n với n = n
1
n
2
.
1.2.1.3. Thặng dƣ thu gọn và phần tử nguyên thủy
Tập Z
n
= {0, 1, 2, , n-1} thƣờng đƣợc gọi là tập các thặng dư đầy đủ theo mod n,
vì mọi số nguyên bất kỳ đều có thể tìm đƣợc trong Z

n
*
lập thành một nhóm con đối với phép nhân của Z
n
, vì trong Z
n
*
phép chia
theo mod n bao giờ cũng thực hiện đƣợc, gọi Z
n
*
là nhóm nhân của Z
n
.
Theo đại học số học, gọi số các phần tử trong một nhóm là cấp của nhóm đó. Ký
hiệu

(n) là số các số nguyên dƣơng bé hơn n và nguyên tố với n. Nhƣ vậy, nhóm Z
n
*
có
cấp

(n), và nếu p là số nguyên tố thì nhóm Z
p
*
có cấp p-1. 22

b
n-1
 (mod p)
(1.2.3)
Nếu b có cấp p-1, tức p-1 là số mũ bé nhất thỏa mãn công thức (1.2.3) thì các phần
tử b, b
2
, , b
p-1
đều khác nhau và theo mod p, chúng lập thành Z
p
*
. Theo thuật ngữ đại số,
khi đó ta nói Z
n
*
là một nhóm cyclic và b là một phần tử sinh, hay phần tử nguyên thủy
của nhóm đó. Trong lý thuyết số, ngƣời ta đã chứng minh đƣợc cái tính chất sau đây của
các phần tử nguyên thủy:
1. Với mọi số nguyên tố p, Z
p
*
là nhóm cyclic, và có

(p-1) phần tử nguyên thủy
2. Nếu p-1= p
1
a1
. p
2

a. Nếu p là số nguyên tố và gcd(a,p) = 1, thì a
p-1
 1 (mod p) (định lý Fermat).
b. Nếu a

Z
n
*
, thì a

(n)
1(mod n). Nếu rs(mod

(n)) thì a
r
a
s
(mod n) (định lý
Euler).
1.2.1.4. Phƣơng trình đồng dƣ bậc hai và thặng dƣ bậc hai
Xét phƣơng trình đồng dƣ bậc hai có dạng đơn giản sau đây:
x
2
 a (mod n),
trong đó n là một số nguyên dƣơng, a là số nguyên với gcd(a,n) = 1, và x là ẩn số. Phƣơng
trình đó không phải bao giờ cũng có nghiệm, khi nó có nghiệm thì ta nói a là một thặng
dư bậc hai mod n; nếu không thì nói a là một bất thặng dư bậc hai mod n. Tập các số
nguyên nguyên tố với n đƣợc phân hoạch thành hai tập con: tập Q
n
các thặng dƣ bậc hai


23
a(
p-1)/2
 b
i(p-1)/2
 1 (mod p).
Phần tử b có cấp p – 1, do đó (p-1) chia hết i(p-1)/2, i phải là số chẵn, i = 2j, và a
có căn bậc hai là  b
j
mod p.
Cho p là một số nguyên tố lẻ. Với mọi a ≥ 0 ta định nghĩa ký hiệu Legendre








p
a

nhƣ sau:








p
a
= 1.
Và theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0, ta có:









p
a
 a
(p-1)/2
(mod p).
Bây giờ ta mở rộng ký hiệu Legengdre để đƣợc ký hiệu Jacobi đối với mọi số
nguyên lẻ n ≥ 1 và mọi số nguyên a ≥ 0, cũng đƣợc ký hiệu bởi






n
a
và đƣợc định nghĩa

























2
2
1
1

Khi n = p là số nguyên tố thì giá trị của các ký hiệu Legendre và Jacobi là nhƣ

=





)8(mod3,1
)8(mod1,1
nkhi
nkhi

3.






n
mm 2.1
=






n
m1
.












)4(mod1)4(mod1,
)4(mod3&)4(mod3,
mnkhi
m
n
mnkhi
m
n 24
Ví dụ: Dùng các tính chất đó, ta tính đƣợc:





7411
2
4
.






7411
117

=






7411
117
= -






117

=






117
5
=






5
117
=






5
2
= - 1
9283 là một số nguyên tố. Do đó, giá trị - 1 của ký hiệu Jacobi


p


)(mod
)1(2
paa
m



do đó x   a
m+1
(mod p) là hai nghiệm của phƣơng trình (1.2.4)
1.2.2. Độ phức tạp tính toán
1.2.3.1. Khái niệm về độ phức tạp tính toán
Lý thuyết thuật toán và các hàm số tính đƣợc ra đời từ những năm 30 của thế kỷ 20
đã đặt nền móng cho việc nghiên cứu các vấn đề “tính đƣợc”, “giải đƣợc” trong toán học,
đƣa đến nhiều kết quả rất quan trọng và lý thú. Nhƣng từ cái “tính đƣợc” một cách trừu
tƣợng, hiểu theo nghĩa tiềm năng, đến việc tính đƣợc trong thực tế của khoa học tính toán
bằng máy tính điện tử, là cả một khoảng cách rất lớn. Vấn đề là do ở chỗ những đòi hỏi về
không gian vật chất và về thời gian để thực hiện các tiến trình tính toán nhiều khi vƣợt
quá xa những khả năng thực tế. Từ đó, vào khoảng giữa những năm 60 (của thế kỷ trƣớc),
một lý thuyết về độ phức tạp tính toán bắt đầu đƣợc hình thành và phát triển nhanh chóng,
cung cấp cho chúng ta nhiều hiểu biết sâu sắc về bản chất phức tạp của các thuật toán và
các bài toán, cả những bài toán thuần túy lý thuyết đến những bài toán thƣờng gặp trong
thực tế. Sau đây giới thiệu sơ lƣợc một số khái niệm cơ bản và vài kết quả sẽ đƣợc dùng
đến của lý thuyết đó.

làm việc có kết thúc trên mọi dữ liệu vào các bài toán, và cho kết quả đúng hoặc sai tùy
theo câu hỏi Q trên dữ liệu đó có trả lời đúng hoặc sai. Bài toán P là giải được trong thời
gian đa thức, nếu có thuật toán giải nó với độ phức tạp thời gian đa thức. Sau đây là vài ví
dụ về các bài toán quyết định:
Bài toán SATISFIABILYTY (viết tắt là SAT):
- Mỗi dữ liệu vào là một công thức F của logic mệnh đề, đƣợc viết dƣới dạng hội
chuẩn tắc, tức dạng hội của một số các “clause”.
- Câu hỏi là: công thức F có thỏa đƣợc hay không?
Bài toán CLIQUE:
- Mỗi dữ liệu vào là một graph G và một số nguyên k.
- Mỗi câu hỏi là: Graph G có một clique với ≥ k đỉnh hay không? (một clique của
G là một graph con đầy đủ của G).
Bài toán KNAPSACK:
- Mỗi dữ liệu là một bộ n + 1 số nguyên dƣơng I = (s
1
, s
n
; T).
- Câu hỏi là: có hay không một vectơ Boole (x
1
, ,x
n
) sao cho



n
i
Tsixi
1