Chương 3
KIỂM TRA VÀ XÂY DỰNG SỐ NGUYÊN TỐ
Dựa vào tính chất đặc biệt của số nguyên tố, mà khi xây dựng một số bài toán với
việc áp dụng số nguyên tố, đặc biệt là ứng dụng số nguyên tố lớn, nó trở nên hữu ích cho
mục đích bài toán. Trong chương này chúng ta đi tìm hiểu cách kiểm tra một số nguyên
tố cho trước và làm thế nào để xây dựng được số nguyên tố lớn.
3.1 Khái niệm về 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ó 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
α
α

1
1
=
,
ở đây
k
ppp <<<
21
- là các số nguyên tố khác nhau,
N
k
∈
αα
, ,
1

3.3 Kiểm tra tính nguyên tố của số có dạng đặc biệt
Chúng ta xem số n dạng
12 +=
m
n
, ở đây
Nm
∈
. Nếu m chia hết cho số nguyên tố
2>p
, tức là
1,
11
≥= mpmm
, thì
1)2(
1
+=
p
m
n
chia hết cho
12
1
+
m
, có nghĩa là n là hợp số.
Cho nên số nguyên tố có thể chỉ khi
k
m 2=

Chứng minh: Chúng ta chứng minh điều kiện đủ. Chúng ta có:
k
n
2
21 =−
. Từ
)(mod13
2
1
n
n
−≡
−
, nên
)(mod13
1
n
n
≡
−
, điều này có nghĩa là bậc của 3 (mod n) bằng
k
n
2
21 =−
. Nên nhóm nhân
*
n
Z
có ít nhất là n-1 phần tử, và các phần tử khác không của






=−






=






−−
nn
n
n
. Theo tiêu chuẩn Euler thì
)(mod3
3
2
1
n
n

Định nghĩa 3.2. 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 là số nguyên tố Mersenn.
Để kiểm tra tính nguyên tố của số Mersenn ta dùng định lý sau
Định lý 3.2. Cho q là số nguyên tố, q>2,
12 −=
q
n
. Chúng ta xem dãy
, ,,,
210
LLL
xác
định dãy này như sau
4
0
=L
;
)(mod2
2
1
nLL
jj
−≡

.
Chứng minh: Theo định lý nhỏ Fermat ta có
)(mod22
12
p
M
p
≡
−
, từ đây
)(mod512.2
12
pp
MF
p
≡+=
−
. Dẫn đến
1),( =
pp
MFUCLN
, và dẫn đến
)(mod
5
5
2
1
p
p
pp









≡








≡
−
Cho nên
1
5
2
5
),5(mod2)5(mod1212
334
−=




==== 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
−+
−=
jjj
xxx
, được gọi là dãy số Liuka.
3.4 Phương pháp N
±
1 kiểm tra tính nguyên tố và xây dựng số nguyên tố lớn
Trong mục này chúng ta sẽ tìm hiểu một số phương pháp, mà với sự giúp đỡ của nó
chúng ta có thể kiểm tra tính nguyên tố của số tự nhiên N, khi biết được hoàn toàn hoặc
một phần của sự phân tích N ra thừa số. Và chúng ta cũng tìm hiểu một số phương pháp
tạo ra số nguyên tố lớn được áp dụng trong mật mã.
Đầu tiên chúng ta xem phương pháp N-1 kiểm tra số nguyên tố.
Định lý 3.4 Cho
1, >∈ nNn
, n là số lẻ,
∏
=
=−
k
i
i
i
pn
1

Cho
i
m
là bậc của
)(modna
i
trong
n
Z
. Từ điều kiện chúng ta có
1| −nm
i
, và
i
m
không
là ước của
i
p
n 1−
, cho nên
ii
mp
i
|
α
với i=1,…,k. Dẫn đến
)(modnab
i
i

α
trong
*
n
Z
. Điều
này có nghĩa là
n
Z
là một trường, và n là số nguyên tố.
Từ định lý này chúng ta có thể kiểm tra được tính nguyên tố như sau. Phân tích n-1 ra
thừa số, chọn a=2,3,…, kiểm tra điều kiện định lý. Nếu như tìm thấy a nào đó, với
na
<<
1
, mà
)(mod1
1
na
n
≠
−
, thì n là hợp số. Nếu như tìm được
k
aa , ,
1
, mà thỏa mã điều
kiện định lý thì n là số nguyên tố.
Tương tự với việc kiểm tra số nguyên tố bằng phương pháp n-1, ta tìm hiểu phương
pháp n+1 khi biết hoàn toàn các nhân tử nguyên tố của n+1

β
- tức là phân tích n+1 ra thừa số nguyên tố, và
1−=






n
D
. Nếu như đối với từng
ki , ,1=
, tìm được
iiii
QPDZQP 4,,
2
−=∈
, sao cho có
quan hệ với dãy số Liuka
, ,
)(
1
)(
0
ii
uu
thỏa mãn điều kiện:
)(
1

11
=RFUCLN
. Giả sử
chúng ta biết được hoan toàn sự phân tích ra thừa số nguyên tố
∏
=
=
k
j
j
j
qF
1
1
α
. Nếu như đối
với mỗi j=1,…,k tìm được
Na
j
∈
, sao cho
)(mod1
1
na
n
j
≡
−
,
1),1(

−
, từ đây
1),( =paUCLN
j
và bậc
j
e
của phần tử
)(mod pa
j
trong
p
Z
không là ước của n-1. Ngoài ra
theo định lý nhỏ Fermat thì
)1(| −pe
j
. Từ điều kiện của định lý ta có
)(mod1
/)1(
pa
j
qn
j
≠
−
,
từ đây
jj
eq

<<< 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ụ
3
1
=p
.
Giả sử chúng ta đã xây dựng được số nguyên tố
1−i
p
. Chọn số ngẫu nhiên r,
11
1
−≤≤
−i
pr
.
Giả sử:
tr
s
2=
, t là số lẻ. Như thế số nguyên tố
i
p
chúng ta chọn
1212
1

nF >
1
, bởi vì
2
1
2
1
2
1
2
1
1
2212 Fptptpn
i
s
i
s
i
s
≤<<+=
−
+
−
+
−
+
. Dẫn đến để
chứng tỏ n là số nguyên tố, chúng ta cần tìm các số
1
a

.
Nếu như ta tìm được số a, sao cho
)(mod1
1
na
n
≠
−
, thì n là hợp số và chúng ta cần chọn
số ngẫu nhiên r khác. Nếu như chúng ta chứng minh được n là nguyên tố thì đặt
np
i
=
.
Một phương pháp khác xây dựng số nguyên tố ứng dụng định lý trên có thể nêu ra
dưới đây. Chúng ta lại xây dựng dãy số nguyên tố, và giả sử xây dựng
3
1
>
−i
p
. Chúng ta
chọn số chẵn ngẫu nhiên r, thỏa mãn
31
1
−≤≤
−i
pr
, và đặt
1

−
−1
1
). Rõ ràng ta có bất đẳng thức
npF
i
>=
−11
, bởi vì
2
11
2
1111
131)3(1
−−−−−−
≤+−=+−≤+=
iiiiii
ppppprpn
Chọn a và thực hiện tương tự như phương pháp xây dựng trên.
Định lý tiếp theo sẽ cho chúng ta cách xây dựng số nguyên tố hiệu quả hơn, bởi vì
không cần tính toán ước nguyên tố lớn.
Định lý 3.7 Cho
12 += rqn
, ở đây q là số nguyên tố lẻ, và r với
12 +≤ qr
. Nếu tồn tại
số
Na
∈
, sao cho

pp
an
νν
và khi
11)1(
2
≥+−=
r
p
as
ν
chúng ta có
np
s
|
và
s
p
không là ước của
1
2
−
r
a
.
Giả sử d là bậc của a (mod
s
p
) trong
S

)(mod1 qp ≡
, và do tính lẻ của p và q nên
)2(mod1 qp ≡
. Ngoài ra
)2(mod1 qn ≡
. Bởi vì n=pN, nên
)2(mod1 qN ≡
. Bởi vì
1>p
và
1
>
N
, nên
qNqp 21,21 +≥+≥
. Nghĩa là
2
)21( qpNn +≥=
. Thế nhưng
2
)21(1)12(212 qqqrqn +<++≤+=
. Nhận được mâu thuẩn. Nên định lý được chứng minh.
Định lý 3.8 Cho
12 += qrn
, ở đây q là số nguyên tố,
24 +≤ qr
. Giả sử tồn tại
Na∈
,
sao cho

>
N
. Chúng ta
chứng minh được rằng
)2(mod1 qNpn ≡≡≡
.
Nếu như một trong hai số p và N lớn hơn nhiều so với
q21+
, thì nó sẽ lớn hơn hoặc
bằng
q41+
, và
168)41)(21(
2
++=++≥= qqqqpNn
. Nhưng điều kiện
1481)24(2
2
++=++≤ qqqqn
. Dẫn đến
2
,21 pnqNp =+==
. Chứng minh phần còn lại
)(mod1
21
pa
p
≡
−
. Rõ ràng theo điều kiện và n=p

chia số n-1 sẽ có bậc nhỏ hơn
3/1
n
.
Định lý 3.9 Giả sử n là số lẻ,
11
1,1 RFnn =−>
, ở đây
1),(
11
=RFUCLN
,
1
F
là số chẳn,
và ta biết được hoàn toàn sự phân chia
1
F
ra thừa số nguyên tố. Giả sử đối với bất kỳ ước
nguyên tố q của
1
F
tìm thấy được
Na
q
∈
, sao cho
)(mod1
1
na

111
2
,
1
21 FL <≤
, thì n là số nguyên tố khi và chỉ khi hoặc
LR =
1
, hoặc
1
2
8LL −
không là số chính phương.
3.5 Kiểm tra số nguyên tố bằng thuật toán Konigin-Pomerans
Nếu
Nn∈
và biết được sự phân tích hoàn toàn hoặc một phần lớn ra thừa số nguyên
tố của số n-1, thì có thể để kiểm tra xem n là hợp số hay là số nguyên tố với độ phức tạp
theo đa thức. Đánh giá tốt nhất độ phức tạp nhận được từ thuật toán Konigin- Pomerans:
Định lý 3.10 Giả sử
1, >∈ nNn
, n là số lẻ,
∏
=
=−
k
j
a
j
j

, và biết
được sự phân chia
1
F
ra thừa số nguyên tố. Nếu
ε
+
≥
n
nF
4
1
1
, với
ε
là số dương không đổi,
thì việc kiểm tra tính nguyên tố của n có thể chi phí là
))((log
)(
ε
c
nO
(
)(
ε
c
là số nguyên
dương không đổi, phụ thuộc vào
ε
).

sao cho k|(m/q). Từ đây ta có
)(mod1
/
pa
qm
≡
, có nghĩa là
),1(|
/
naUCLNp
qm
−
. Điều này
trái với giả thuyết của bổ đề.
Ngoài ra chúng ta còn có, theo định lý Fermat
)(mod1
1
pa
p
≡
−
, dẫn đến m|p-1. Đây là
điều ta cần chứng minh.
Thuật toán kiểm tra tính nguyên tố của số.
I. Tầng 1. Chuẩn bị sẳn một bảng tất cả các số nguyên tố, không lớn hơn
[ ]
1log
2
+n
.

2. Bước 2. Khi phân tích n-1 ra thừa số nguyên tố, ta tìm bậc của a (mod n),
nghĩa là số tự nhiên nhỏ nhất E(a), thỏa mãn
)(mod1
)(
na
aE
≡
.
3. Bước 3. Kiểm tra điều kiện sau có thỏa mãn hay không:

)(|
/)(
)1((
aEq
qaE
aUCLN −
, q là số nguyên tố.
Nếu như điều kiện trên không hòan thành thì n là hợp số.
4. Bước 4.
))(),1((:)( aEaFBCNNaF −=
, BCNN-bội số chung nhỏ nhất.
5. Bước 5. Nếu như
naF ≥)(
, thì n là số nguyên tố.
6. Bước 6. Nếu như
[ ]
na
2
log≤
, thì quay về tầng 2 với a là giá trị tiếp theo. Nếu

j
j
j
pn
1
1
α
- tức là biết được sự phân tích ra
thừa số nguyên tố của số n-1. Đầu ra là bậc của a (mod n) trong
n
Z
.
Bước 1.
0:,1 =−= jnM
.
Bước 2.
M
j
aApMMjj
j
==+= :,/:,1:
α
.
Bước 3 (Chu trình). Đối với
j
l
α
, ,1,0=
, kiểm tra xem điều kiên sau có thỏa mãn
không

. Cho nên bên trong và bên ngoài chu trình
thực hiện
)(lognO
bước, và trong từng bước thực hiện
)(lognO
lệnh. Tổng độ phức tạp là
)(log
3
nO
lệnh.
Trở lại thuật toán kiểm tra tính nguyên tố. Nếu như UCLN trong bước 3 của tầng 2
không bằng 1, thì n là hợp số. Rõ ràng rằng, theo định nghĩa E(a) không có một số nào từ
số
1
/)(
−
qaE
a
chia hết cho n. Có nghĩa là gcd lớn hơn 1, một trong các số
1
/)(
−
qaE
a
có với
n ước chung là d, 1<d<n. Độ phức tạp của bước 3 tầng 2 là
)(log
2
nO
lệnh.

))((mod1 aFp ≡
, thì
naFp +≥+≥ 1)(1
, từ đây dẫn đến n
là số nguyên tố. Chúng ta chứng minh đồng dư thức
))((mod1 aFp ≡
. Giả sử rằng
))1((mod1 −≡ aFp
. Theo bổ đề thì chúng ta có
))((mod1 aEp ≡
, từ đây
(mod1≡p
BSCNN (F(a-1), (E(a)))
))((mod1 aF≡
Bây giờ chúng ta chứng minh bước 6 của tầng 2. Giả sử rằng n là số nguyên tố,
[ ]
naFFna <=> )(,log
2
, chúng ta dẫn đến điều mâu thuẫn. Theo cách xây dựng
1|)( −naF
, bởi vì
1|)( −naE
. Đặt
{ }
{ }
)(mod1|1, ,1
)(
nbnbH
aF
≡−∈=

nanH
log
loglog
1
1
),(||
−
>=
ϕ
.
Từ đây
nnnanF
n
n
a
n
=>>≥
−−
loglog2
loglog
1
log
loglog
1
),(
ϕ
,
bởi vì
na
2

)1(1
2
−≤≤ nvk
,
nnnaUCLN
k
n
<−<
−
)),(mod1(1
2
1
Nếu như một trong ba điều kiện (i)-(iii) thỏa mãn thì n là hợp số, và thuật toán dừng.
Bước 3. Nếu như chúng ta đi đến được bước này thì n là số nguyên tố.
Chú ý. Hàm
)(bv
a
là số k lớn nhất thỏa mãn
ba
k
|
.
3.7 Kiểm tra tính nguyên tố của số 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ó

(2)
)(mod1
1
na
n
≡
−
.
Cho nên để kiểm tra tính nguyên tố của n, chúng ta chọn một số bất kỳ
Za∈
và kiểm
tra xem có thỏa mãn định lý của Fermat hay không? Nếu như định lý Fermat không thỏa
với một giá trị a nào đó thì n là hợp số. Nếu như định lý thỏa mãn, thì chúng ta cũng
không thể kết luận rằng n là số nguyên tố, bởi vì định lý chỉ đúng trong điều kiện cần. Vì
vẫn tồn tại n là hợp số, thì đối với bất kỳ số
Za∈
, thì ta vẫn có được đằng thức
)(modnaa
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 ≡

1, ,2,1 −n
và kiểm tra điều kiện UCLN(a,n)=1
2. Nếu như điều kiện trên không thỏa mãn thì n là hợp số
3. Kiểm tra đẳng thức (2)
4. Nếu như đẳng thức (2) không thỏa mãn thì trả lời n là hợp số
5. Nếu như đẳng thức đúng thì trả lời là chưa biết, nhưng có thể kiểm tra lại một số
lần với các a khac nhau.
Giải thuật Fermat kiểm tra tính nguyên tố của số
Đầu vào: n: giá trị để kiểm tra tính nguyên tố; k: tham số tham gia vào quá trình kiểm
tra .
Đầu ra: hợp số nếu n là hợp số, nếu không nguyên tố xác suất
repeat k times:
lấy a ngẫu nhiên trong [1, n − 1]
if a
n − 1
mod n ≠ 1 then
return hợp số
return nguyên tố xác suất
Khi dùng thuật toán tính nhanh luỹ thừa theo mođun, thời gian thi hành của thuật toán
là O(k × log
3
n), ở đó k là số lần kiểm tra với mỗi số a ngãu nhiên, và n là giá trị ta muốn
kiểm tra. Và từ việc kiểm tra này dẫn ta đến phần sau.
Định nghĩa 3.4 Cho n>1 là số tự nhiên lẻ,
dn .21
2
=−
, ở đây d là số lẻ. Số n gọi là số
giả nguyên tố chặc chẽ trong cơ sỡ a,
Na

na
d
s
≡
. Từ đây ta có
)(mod1
1
2
na
d
s
±≡
−
. Nếu như
)(mod1
1
2
na
d
s
−≡
−
, thì chúng ta
dừng, nếu như
)(mod1
1
2
na
d
s

muốn kiểm tra và một số
Aa
∈
đượ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ổ đề 3.2 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

Hay
)(mod1
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

≤≤
0
sao
cho
)(mod1
2
pax
m
k
k
−≡=
⋅
.
Giải thuật kiểm tra Miller-Rabin
Đầu vào: Số tự nhiên lẻ n.
Đầu ra: FALSE nếu n là hợp số, nếu không TRUE
1. Phân tích n - 1 =
m
s
⋅2
trong đó
1≥s
và m là số tự nhiên lẻ
2. Chọn ngẫu nhiên số tự nhiên a
∈
{2, ,n-1}.
3. Đặt b = a
m
(mod n)
4. Nếu

i
−≠
Với
10
−≤≤
si
Theo định lý Fermat ta có
)(mod1
2
na
m
s
≡
Khi đó
m
s
a
1
2
−
là căn bậc 2 của 1 modulo n, theo bổ đề ta có hoặc
)(mod1
1
2
na
m
s
≡
−
hoặc

2
2
−
là căn bậc 2 của 1. Bằng cách tương tự:
)(mod1
1
2
na
m
s
≡
−
Và lặp lại lập luận trên, cuối cùng ta có
)(mod1 na
m
≡
Điều này là mâu thuẫn.
Xác suất trả lời sai:
Định lý 3.12: 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

BAP
⋅+⋅
⋅
=
⋅
=
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:

≡






.
Định lý 3.13 Nếu n là hợp số lẻ thì tồn tại không quá
2
n
số tự nhiên dương a nhỏ hơn
n, nguyên tố cùng nhau với n sao cho n là số giả nguyên tố Euler cơ sở a.
Chứng minh:
Chúng ta đi chứng minh tồn tại số
Nb∈
, mà
1),( =nbUCLN
và
)(mod
2
1
n
n
b
b
n




)(mod1
2
1
nb
n
±≠
−
. Rõ ràng rằng, tồn tại
2≥
i
α
. Theo định lý
về phần dư trung hoa, có thể tìm được
Nb
∈
,
)(mod
i
i
pb
α
- là căn nguyên thủy trong
i
i
p
Z
α
,
còn khi
)(mod1,

αα
φ

, điều này là không thể bởi vì n-1 không chia hết cho
i
p
.
Bây giờ giả sử rằng
k
ppn
1
=
. Chúng ta tìm số
Nb∈
, sao cho
)(mod
1
pb
-là căn
nguyên thủy trong
1
p
Z
, và
)(mod1
j
pb ≡
khi j>1. Khi đó
1),( =nbUCLN
và







p
b
p
b
p
b
n
b
k
Đồng dư thức
)(mod1
2
1
nb
n
−≡
−
tương đương với
)(mod1
2
1
j
n
pb −≡

2
1
1
n
n
a
anaUCLNnaaW
n
,












≠=−≤≤=
−
)(mod,1),(,11|
2
1
2
n
n
a

a
n
a
n
aa
2121
. Cho nên đối với số
1
Wa ∈
, thặng dư không âm nhỏ nhất của
)(modnba
thuộc
2
W
. Dẫn đến ,
||||
12
WW ≥
, từ đây
rút ra điều khẳng định của định lý.
Giải thuật kiểm tra Solovay-Strasen
Đầu vào: n: là số tự nhiên lẻ
Đầu ra: FALSE nếu n là hợp số, nếu không TRUE
1. Chọn a ngẫu nhiên trong khoảng[1,n-1]
2. Tính ký hiệu Jacobi J=






=
.
2)2(ln)|(
)2(ln)|(
)/(
+−⋅
−⋅
≈
nABP
nABP
BAP
.
3.8 Kiểm tra tính nguyên tố của số bằng thuật toán đa thức
Định lý 3.14 Cho p là số lẻ,
Za∈
,
1),( =paUCLN
. Số p là số nguyên tố khi và chỉ khi
)(mod)( paxax
pp
−≡−
(3.3)
(đồng dư thức 3.3 nghĩa là hệ số của đa thức so sánh với modulo p)
Chứng minh: Rõ ràng ta có
pipi
p
i
pp
aaax
i


i
p
chia hết cho p.
Giả sử biểu thức (3.3) thỏa mãn, và giả sử p là hợp số. Chúng ta sẽ tìm được số
nguyên tố q và số tự nhiên k sao cho
pq
k
||
, điều kiện
pq <
. Rõ ràng rằng
k
q
không chia
hết cho
!
)1) (1(
q
qppp
q
p
+−−
=







≥
, thì
))((mod xhxx
r
m
m
≡
.
4)Nếu như
)( pOrd
r
bậc của p (mod r), thì trong
[ ]
xZ
p
đa thức
1
1
−
−
x
x
r
được phân chia
ra các đa thức bất khả quy, mà mỗi trong chúng nó có mũ là
)( pOrd
r
.
Bổ đề 3.4 Tồn tại hằng số dương
0

log
8
)(
log6
≤≤
π
,
ở đây
)(m
π
là một số nguyên tố
mp ≤
, mà
3/2
)1( mpP >−
.
Thuật toán kiểm tra tính nguyên tố của số tự nhiên lẻ n>1
Bước 1. Nếu như n có dạng
b
a
, ở đây
2,, ≥∈ bNba
, thì thông báo, n là hợp số và
thuật toán kết thúc.
Bước 2. r:=2
Bước 3. Đối với giá trị hiện tại của r thực hiện bước 4-8
Bước 4. Nếu như r<n và UCLN(r,n)>1, thì n là hợp số, thuật toán kết thúc.
Bước 5. Nếu r là số nguyên tố, thì hoàn thành các bước 6-7, ngược lại thì chuyển
đến bước 8
Bước 6. Tìm số q – là ước số nguyên tố lớn nhất của r-1

2) Nếu như
[ ]
nrn
2
log21>−
, thì đối với tất cả a từ đoạn
[ ]
nra
2
log21 ≤≤
kiểm
tra biểu thức
)1(mod)( −−≡−
rnn
xaxax
trong
[ ]
xZ
n
. Nếu như đối với một số giá trị a trong trường hợp 1 hoàn thành bất
đẳng thức UCLN(a,n)>1, hoặc trong trường hợp 2 đẳng thức theo modulo
1−
r
x
không
đúng thì n là hợp số và thuật toán dừng.
Bước 10. Nếu như chúng ta đi đên bước này thì n là số nguyên tố.
Kết thúc thuật toán
.