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 thể ta có thể thiết lập đ-
ợc một hệ mật RSA. Sau đây sẽ tiếp tục xem xét điều này đợc thực
hiên nh thế nào.
Một bài toán quyết định là một bài toán toán trong đó một câu hỏi cần
đợc trả lời có hoặc không. Một thuật toán xác suất là một thuật

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.
Định nghĩa 4.2.
Giả sử p là một số nguyên tố lẻ và x là một số nguyên, 1 x
p-1. x đợc gọi là thặng d bậc hai theo modulo p nếu phơng trình đồng
Đặ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 ?
Đặc trng của bài toán: cho p là một số nguyên tố lẻ và một
số nguyên x sao cho 0 x p-1
Câu hỏi: x có phải là thặng d bậc hai phép modulo p ?
d y
2
x (modulo p) có một nghiệm yZ
p
x đợc gọi là thặng d không
bậc hai theo modulo p nếu x ??? 0 (mod p) và x không phải là thặng d
bậc hai theo modulo p.
Ví dụ 4.6.
Các thặng d bậc hai theo modulo 11 là 1,3,4,5 và 9. Cần để ý rằng,
(1)
2
=1, (5)
2
=3, (2)
2
=4, (4)
2
=5, (3)
2
=9 (ở đây tất cả các phép số

(mod p)
1 (mod p)
Ngợc lại, giả sử rằng x
(p-1)/2
1 (mod p). Cho p là một phần tử
nguyên thuỷ theo modulo p. Khi đó xb
i
(mod p) với giá trị i nào đó.
Ta có
x
(p-1)/2
(b
i
)
(p-1)/2
(mod p)
b
i(p-1)/2
(mod p)
Vì p có bậc bằng p-1 nên p-1 phải là ớc của i(p-1)/2. Bởi vậy i là số
chẵn và nh vậy căn bậc hai của x là b
i/2
.
Đị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ố:

....... p
K
ek
. Giả sử a 0 là một số nguyên.
Ký hiệu
Jacobi đợc định nghĩa nh sau:

Ví dụ 4.7.








p
a








p
a



p
a
n
a

=








=












9975
6278
Xét ký hiệu Jacobi . Phân tích luỹ thừa nguyên tố của

Ta đã biết cách đánh giá a
(n-1)/2
(mod n) trong thời gian đa thức
O((log n)
3
), tuy nhiên cần phải làm thế nào để tính các ký hiệu Jacobi
một cách có hiệu quả. Vì ký hiệu Jacobi đợc xác định theo các thừa số
trong phân tích của n. Tuy nhiên nếu có thể phân tích đợc n thì ta đã





































19
8
7
6
5
3
3
2
2






91


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)
3. Nếu n là một số nguyên lẻ thì
Đặc biệt nếu m=2
k
t với t là một số lẻ thì:







n
a













=






n
m
n
m
n
mm
2121







hiệu Jacobi trong thời gian đa thức. Các phép tính số học dùng ở đây
chỉ là rút gọn theo modulo và phân tích ra các luỹ thừa của thuật toán
đợc biểu diễn dới dạng nhị phân thì việc phân tích ra các luỹ thừa của
hai số chính là việc xác định số các số 0 tiếp sau. Bởi vậy, độ phức tạp
của thuật toán đợc xác định bởi số các phép rút gọn theo modulo cần
tiến hành. Không khó khăn lắm có thể chứng tỏ rằng, cần thực hiện
nhiều nhất là.






n
2





















=






7411
9283
9283
7411
theo tính chất 4
=







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









117
7411
theo tính chất 4
=







177
40
theo tính chất 1
=









theo tính chất 4
=






5
2
theo tính chất 1
= -1 theo tính chất 2
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.

Giả sự n 2
256
e
177
(đây là kích thớc của các số nguyên tố sự dụng
trong hệ mặt RSA). Khi đó hàm đầu tiên xấp xỉ bằng????. Ta sẽ lập
bảng cho hai hàm ứng với một số giá trị của m (xem hình4.8).
Hình 4.8. Các xác suất sai đối với phép kiểm tra Solovay- Strasen
M 2
-m
1 0,500 0,978
2 0250, 0,956
5 0,312.10
-1
0,732
10 0,977.10
-3
0,787.10
-
20 0,954.10
-6
0,834.10
-4
30 0,930.10
-9
0,815.10
-7
50 0,888.10
-15
0,777.10

Hình 4.9 Thuật toán kiểm tra tính nguyên tố Miller-rabin với số
nguyên lẻ n

1. Viết n-1=2
k
m, trong đó m là một số lẻ
2. Chọn số nguyên ngẫu nhiên a, 1 a (n-1 )
3. Tính b=a
m
mod n
4. IF b1 (mod n) then
Trả lời n là số nguyên tố và quit
5. For I=0 to k-1 do
6. IF b-1 (mod n) then
Trả lời n là số nguyên tố và quit
Else b=b
2
mod n
7.Trả lời n là hợp số
Chứng minh:
Ta sẽ chứng minh bằng cách giả sử thuật toán trả lời n là hợp
số với số nguyên tố n nào đó và nhân đợc mâu thuẫt. Vì thuật toán trả
lời nlà hợ số nên chắc chắn là a
m
1(mod n). Bây giờ xét dãy các
giá trị b đợc kiểm tra trong bớc 2 của thuật toán .Vì b đợc bình phơng