1
Chương 5. TÍNH NGẪU NHIÊN TRONG TÍNH TOÁN

NỘI DUNG
5.1 Máy Turing ngẫu nhiên và các vấn đề liên quan
5.2 Thuật toán thử Monte-Carlo
5.3 Tính ngẫu nhiên và độ phức tạp
5.4 Tính giả ngẫu nhiên
5.5 Mật mã

TÀI LIỆU THAM KHẢO

1. Bài giảng về cơ sở tính toán tại địa chỉ
2. Dexter C. Kozen. Theory of Computation. Springer, 2006
3. Michael Sipser , Introduction to the Theory of Computation, 2nd edition,
Couse technology 2005
4. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata
Theory, Languages, and Computation (2nd Edition), Addison Wesley, 2000.
2
5.1 Máy Turing ngẫu nhiên và các vấn đề liên quan
5.1.1 QuickSort: Một ví dụ về thuật toán ngẫu nhiên
Đặt bài toán: Cho một danh sách (a) gồm n phần tử a
1
, …, a
n
. Cần sắp xếp (a)

- Chép băng 4, rồi băng 5 vào vị trí của danh sách con trên băng 1 và đặt một dấu
ngăn cách giữa các dãy con này.
- Nếu có một dãy con mới có > 1 phần tử thì sắp đệ qui theo thuật toán vừa trình
bày. 4
5.1.3 Ngôn ngữ của máy Turing ngẫu nhiên
Xét RM chỉ có 1 băng input và băng ngẫu nhiên, không thay đổi các ký hiệu trên
băng mà chỉ di chuyển đầu đọc-ghi sang phải (R) hoặc đứng yên (S). Mỗi ký hiệu trên
băng (XY), trong đó X là ký hiệu trên băng input, Y là ký hiệu trên băng ngẫu nhiên.
Mỗi hướng di chuyển (DE), trong đó D trên băng input, E trên băng ngẫu nhiên.
Bảng hàm chuyển vị: 00
01
10
11
B0
B1
 q
0

q
1
00RS
q
3
01SR

q
4
B0SS

q
3

q
3
00RR q
3
11RR
q
4
B0SS
q
4
B1SS
*q
4


.

5.1.4 Lớp RP
Định nghĩa: L là ngôn ngữ thuộc lớp RP (Random Polynomial) khi và chỉ khi L
được thừa nhận bởi một máy RM thỏa mãn
- w  L  xác suất RM thừa nhận w bằng 0.
- w  L  xác suất RM thừa nhận w  1/2.
- Tồn tại đa thức p(n) để độ phức tạp tính toán T(n)  p(n).
Máy RM là Monte-Carlo  nếu RM thừa nhận mọi w với xác suất 0 hoặc xác suất
 1/2.
Ví dụ ở trên không phải là Monte-carlo.
6
5.1.5 Lớp ZPP
Định nghĩa: L là ngôn ngữ thuộc lớp ZPP (Zero-error Probabilistic Polynomial) khi
và chỉ khi L được thừa nhận bởi một máy RM luôn dừng thỏa mãn
- w  L  xác suất RM thừa nhận w bằng 0.
- w  L  xác suất RM thừa nhận w > 0.
- Tồn tại đa thức p(n) để độ phức tạp tính toán T(n)  p(n).
Máy RM là Las-Vegas  nếu RM thừa nhận mọi w với xác suất nào đó.
Định lý: ZPP = ZP  co-RP, trong đó co-RP là lớp các ngôn ngữ thỏa mãn: L thuộc
vào co-RP  phần bù của L thuộc vào lớp RP.

2
mod p) = (
i
x
2
mod p), i < q. Sau đó biểu
diễn q dưới dạng nhị phân , tức là tổng của các lũy thừa của 2 và nhân mod p cần x’
i
s.

8
5.2.2. Phép thử Fermat

Định lý nhỏ Fermat : Với mỗi x  [1, p-1] và số nguyên tố p có x
p-1
 1 (mod p).
Chứng minh : Thật vậy, dãy (xi mod p) là một hoán vị của 1, 2, …, p-1. Do đó, 1 

i<p
(xi)/(p-1) !  x
p-1
(mod p).
- Định lý trên chỉ đúng với số p nguyên tố. Với hợp số p cần dùng cách thử khác.

5.2.3. Phép thử căn bậc hai

Bổ đề : Đối với mỗi số y và số nguyên tố p, phương trình (x

- Nếu x
0
= 1, hoặc một trong các x
i
= -1 thì T(x
m
, p) = 1 với m > i. 9
- Nếu x
k
 1 thì phép thử Fermat không sử dụng được và xét z = x
i
 1sao cho (z
2

mod p) = x
i+1
= 1. Tiếp theo áp dụng phép thử căn bậc hai các nhân tử của p.
Giả sử p là hợp số lẻ. Xét p = a
j
, j > 1, với a là số nguyên tố và x = 1 + p/a. Có (1 +
p/a)
p-1
= 1 + (p/a)(p-1) + …  1 – p/a  1 (mod p). Khi đó có thể sử dụng phép thử
Fermat.
Giả sử x = a*b, với gcd(a, b) = 1. Xét x’ = 1 + b*(1/b mod a)*(x-1). Khi đó x’  1 
x’
i

Xét U là thuật toán phổ dụng sao cho K
U
(x) < K
A
(x) + O(1) với mỗi A. Nếu y rỗng
thì coi K
U
(x/y) như là K
A
(x/y) hay K
A
(x).
Ví dụ : Xét A : x  x có K
A
(x) = x. Do đó K(x) < K
A
(x) + O(1) < x + O(1).
Giả sử L(x)  O(1) tính cận dưới của K(x). Sử dụng hàm f(n) tìm x với n < L(x) <
K(x). Do K(x) < K
f
(x) + O(1) và K
f
(f(n))  n nên n < K(f(n)) < n + O(1) =
log O(n) < n nên K không có cận dưới. Vì vậy K(x) là không tính được.

5.3.2. Số khuyết của tính ngẫu nhiên
Với mỗi xâu x được sinh ngẫu nhiên, d(x) = x – K(x/x) (d(x) > -O(1)).
Tính xác suất của biến cố: {d(x) > i: x = n}.
- Có 2
n

.
Tích XZ là ma trận cấp nxi có phân phối không chuẩn xấp xỉ






k
ni
O
2
.
12
5.4. Tính giả ngẫu nhiên

G
. Giả sử thuật toán ngẫu nhiên
A chạy với thời gian kỳ vọng t
A
thừa nhận G(s) và xâu ngãu nhiên với sự sai khác
xác suất d. Khi đó, với mỗi i ngẫu nhiên có thể sử dụng A để ước đoán S
i
từ S
i+1
,
S
i+2
, … với thời gian t
A
+ t
G và
độ chính xác d/O(n).

5.4.2 Lõi cứng (Hard core)
Cho B
p
(x) = (x.p) = (
i
x
i
p
i
mod 2). Có thể chuyển một phương pháp g ước đoán
B
p

.x); s
i+1
= (s
i
2
mod
n), trong đó n = p*q được phép công khai, còn p, q là giữ bí mật.
- Mã hóa bằng cách chọn x, s
0
một cách ngẫu nhiên và gửi x, s
k
và m S.
- Giải mã bằng cách biết p, q và tính u, t và v = (u
k-1
mod t). Tiếp theo tính s
1
= (s
v
k
mod n)
và S, m.
- Một cách khác là sử dụng tính khó của phân tích nhân tử đối với các tín hiệu số. Xâu x có
thể tách ra thành các phần cho phép y = (x
2
mod n). Bất cứ ai cũng có thể xác thực x,
nhưng không thể giả mạo x do chỉ có người sử dụng hợp pháp biết được các nhân tử của n
và có thể tính căn bậc hai. 14