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

TAÏP CHÍ KHOA HOÏC ÑAÏI HOÏC SAØI GOØN Soá 10 (35) - Thaùng 12/2015 58 g A randomized algorithm solving the problem of deciding a prime TS. Nguyễn Hòa Trường Đại học Sài Gòn Ph.D. Nguyen Hoa Sai Gon University Tóm tắt n g g ng n n g n n n ng n n n ư r n n n Fermat n ng n n ư n n n ng ng n ư r ạ ng ng ng n ư ng r n ng n n g ng n n ng g n n n ng n n n n ạ ng n ư ng g ng n n ờ g n ạ n g n r n ng : Abstract This paper introduces a randomized algorithm for solving the 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