Một giải thuật ngẫu nhiên giải bài toán xác định số nguyên tố

problem that decides whether a 
natural number is a prime or not. The algorithm is designed on the b f Fer ’ e e re w 
a set of random tests that is quite small and a optimized procedure to compute the power of a natural 
number by applying two strategy of the divide and conquer and the dynamic programming. We also 
implement a program for testing and comparing the performance of the randomized algorithm supposed 
and the classical algorithm when deciding whether a natural number is a prime or not. The result of 
analyzing the complexity of the algorithm as well as making real experiments have proven the 
randomized algoritm is better than the classical algorithm on the same input data set. 
Keywords: probability, randomized algorithm, natural number, prime 
1. Giới thiệu 
N ư ng ổ đ ể 
(classical algorithm) ng 
 ng n n n ng n 
 n n r ng ([1], [2] [4]) T n 
 n n 
 n r n 
g ạ n n ng g 
 ng n ư ng 
 ng năng ng n 
 ng n , 
 n g 
 r ng ĩn ng ư 
ng n ạn ẽ, ng ỉ g 
 n ng ồn ạ òn 
 ng n g n n 
59 
 n ư ặ r ễn 
T e n n , n 
 g n n [4] ư 
 r n ng ng n ư a để rị (divide-
and-conquer), b ế đổ để rị (transform-
and-conquer), q oạ độ ( n 
 r gr ng), n g ạ 
 ờ g n n ng n n 
 g n 
 ỉ ng ư r n ng 
 ờ g g n ng n ng 
g ạ ng 
 ạn n r n n ng n 
n r ng ồ rọng ỉ 
 ư g ng 
(a r n g r ) ỉn 
 ồ n 
Mặc dù gi i thu t x p xỉ là m t công 
c t ờ g g n ng 
toán ng g ờ g n 
 , n ưng ng ng ư ng 
ti n c i thi n ph c tạ ờ 
g ( ng) n g i thu t 
 c nh m nâng cao hi u qu t ng th 
c a các ng d ng th c t Đ kh c ph c 
hạn ch c a các gi i thu t c n nói 
chung và gi i thu t x p xỉ nói riêng, các 
gi i thu t ng u nhiên (randomized 
algorithm) ư c nghiên c u và phát 
tri n ([2], [5], [6]), nh m gi ph c tạp 
v thời gian gi n, n ư t gi i pháp 
thay th . 
Gi i thu t ng u nhiên là gi i thu 
 ng p d li u ng u nhiên trong 
ti n trình th c thi các dòng l nh c a nó ([2]. 
H qu là trong các gi i thu t ng u nhiên, 
các l nh có th ư c chọn ng n n 
th c hi n, d n n tính k ô đơ định 
(nondeterministic) c a gi i thu 
làm gi ph c tạp c n Tr ng 
 n , ng g 
ng n n g n n 
 n n n ng n ng 
 ng n n ạ 
O(mlog2 n), m ư ọn 
 rư n , n g 
 n [ ] ạ ặ O(n). 
 n ặ rưng g 
ng n n ư r n r ng n 2, 
 ạ n 
ng n ư r n r ng n 
 n 4 r n ng n 
 ờ g n ạ r n g 
 n ng n n n 
 n ư ng ng n r ng 
 ư ng 
 . Gi i thu t u hi 
G (randomized 
algorithm) n ư ng n 
ng R n nă 19 6 g n 
 ặ g n n ạ 
 n n ([ ], [6]) n 
 n r ng ọ ễn ư 
g ng g ng n n 
 n g n 
2.1. 
 ng n ư g r n ng, 
 ỗ ư n ư n 
 n, r ng g ng n n, ỗ 
 ư ư ọn ng n n 
 n ng n n 
g ư ng 
 n 1 g g 
 n g ng n n 
 1 
Randomized Algorithm 
Input Output 
Random
mput 
Classical Algorithm 
Input Output 
60 
Đị h hĩa .1.1. G 
nhiên g r ng ư 
 n ư ọn n ng n n 
 r n 
 ư n ng n n 
Ví dụ .1.1. r n ng A, 
B C n r n 
 ng n n ư [ ] n 
 r r n C 
 r n uông A B hay không. 
MatrixEqualityTest(A, B, C, k) 
1 for i1 to k do 
2 Choose r← (r1,...,rn)
T
 at random with 
 ri  {0,1}, i = 1,, n 
3 Compute C · r and A · (B · r) 
4 if C · r ≠ A · (B · r) 
5 then return false 
6 return true 
 k n n ư ọn 
 rư ng ư n. R r ng g 
 ờ g n ạ (kn2). 
 n n , g r g r ng 
( r e) n 1-(1/2)k T 
n A.B  C thì D = A.B-C  0 ng 
 n ng , g d11  0 ặ , 
Pr(A.B.r = C.r) = Pr((A.B-C).r = 0) = 
Pr(D.r = 0) N D.r = 0 n 
 n D.r ng 0 Ng ĩ j=1, n d1jrj = 
0. Vì d11  0 nên ta có 
N n rj r r1, ng 
 r n n n ọn 
r1{0, 1} V , r(A.B.r = C.r)  1/2. 
Vòng ặ n k n N C = A.B thì 
g n n ng N C  A.B, 
 g r g r ng 
n 1-(1/2)k. 
2.2. Phâ loạ á 
 ng n n ư n 
 ạ ư ng ng gọ g n e 
 r Veg n ư ư n 
ng ĩ n ư ([2]) 
Đị h hĩa . .1. g 
 n e r g ng n n 
 ờ g n ạ n n n n ưng 
 n 
 ng n n r ng V 
2 1 1 g n e r 
 ờ g n ạ n (kn2) 
 n n (1/2)k. 
Đị h hĩa . . . g 
Veg g ng n n n 
 ư r ng, n ưng ờ g n ạ 
 g r ng n n ỗ n 
 n n 
Ví dụ . .2 ng n n 
Randomized-Quicksort(A, p, r) 
 A[p], , A[r] ăng n 
 g Veg 
Randomized-Quicksort(A, p, r) 
1 if p<r then 
2 q  Randomized-Partition(A,p,r) 
3 Randomized-Quicksort(A,p,q-1) 
4 Randomized-Quicksort(A,q+1,r) 
Tr ng R ndomized-Partition(A,p,r) 
 g ng n n n ạ 
 A[p], , A[r] n n ỗ 
 n ư ng ng ng n n ặ 
 ng A[q] n n A[q] n ư 
Randomized-Partition(A,p,r) 
1 i ← R n (p,r) 
2 Exchange A[r] with A[i] 
3 return Partition(A,p,r) 
 , i ng n ư ọn 
 ng n n r ng ng [p, r] 
 ng R n (p,r) 
Partition(A,p,r) g n 
 n n ạ ọn ư i. 
Partition(A,p,r) 
1 x  A[r] 
2 i  p-1 
61 
3 for j  p to r - 1 
4 do if A[j] = x 
5 then i i+1 
6 Exchange A[i] with A[j] 
7 Exchange A[i+1] with A[r] 
8 return i+1 
 ư r ng, g R n e -
Quicksort(A,p,r) ỉ g 
Quicksort(A,p,r) n [1] 
 ọn ng n n n n i  [p, r] 
 A[i] cho A[r] n 
ng ĩ ạ năng 
 rư n n ờ g n 
 ạ n (n2), n = r-p 1 
 n V , g 
Randomized-Quicksort(A,p,r) n n 
 ạ ng Ng r , n ư n 
 r ng [1], ờ g n ạ g 
Randomized-Quicksort(A,p,r) 
n r ng ỗ n n ưng r ng 
 n (nlog2n) N ư , g ng 
nhiên Randomized-Quicksort(A,p,r) 
g Veg 
 . Gi i thu t u hi ị h 
 u t 
 n g n 
 n n n n ng n 
 ng r n r n có chia 
 2 n   hay không 
[7]. Tr ng n n , ng ng 
g ng n n n g 
 n Trư ng g 
 n n Fer r ng [ ] n ư 
 g ng n n n . 
Đị h lý .1. N n ng n 
 , an-1  1 (mod n), ọ *nZa = 
{1, 2, . . . , n - l}. 
 h mi h X = {a mod n, 
2a mod n,  , (n-1)a mod n} R r ng 
k ng n n X ng 0 a 
ng n ng n n n n , 
k ng ồn ạ i, j  n, (i ≠ j) sao cho ia mod 
n = ja mod n. n ngư ạ i  j 
mod n i = j T r X = {1, 
2,, n-1} a.2a...(n-1)a  [1.2...(n-
1)] mod n. Hay a
n-1  1 mod n. 
V ư r ng an-1 mod n = 1  an 
mod n = a, ng g 
ng n n ng ọn ng n n k 
 n n a  {2, 3,.., n-1} m tra e 
 n n n 
Fermat hay không. N a 
 ng an mod n = a n ng 
 ng n , ngư ạ g r 
g r ng ( r e) e n 
ng n 1  k  n-1. 
n ư . 
PrimeNumberTest(n, k) 
1 if n mod 2 = 0 
2 then return false 
3 for i1 to k do 
4 a Random(2,n-1) 
5 q Power(a,n) mod n 
6 if qa 
7 then return false 
8 return true 
Tr ng , g Power(a,n) n an. 
Ví dụ .1. Khi n = 9, ọn k =3, g 
 n r n ọn ng n n a = 
7, an mod n = 79 mod 9 = 8  a, g 
 r f e, 9 n =13, 
 ọn k =3, g n r n 
 ọn ng n n a = 9, an mod n = 913 
mod 13 = 9 = a. n ọn ng 
nhiên a = 10, an mod n = 1013 mod 13 = 
10 = a. n r ọn ng 
nhiên a = 8, th an mod n = 813 mod 13 = 8 
= a n r g ng 
 r f e, , g r 
true, 1 ng n 
 n ng n 
 ng n n ọ a  
62 
{2, ,, n−1}, an−1 ≡ 1 (mod n). Trong 
 rường n Carmichael ( 
 n n n n Fer ) 
 n n n ng 
luôn có ọ a  {2, ,, n−1}, an−1 
≡ 1 (mod n). ng, g 
 ( r ng n ng n ) 
khi n n n 
 ng (1/2)k V , ng 
g n n ng 1-(1/2)k ng 
 n ng r ng 
khi n n, ọn k = 10 (g 
 ạ ng ng n 
 n 1-(1/2)10  0.99902 khi n và 
n ng r e ) 
 T ờ g n ạ g n , 
 n ờ g n ạ g 
 Power(a, n) n n 
 n n a. Đ g 
 ng n ư 
 r ạ ng 
 n n an n ư 
Power(a,n) 
1 if n = 0 
2 then return 1; 
3 u  Power(a, n/2); 
4 if n mod 2 = 1 
5 then return u * u * a; 
6 else return u * u; 
 ọ T(n) ạ 
Power(a,n) 
 T(n) =





0),1()2/(
0),1(
nOnT
nO
 ng n er r ng [ ] 
T(n) = O(log2n) T ờ g n ạ 
g r n ng n 
 ng (k log2n) R r ng, n n, 
 k ư ọn rư n ng 
10, ờ g n ạ g ng 
n n n n n ờ g n ạ 
 g n n ạ 
g n e r . 
 ng ư r ng, n 
Power(a, n/2) ư n ạ u 
 òng r n ờ gọ r ng 
 òng 4 ặ r 
q ạ ng N ng ng òng 
 gọ r ờ gọ òng 
 ặ 6 ạ Power(a, 
n/2) (n) ng ( g2n) . 
 á 
 n n , r n ư ng r n 
 ư ng n 
nhiên n ng n ng 
 r n g ng n n r n 
 r n ng ng n g 
 n ạ r 
 n ng n ng 
 ng ờ 
g n ạ g ng n n 
 r n ng n ồ 
Tr ng g ng n n r n 
 r n, n r 
 r n ( n n), 
 r ng ng n ng ng 
 n ư V 
 ng lớ 
lớ (BigInteger class, [8]), 
 n 
 ng gIn eger ng 
 n n , -, *, /, %, 
>>, , =, <=, &, |, ^, ++, -- 
 ~ r n ng n n 
4.1. 
 n ư ng r n n ư n 
4.1 Đ n ng ẽ n 
n n ạ Input number (1), sau 
 n Classical (2) ( n 
ng n e ư ng n) ặ 
Fermat ( ) ( n ng n e 
g ng n n) N r e 
g ng n n, ư ng r n ẽ 
63 
 ng n k (k n 
 r ) 
T e , ư ng r n ẽ n 
 r n (n 
ng n - r (4); 
T ờ g n ạ e r e n – 
 r ( ) ẽ ồ r (6) ng 
 n ờ g n ạ 
 ồ ẽ ạ ồ n 
Clear all (7). 
 h 4.1: Gia diệ a h t h ị h u t 
4.2. 
N ư r n n ạ 
 g ng n n r n n 
n Fermat n n ng n 
 là O(k.log2n), r ng 
 ạ g n g ng 
 n n là . 
 ng 4 2 ễn ờ g n ạ 
 r n ng g 
 ng n n n R r ng e 
 ng n ờ g n ạ g 
 n n n n g ng 
n n, ặ n n 
 ng 4.2 
ng ng, ư ng r n ẽ ư ồ 
 n ư n 4.2 Tr ng n n , ường 
 r n ường ễn ờ g n ạ 
 g n, ường ư là 
 ường ễn ờ g n ạ g 
 ng n ên. n n , ễ r ng 
 ờ g n ạ ( ễn r ng) 
 e n n n ( 
 ễn r n ) g ng 
nhiên n n n g n 
64 
B 4.2: h thời ia hạ c i i thu t ị h u t 
S n K t qu khi th c hi n b ng gi i 
thu t c n 
K t qu khi th c hi n b ng gi i 
thu t ng u nhiên 
68718952447 11613 5878 
274876858367 23080 2436 
4398042316799 92118 3716 
 h . Đ thị h thời ia hạ a i i thu t ị h u t 
5. t lu 
Tr ng n , ng g 
 g ng n n 
 r n n 
ng n ng 
Monte Carlo. ư ng r n ng ư 
 n ng ng 
g n T n g 
 ạ ng n ư ng , g ng 
n n n n g 
 n 
Tr ng ư e , ng ẽ 
 n n ư ng 
 ọn n k n 
g ng n g 
 ng n n ạ Las Vegas 
 g ng n n 
ng Ng r , ng ng ẽ ng 
 g ng n n 
g n n ư 
 r n n , ặ g n n n 
TÀI LIỆU T AM ẢO 
1. Cormen, T.H., Leiserson, C.E., Rivest, R.D., 
Stein, C. (2009), Introduction to Algorithms, 
McGraw-Hill Book Company. 
65 
2. Karp, R.M. (1991), An introduction to 
randomized algorithm, Discrete Applied 
Mathematics, 34, 165-201. 
3. Lee, R.C.T., Tseng, S.S., Chang, R.C., Tsai, 
Y.T. (2005), Introduction to The design and 
Analysis of Algorithms: A Strategic Approach, 
McGraw-Hill Education. 
4. Levitin, A. (2014), Introduction to The design 
and Analysis of Algorithms, Addison-Wesley. 
5. Mitzenmacher, M., Upfal, E. (2005), 
Probability and Computing Randomized 
Algorithms and Probabilistic Analysis, 
Cambridge university press. 
6. Motwani, R., Prabhakar, R.P. (1995), 
Randomized algorithms, Cambridge 
university press. 
7. Rosen, K.H. (2014), Discrete Mathematics 
and Its Applications, Prentice Hall Inc.,. 
8. 
BigInteger-Class, 20/7/2015. 
Ng n n : 12/10/2015 n ng: 15/12/2015 ăng: 20/12/2015