ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
&&&
TIỂU LUẬN
MẬT MÃ VÀ AN TOÀN DỮ LIỆU
Đề tài: “VẤN ĐỀ KIỂM TRA SỐ NGUYÊN TỐ LỚN”
Giảng viên: PGS.TS Trịnh Nhật Tiến
Học viên thực hiện: Nguyễn Thế Tùng, K20
Lớp MH: INT 6010 2
Mã HV: 13025189
Hà Nội, 05/2014
1/ Giới thiệu
Bài toán kiểm tra số nguyên tố lớn là một trong những bài toán cơ bản nhưng hết
sức quan trọng trong lĩnh vực an toàn và bảo mật thông tin. Số nguyên tố cũng thường
được dùng để tạo khóa cho các thông tin nhạy cảm mà người gửi cũng như người
nhận đều muốn giữ bí mật. Ứng dụng chính của số nguyên tố là trong lĩnh vực mã hóa
(cryptography), trong đó chúng ta cần tạo ra những số nguyên tố với hàng trăm chữ số.
Kiểm tra một số có phải số nguyên tố hay không là một bài toán khá quan trọng trong
khoa học máy tính, vì số nguyên tố được sử dụng rất rộng rãi trong các giải thuật mã hóa
dùng khóa mở (public key cryptography algorithms). Ngoài ra nó còn được ứng dụng
trong các bộ phát sinh số giả ngẫu nhiên (pseudorandom) và bảng hash (hash table).
2/ Các khái niệm cơ bản
2.1/ Số nguyên tố
Số tự nhiên p, lớn hơn 1 gọi là số nguyên tố nếu như nó chỉ chia hết cho 1 và chính nó.
Định lý cơ bản của số học nói rằng, bất kỳ số tự nhiên n, lớn hơn 1 có thể phân tích thành
tích các số nguyên tố. Tức là một số tự nhiên có thể biểu diễn dưới dạng sau
k
k
ppn
αα


là 3. Số 1 là nguyên tố cùng nhau với mọi số nguyên. Nhưng cũng có những trường hợp
đặc biệt, hợp số là số nguyên tố cùng nhau. VD: 6 và 25 tuy là hợp số nhưng chúng có
Ước chung lớn nhất là 1 nên chúng là những số nguyên tố cùng nhau.
2.3/ Hợp số
Cho hai số tự nhiên a, b. Nếu có số tự nhiên q sao cho a=b*q thì ta nói a chia hết cho b
hay b chia hết a. Khi đó ta cũng nói a là bội của b, b là ước của a. Mọi số tự nhiên lớn
hơn 1 đều có ít nhất hai ước tự nhiên là 1 và chính nó. Các ước này được gọi là ước tầm
thường của n. Một số tự nhiên lớn hơn 1, không chia hết cho số nào khác ngoài các ước
tầm thường, được gọi là số nguyên tố. Các số tự nhiên lớn hơn 1 và không nguyên tố thì
được gọi là hợp số. Một hợp số là tích của ít nhất 2 số nguyên tố.
Ví dụ: 14 là hợp số vì ngoài việc chia hết cho hai ước tầm thường là 1 và 14 nó còn chia
hết cho 2 và 7.
2.4/ Đồng dư thức
Cho số nguyên dương n, hai số nguyên a,b được gọi là đồng dư theo mô-đun n nếu chúng
cho cùng số dư khi chia cho n (hay là a-b chia hết cho n).
Kí hiệu là:
Ví dụ:
Vì 11 và 5 khi chia cho 3 đều cho số dư là 2.
Nếu số nguyên dương n và số nguyên a nguyên tố cùng nhau thì tồn tại duy nhất một
số sao cho: , số x này được gọi là nghịch
đảo của a theo mô-đun n.
2.5/ Số Fermat
Chúng ta xem số n dạng
12 +=
m
n
, ở đây
Nm
∈
. Nếu m chia hết cho số nguyên tố

Hiện tại chúng ta biết được rằng
43210
,,,, FFFFF
là số nguyên tố, còn các số Fermat tiếp
theo
325
≤≤
k
là hợp số, còn các số tiếp theo thì chưa được kiểm tra.
Để kiểm tra tính nguyên tố của số Fermat chúng ta xem định lý sau
Định lý:
Số
k
Fn =
khi k>0 là số nguyên tố khi và chỉ khi:
)(mod13
2
1
n
n
−≡
−
.
Chứng minh: Chúng ta chứng minh điều kiện đủ. Chúng ta có:
k
n
2
21 =−
. Từ
)(mod13

≡≡
−kk
. Bởi vậy n>3,
)4(mod1),3(mod2 ≡≡ nn
. Theo định luật bình phương (định lý Gausse) ta có
1
3
2
3
)1.(
3
3
4
)13)(1(
−=






=






=−



.
2.6/ Số Mersenn
Chúng ta xem số n dạng
12 −=
m
n
. Nếu m là hợp số, m=ab,
ba
≤<
1
, thì
12 −=
ab
n
chia hết cho
12 −=
a
n
. Cho nên số n là nguyên tố chi khi m là số nguyên tố.
Định nghĩa: Cho p là số nguyên tố, và
12
−=
p
p
M
cũng là số nguyên tố. Và số
p
M
gọi

−
Định lý: Cho p là số nguyên tố,
)4(mod3≡p
,
12
−=
p
p
M
. Số Fermat
p
F
là số nguyên
tố khi và chi khỉ
)(mod1
2/)1(
p
F
p
FM
p
−≡
−
.
Chứng minh: Theo định lý nhỏ Fermat ta có
)(mod22
12
p
M
p

F
F
M
M
p








≡








≡













≡−≡−=
+
p
k
p
M
M
2.7/ Dãy số Liuka
Cho dãy số
, ,,
210
uuu
và
, ,,,
210
vvv
với
4,2,1,0
1010
==== vvuu
, còn các thành phần
tiếp theo của dãy được tính theo công thức truy hồi
11
4
−+

∈
, sao cho
)(mod1
1
na
n
i
≡
−
,
)(mod1
1
na
i
p
n
i
≠
−
,
thì n là số nguyên tố.
Chứng minh:
Cho
i
m
là bậc của
)(mod na
i
trong
n

i
p
α
trong
*
n
Z
, còn phần tử
)(mod
1
nbbb
k
⋅⋅=
có bậc là
1
1
1
−=⋅⋅ npp
k
k
α
α
trong
*
n
Z
. Điều này
có nghĩa là
n
Z

uu
và định thức D
bằng các biểu thức sau:
jjj
QuPuuuu −===
++ 1210
,1,0
điều kiện là
0≥j
. Cho n là một số
tự nhiên lẻ, n>1,
∏
=
=+
k
i
i
i
qn
1
1
β
- tức là phân tích n+1 ra thừa số nguyên tố, và
1−=







i
qn
i
u
+
,
thì n là số nguyên tố. Nếu như tồn tại dãy số Liuka
{ }
j
u
như thế và D, sao cho
1+n
u
không chia hết cho n, thì n là hợp số.
Định lý: Cho
Nn
∈
, n>1, n là số lẻ,
11
1 RFn
⋅=−
, với
1),(
11
=
RFUCLN
. Giả sử chúng
ta biết được hoàn toàn sự phân tích ra thừa số nguyên tố
∏
=

j
với điều kiện
nF ≥
1
, thì số n là số nguyên tố.
Chứng minh: Giả sử p là ước số nguyên tố của n. Chúng ta chứng minh rằng
np >
,
từ đây dẫn đến n là số nguyên tố.
Từ điều kiện chúng ta có
)(mod1
1
na
n
j
≡
−
dẫn đến
)(mod1
1
pa
n
j
≡
−
, từ đây
1),( =paUCLN
j
và bậc
j

j
α
, và
)1(|
1
1
−=
∏
=
pqF
k
j
j
j
α
. Nghĩa là
nFpFp ≥>≥−
11
,1
.
Chúng ta sẽ chứng minh với sự giúp đỡ của định lý này có thể xây dựng được số
nguyên tố lớn. Chúng ta xây dựng dãy số nguyên tố
,
321
<<< ppp
cho đến khi xây
dựng được số nguyên tố đủ lớn chúng ta cần. Số nguyên tố
1
p
chọn bất kỳ, ví dụ

tprpn
i
s
i
. Đặt
1
1
1
2
−
+
=
i
s
pF
,
tR
=
1
. Rõ ràng rằng
1),(
11
=
RFUCLN
và
chúng ta cũng có
nF >
1
, bởi vì
2

)(mod1
1
2
1
1
naa
nn
≡≡
−−
,
1),1(),1(
1
1
2
2
1
1
=−=−
−
−
−
naUCLNnaUCLN
i
p
n
n
.
Nếu như ta tìm được số a, sao cho
)(mod1
1

i
. Giả sử
11 −
=
i
pF
,
rR =
1
,
1),(
11
=
RFUCLN
.Chúng ta cần tìm một số tự nhiên a sao cho
1),1(),(mod1
1
=−≡
−
naUCLNna
rn
(bởi vì
r
p
n
i
=
−
−1
1

≡
−
,
)(mod1
2
na
r
≠
,
thì n là số nguyên tố.
Chứng minh. Giả sử n là hợp số,
pNn =
, với p là số nguyên tố,
1
>
N
. Bởi vì n không
là ước của
1
2
−
r
a
, nên tồn tại số nguyên tố p sao cho
)1()(
2
−>
r
pp
an

. Số d được xác định và d|n-1=2rq, bởi vì
)(mod1
1
na
n
≡
−
. Ngoài ra ta có
)1()(|
1
−=
−
pppd
ss
φ
. Nhưng từ biểu thức
)(mod1
2 sr
pa ≠
dẫn đến d không là ước của 2r. Nghĩa là q|d. Bởi vì
)1(|
1
−
−
ppq
s
. Số q và p khác nhau,
bởi vì p|n, q|n-1. Dẫn đến q|p-1. Từ đây
)(mod1 qp ≡
, và do tính lẻ của p và q nên

1
na
n
≡
−
,
)(mod1
2
na
r
≠
.
Thế thì n hoặc là số nguyên tố, hoặc
2
pn =
, với
12 += qp
- là số nguyên tố và
)(mod1
21
pa
p
≡
−
.
Chứng minh. Giả sử n là hợp số,
pNn =
, với p là số nguyên tố,
1
>

nên chúng ta có
)(mod1
21
2
pa
p
≡
−
, theo
định lý Euler thì
)(mod1
2
2
pa
pp
≡
−
, từ đây dẫn đến điều phải chứng minh.
Chú ý: Nếu biết được q thì kiểm tra đẳng thức
2
)12( += qn
rất dễ dàng. Có nghĩa là khi
biết được a, chúng ta sẽ biết được n là nguyên tố hay hợp số. Từ định lý kiểm tra tính
nguyên tố này chúng có thể xây dựng số nguyên tố lớn rất hiệu quả, bởi vì càng lớn giới
hạn trên của số ngẫu nhiên r thì càng đạt được việc xây dựng số nguyên tố như ý.
Định lý: Giả sử n là số lẻ,
11
1,1 RFnn
=−>
, ở đây

=−
−
naUCLN
qn
q
.
Giả sử
Nm
∈
đối với từng
1, ,2,1 −= ml
, thì
1
1
+lF
không là ước của n nếu
)1)(2)(1(
1
2
11
+−++< FmLFmFn
,
ở đây
LLFR
+=
111
2
,
1
21 FL

1
1
. Lúc này việc kiểm tra tính
nguyên tố của n có thể có chi phí là
( )








n
n
O
loglog
log
7/17
.
Định lý: Giả sử
1, >∈ nNn
, n là số lẻ,
11
.1 RFn
=−
, ở đây
1),(
11
=

).
Bổ đề: Giả sử
)(mod1,, naNma
m
≡∈
, và giả sử đối với từng ước nguyên tố q của m
thỏa mãn
1),1(
/
=− naUCLN
qm
. Khi đó nếu p là số nguyên tố và
np |
, thì
)(mod1 mp ≡
.
Chứng minh. Rõ ràng rằng m là bậc của
)(mod na
trong
n
Z
. Giả sử p là số nguyên tố, và
ước của n, và giả sử k là bậc của a (mod p). Như thế k=m. Rõ ràng, k|m bởi vì từ
)(mod1 na
m
≡
, dẫn đến
)(mod1 pa
m
≡

.
Đặt F(1):=1. Sau đó đối với từng số a=2,3,…,
[ ]
1log
2
+n
chúng ta thực hiện tầng 2
cho đến khi chúng ta không chứng minh được n là hợp số hay nguyên tố.
II. Tầng 2.
1. Bước 1. Nếu a là hợp số, thì
)1(:)( −= aFaF
và nhảy lên bước 6. Nếu a là số
nguyên tố, và
)(mod1
)1(
na
aF
≡
−
, thì
)1(:)( −= aFaF
và nhảy đến bước 6. Ngược lại
chúng ta kiểm tra điều kiện sau, xem có thỏa mãn không:
)(mod1
1
na
n
≡
−
.

, thì quay về tầng 2 với a là giá trị tiếp theo. Nếu như
[ ]
1log
2
+= na
, thì n là hợp số.
Chúng ta chứng minh tính đúng đắn của thuật toán và nhận đánh giá về độ phức
tạp của thuật toán.
Bảng liệt kê số nguyên tố thực hiện trên tầng 1 nhờ sự giúp đỡ của sàng Eratosfen
với độ phức tạp
)(log
4
nO
.
Giá trị hiện tại của F(a) là ước số của n-1, cho nên bước 1 của tầng mất
)(lognO
lệnh.
Bước 2 của tầng tốn
)(log
3
nO
lệnh nhờ sự giúp đở của thuật toán hổ trợ sau
Thuật toán tìm bậc của phần tử
Cho đầu vào thuật toán
Nna ∈,
,
∏
=
=−
N

)(mod1 nA ≡
.
Nếu như đúng thì nhảy sang bước 4. Ngược lại
j
MpM =:
,
j
p
AA
=
:
;
Và chuyển đến giá trị tiếp theo của l trong chu trình.
Bước 4. Nếu như j<N, thì quay về bước 2, ngược lại thì đưa ra M.
Tính đúng đắn của thuật toán tìm bậc của phần tử thì quá rõ ràng. Để nhận được đánh
giá về độ phức tạp của thuật toán này ta chú y rằng
∏
=
≥≥−
N
j
N
j
pn
1
21
,
từ đây
)(log),(log),(log nOnOpnON
jj

2
nO
lệnh.
Sau khi trải qua bước 4, hòan thành điều kiện sau: Đối với tất cả các số b,
ab
≤≤
2
,
)(mod1
)(
nb
aF
≡
.
Chúng ta chứng minh tính đúng đắn của bước 5. Chúng ta có
)(mod1),(mod
)(1)(
nana
aEaF
≡≠
−
, và đối với bất kỳ số nguyên tố q, a|E(a),
1),1(
/)(
=− naUCLN
qaE
.
Cũng như
)(mod1
)(

)(mod1|1, ,1
)(
nbnbH
aF
≡−∈=
.
=
1
H
{
nbb
≤≤
1|
, tất cả các ước nguyên tố b không lớn hơn a
}
.
Dễ dàng thấy
HH
⊆
1
, dẫn đến
||||
1
HH
<
.
Từ n là số nguyên tố, dẫn đến
FH =||
Theo định lý phân bố số nguyên tố, nếu
5

log
loglog
1
),(
ϕ
,
bởi vì
na
2
log>
, dẫn đến
na loglog2log >
. Vậy chúng ta đã dẫn đến mâu thuẫn.
3.3/ Kiểm tra tính nguyên tố bằng thuật toán Millier
Cho
*
: RNf →
- hàm số trên tập số tự nhiên, với f(n)<n.
Đầu vào là số tự nhiên lẻ n, n>1.
Bước 1. Kiểm tra điều kiện sau có thỏa mãn hay không
s
mn =
, với
2,, ≥∈ sNms
. Nếu
như thỏa mãn, thì n là hợp số, và thuật toán dừng.
Bước 2. Thuật hiên các bước nhỏ (i)-(iii) đối với tất cả
)(nfa ≤
(i) Kiểm tra điều kiện a|n
(ii) Kiểm tra điều kiện

.
3.4/ Kiểm tra tính nguyên tố bằng phép kiểm tra xác suất
Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên. Giả sử
có một mệnh đề Q(p,a) nào đó đúng với mọi số nguyên tố p và một số tự nhiên a <= p.
Nếu n là một số tự nhiên lẻ và mệnh đề Q(n,a) đúng với một a<= n được lấy ngẫu nhiên,
khi đó a có khả năng là một số nguyên tố. Ta đưa ra một thuật toán, kết luận rằng n là số
nguyên tố. Nó là một thuật toán ngẫu nhiên hay thuật toán xác suất. Trong các thuật toán
loại này, dùng một kiểm tra ngẫu nhiên không bao giờ kết luận một số nguyên tố là hợp
số nhưng có thể kết luận một hợp số là số nguyên tố. Xác suất sai của phép kiểm tra có
thể giảm xuống nhờ việc chọn một dãy độc lập các số a; nếu với mỗi số a xác suất để
thuật toán kết luận một hợp số là số nguyên tố là nhỏ hơn một nửa thì sau k lần thử độc
lập, xác suất sai là nhỏ hơn 2
−k
, độ tin cậy của thuật toán sẽ tăng lên theo k.
Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là:
(i) Chọn một số ngẫu nhiên a.
(ii) Kiểm tra một hệ thức nào đó giữa số a và số n đã cho. Nếu hệ thức sai thì chắc
chắn n là một hợp số (số a là "bằng chứng" chứng tỏ n là hợp số) và dừng thuật toán.
(iii) Lặp lại bước 1 cho đến khi đạt được số lần đã định hoặc gặp bước 2.
Sau một loạt lần kiểm tra, nếu không tìm được bằng chứng chứng tỏ n là hợp số thì ta
kết luận n là số nguyên tố.
Các phép kiểm tra tính nguyên tố ngẫu nhiên là: Phép kiểm tra tính nguyên tố của
Fermat (kiểm tra Fermat. Đây là phép thử heuristic; tuy nhiên ít người sử dung phép thử
này. Được sử dụng nhiều hơn là Kiểm tra Miller-Rabin và Kiểm tra Solovay-Strassen.
Với mọi hợp số n, ít nhất 3/4 (với kiểm tra Miller-Rabin) hoặc 1/2 (Với kiểm tra Solovay-
Strassen) các số a là bằng chứng chứng tỏ n là hợp số).
3.4.1/ Kiểm tra trên cơ sở định luật nhỏ của Fermat
3.4.1.1/ Cơ sở thuật toán
Phương pháp này dựa trên định luật nhỏ của Fermat: Nếu như n là số nguyên tố thì bất
kỳ số

n
≡
, số này còn được gọi là số Carmichael.
Ví dụ, chúng ta xem số 561=3.11.17. Chúng ta chứng số này là số Carmichael. Đồng
dư thức
)561(mod
561
aa ≡
sẽ tương đương với hệ
)3(mod
561
aa ≡
,
)11(mod
561
aa ≡
,
)17(mod
561
aa ≡
. Nếu 3|a, thì
)3(mod0
561
≡≡ aa
. Nếu như 3 không là ước của a, thì
)3(mod1
2
≡a
, từ đây ta có
)3(mod1

return hợp số
return nguyên tố xác suất
3.4.1.2/ Ví dụ minh họa
Ví dụ 1:
Kiểm tra n = 221 là số nguyên tố. Kiểm tra tới khi nào không còn lấy được số a nào
sao cho
2201
≤≤
a
và UCLN(a,n)=1.
- Chọn a = 38:
- Chọn a= 26:
Vậy 221 là hợp số, không phải là số nguyên tố
Ví dụ 2:
Kiểm tra n = 5 là số nguyên tố. Kiểm tra tới khi nào không còn lấy được số a nào
sao cho
41
≤≤
a
và UCLN(a,n)=1.
- Chọn a = 4:
a
n-1
= 4
4
= 256)5(mod1≡
- Chọn a = 3:

∈
được chọn ngẫu nhiên hay không? Nếu mệnh đề
Q(n,a) không đúng, tất yếu n không phải là số nguyên tố, còn nếu Q(n,a) đúng, số n có thể
là số nguyên tố với một xác suất nào đó. Khi tăng số lần thử, xác suất để n là số nguyên tố
tăng lên.
Bổ đề: Cho trường hữu hạn
p
Z
, trong đó p là số nguyên tố. Chắc chắn rằng 1 và -1
luôn là các căn bậc hai của 1 theo mođun p. Chúng là hai căn bậc hai duy nhất của 1. Thật
vậy, giả sử rằng x là một căn bậc hai của 1 theo mođun p. Khi đó:
)(mod1
2
px ≡
)(mod01
2
px ≡−
)(mod0)1)(1( pxx ≡+−
Từ đó, x − 1 hoặc x + 1 là chia hết cho p.
Bây giờ giả sử p là một số nguyên tố lẻ, khi đó p - 1 là số chẵn và ta có thể viết p − 1
dưới dạng
m
s
⋅2
, trong đó s là một số tự nhiên lớn hơn hay bằng 1 và m là số lẻ - Điều
này nghĩa là ta rút hết các thừa số 2 khỏi p − 1. Lấy số a bất kỳ trong tập {1,2, ,p-1}. Xét
dãy số
m
k
k

2
1
px
s
≡
−
Do đó hoặc
)(mod1
1
px
s
≡
−
hoặc
)(mod1
1
px
s
−≡
−
. Nếu
)(mod1
1
px
s
−≡
−
ta dừng lại, còn
nếu ngược lại ta tiếp tục với x
s − 2

≤≤
0
sao cho
)(mod1
2
pax
m
k
k
−≡=
⋅
.
Xác suất trả lời sai:
Định lý: nếu n là hợp số dương lẻ thì trong các số a
∈
{2, ,n-1} tồn tại không quá
4
1
−
n
cơ sở a để n là số giả nguyên tố mạnh Fermat.
Gọi A là biến cố "Số n là hợp số". B là biến cố "Kiểm tra Miller-Rabin trả lời n là số
nguyên tố". Khi đó xác suất sai của kiểm tra này là xác suất để số n là hợp số trong khi
thuật toán cho câu trả lời TRUE, nghĩa là xác suất điều kiện P(A|B).
Theo định lý trên nếu n là hợp số thì khả năng kiểm tra này trả lời TRUE xảy ra với
xác suất không vượt quá
4
1
, nghĩa là P(B|A)
4

=
⋅
=
Trong công thức này P(A) đã biết ở trên, P(B|A)
4
1
≤
, còn
1)|( =ABP
vì khi n là số
nguyên tố thì chắc chắn mệnh đề Q(n,a) là đúng và
n
APAP
ln
2
)(1)( =−=
. Từ đây ta có
2)2(ln)|(
)2(ln)|(
)|(
+−⋅
−⋅
=
nABP
nABP
BAP
Kiểm tra Miller-Rabin lặp:
Theo công thức tính xác suất sai trên đây, với n lớn (cỡ 130 chữ số thập phân), nếu
thực hiện phép thử Miller-Rabin chỉ một lần, xác suất sai là khá lớn, tới trên 90%. Để
giảm xác suất sai, ta lặp lại phép thử k lần với k số ngẫu nhiên a khác nhau, nếu n vượt