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

Bài viết giới thiệu một giải thuật ngẫu nhiên để giải bài toán xác định tính nguyên tố của một số tự nhiên. Giải thuật được thiết kế dựa trên cơ sở định lý nhỏ Fermat với một tập đủ nhỏ mẫu thử ngẫu nhiên và một thủ tục tối ưu để tính lũy thừa của một số tự nhiên bằng cách áp dụng hai chiến lược thiết kế chia để trị và quy hoạch động. | Một giải thuật ngẫu nhiên giải bài toán xác định số nguyên tố TAÏP CHÍ KHOA HOÏC ÑAÏI HOÏC SAØI GOØN Soá 10 (35) - Thaùng 12/2015 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 . 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 ạ ng 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 ng n ư ng N ư ng ổđể ng năng ng n (classical algorithm) ng ng n , ng n nn ng n n g n n r ng ([1], [2] [4]) T n r ng ĩn ng ư n n ng n ạn ẽ, ng ỉ g n r n n ng ồn ạ òn g ạ n n ng g ng n g n n 58 n ư ặ r ễn n nn ng n ng T e n n , n ng n n ạ g n n [4] ư O(mlog2 n), m ư ọn r n ng ng n ư a để rị (divide- rư n , n g and-conquer), b ế đổ để rị (transform- n[ ] ạ ặ O(n). and-conquer), q oạ độ ( n n ặ rưng g r gr ng), n g ạ ng n n ư rn r ng n 2, ờ g n n ng n n ạ n g n ng n ư rn r ng n ỉ ng ư r n ng n 4 rn ng n ờ g g n ng n ng ờ g n ạ r n g g ạ ng n ng n n n ạn n rn n ng n n ư ng ng n r ng n r ng ồ rọng ỉ ư ng ư g ng