Vietebooks Nguyn Hong Cng
Trang 1
Chơng 4
Kiểm tra tính nguyên tố xác suất

Để thiết lập hệ mật RSA, ta phải tạo ra các số nguyên tố ngẫu
nhiên lớn (chẳng hạn có 80 chữ số). Trong thực tế, phơng cách thực
hiện điều này là: trớc hết phải tạo ra các số ngẩu nhiên lớn, sau đó
kiểm tra tính nguyên thuỷ của chúng bằng cách dùng thuật toán xác
suất Monte- Carlo thời gian đa thức (chẳng hạn nh thuật toán
Miller- Rabin hoặc là thuật toán Solovay- Strasen). Cả hai thuật toán
trên đều đợc trình bày trong phần này. Chúng là các thuật toán
nhanh (tức là một số nguyên n đợc kiểm tra trong thời đa thức theo
log
2
n, là số các bít trong biểu diện nhị phân của n). Tuy nhiên, vẫn có
khả năng là thuận toán cho rằng n là số nguyên tố trong khi thực tế n
là hợp lệ số. Bởi vậy, bằng cách thay đổi thuật toán nhiều lần, có thể
giảm xác suất sai số dới một mức ngỡng cho phép (sau này sẽ thảo
luận kỹ hơn một chút về vấn đề này).
Một vấn đề quan trọng khác: là cần phải kiểm tra bao nhiêu số
nguyên ngẫu nhiên (với kích thơc xác định)cho tới khi tìm đợc một
số nguyên tố. Một kết quả nỗi tiếng trong lý thuyết số (đợc gọi là
định lý số nguyên tố) phát biểu rằng: số các số nguyên tố không lớn
hơn N xấp xỉ bằng N/ln N. Bởi vậy, nếu p đợc chọn ngẫu nhiên thì
xác suất p là một số nguyên tố sẽ vào khoảng 1/ln p. Với một mođun
512 bít, ta có 1/ln p 1/77. Điều này có nghĩa là tính trung bình, c
177 số nguyên ngẫu nhiên p với kích thớc tơng ứng sẽ có một số là
số nguyên tố. Dĩ nhiên, nếu chĩ hạn chế xét các số nguyên lẻ thì xác
suất sẽ tăng gấp đôi tới khoảng 2/177). Bỡi vậy trên thực tế, hoàn
toàn có khả năng tạo đợc các nguyên tố đủ lớn và do đó về mặt thực

Trớc tiên ta sẽ mô tả thuật toán Soloway- Strasson. Đây là một
thuật toán Monte-Carlo định hớng có cho bài toán hợp số và xác
xuất sai 1/2. Bởi vậy, nếu thuật toán trả lời có thì n là hợp số;
ngợc lại nếu n là hợp số thì thuật toán trả lời có với xác xuất tối
thiểu 1/2.

Hình 4.5. Bài toán hợp số.

Hình 4.6. Bài toán về các thặng d bậc hai. Mặc dù thuật toán Miller-Rabin (ta sẽ xét sau) nhanh hơn
thuật toán Soloway-Strasson (S-S) nhng ta sẽ xét thuật toán S-S
trớc vì nó dễ hiểu hơn về khái niệm, đồng thời lại liên quan tới một
số vấn đề của lý thuyết số (mà ta sẽ còn dùng trong các chơng trình
sau). Ta sẽ xây dựng một số nền tảng sâu sắc hơn trong lý thuyết số
trớc khi mô tả thuật toán. Đặc trng của bài toán: một số nguyên dơng n 2
Câu hỏi: n có phải là hợp số không ?

học đều thực hiện trong Z
11
).

Bài toán quyết định thặng d bậc hai đợc trình bày trên hình
4.6 sẽ đợc thấy một cách tơnngf minh nh sau:

Trớc hết, ta sẽ chứng minh một kết quả- tiêu chuẩn Euler
tạo nên thuật toán tất định theo thời gian đa thức cho bài toán về các
thặng d bậc hai. Định lý 4.8. (Tiêu chuẩn Euler)
Giả sử p là một số nguyên tố, khi đó x là một thặng d bậc hai
theo modulo p khi và chỉ khi:
x
(p-1)/2
1 (mod p)
Chứng minh:
Trớc hết giả sử rằng, xy
2
(mod p). Theo hệ quả 4.6, nếu p là
số nguyên tố thì x
p-1
1 (mod p) với mọi x 0 (mod p). Bởi vậy ta có :
x
(p-1)/2
(y
2
)

Trang 4
Định lý 4.8 sẽ dẫn tới một thuật toán thời gian đa thức cho các
thặng d bậc hai nhờ sử dụng kỹ thuật bình phơng và nhân cho
phép lấy luỹ thừa theo modulo p. Độ phức tạp của thuật toán khoảng
O((log p)
3
).

Sau đây tiếp tục đa ra một số định nghĩa từ lý thuyết số:

Định nghĩa 4.3.
Giả sử p là số nguyên tố lẻ. Với một số nguyên tố bất kỳ a 0,
ta

định nghĩa ký hiệu Legendre nh sau:

0 nếu a 0 (mod p)

= 1 nếu là thăng d bậc hai theo modulo p
-1 nếu là thăng d không bậc hai theo
modulo p Ta đã biết là a
(p-1)/2
1 (mod p) khi và chỉ khi a là một thặng d
bậc hai theo modulo p. Nếu a là bội của p thì rõ ràng a
(p-1)/2
0(mod
p). Cuối cùng, nếu a là một thặng d không bậc hai theo modulo p thì

Jacobi đợc định nghĩa nh sau:








p
a








p
a








p

=

=(-1)(-1)
2
(-1)(-1)

= -1.

Giả sử n > 1 là một số lẻ. Nếu n là một số nguyên tố thì a
(n-1)/2
(mod n) với a bất kỳ. Mặt khác nếu n là một hợp số thì đồng d
thức trên có thể đúng hoặc không. Nếu phơng trình đó vẫn đúng thì
a đợc gọi
là số giả nguyên tố Euler theo cơ số n. Ví dụ: 10 là số giả nguyên tố
Euler

theo cơ số 91 vì :
= -1 = 10
45
mod 91

Tuy nhiên có thể chứng tỏ rằng, với một hợp số lẻ n bất kỳ, sẽ
cóp nhiều nhất một nửa các số nguyên a (sao cho 1 a n-1) là các
số giả nguyên tố Euler cơ số n (xem các bài tập). Điều đó chứng tỏ




9975
6278
























=












19
8
7
6
5
3
3
2
2







91
10



1. Chọn một số nguyên ngẫu nhiên a, 1 a n-1

2. Nếu a
(n-1)/2
(mod n) thì
Trả lời n là số nguyên tố
Nếu không
Trả lời n là một hợp số
Rất may là có thể đánh giá ký hiệu Jacobi mà không cần phải
phân tích n nhờ sử dụng một số kết quả của lý thuyết số, trong đó kết
quả quan trọng nhất là tính chất 4 (tổng quát hoá luật tơng hỗ bậc
hai ).
Ta sẽ liệt kê mà không chứng minh các tính chất này.
1. Nếu n là một số nguyên tố lẻ và m
1
m
2
(mod n) thì: =

2. Nếu n là một số nguyên lẻ thì
1 nếu n 1 (mod 8)
= -1 nếu n 3 (mod 8)


m
Vietebooks Nguyn Hong Cng
Trang 7 Đặc biệt nếu m=2
k
t với t là một số lẻ thì:
4. Giả sử m và n là các số nguyên lẻ, khi đó:
=

ví dụ
Để minh hoạ cho việc áp dụng các tính chất trên , ta sẽ đánh
giá kí








=






n
m
n
m
n
mm
2121



























lại còn hợp trờng các trong
m
n

4) (mod 3nm nếu
m
n








O(log n) phép rút gọn theo modulo. Mỗi phép có thể thực hiện trong
thời gian O((log n)
2
). Điều đó chứng tỏ rằng, độ phức tạp là O((log
n)
3
) là đa thức theo log n. Thực ra bằng các phân tích chính xác hơn,
có thể chứng tỏ răng, độ phức tạp chỉ cỡ O((log n)
2
).

Giả sử ta đã tạo đợc một số ngẫu nhiên n và đã kiểm tra tính
nguyên tố của nó theo thuật toán Soloway- Strasen. Nếu chạy thuật
toán m lần thì câu trả lời n là một số nguyên tố sẽ có mức độ tin
cậy nh thế nào? Quả là liều lĩnh nếu coi răng, xác suất này là 1-2
-m
.
Kết luận này thờng đợc nêu trong các giáo trình và bài báo kĩ
thuật, tuy nhiên ta không thể dẫn ra theo các số liệu cho trớc.

Cần phải thận trọng hơn khi sự dụng các tính toán xác suất. Ta sẽ
định nghĩa các biến ngẫu nhiên sau:

a- Chỉ sự kiện số nguyên lẻ n có kích thớc đã định là một hợp
số.
b- Chỉ sự kiện thuật toán trả lời n là số nguyên tố m lần liên tiếp
.

Điều chắc chắn là prob(b| a)2
-m


7411
1872
theo tính chất 1
. =













7411
117
4
7411
2
theo tính chất 3
=

















117
5
3
117
2
theo tính chất 3
=






117
5
theo tính chất 2
=