Tài liệu Kỹ thuật lập trình - Chương 3: Kiểm tra và xây dựng số nguyên tố

Dựa vào tính chất đặc biệt của số nguyên tố, mà khi xây dựng một số bài toán với việc áp dụng số nguyên tố, đặc biệt là ứng dụng số nguyên tố lớn, nó trở nên hữu ích cho mục đích bài toán. Trong chương này chúng ta đi tìm hiểu cách kiểm tra một số nguyên tố cho trước và làm thế nào để xây dựng được số nguyên tố lớn.
Nội dung trích xuất từ tài liệu:
Tài liệu Kỹ thuật lập trình - Chương 3: Kiểm tra và xây dựng số nguyên tố Chương 3 KIỂM TRA VÀ XÂY DỰNG SỐ NGUYÊN TỐ Dựa vào tính chất đặc biệt của số nguyên tố, mà khi xây dựng một số bài toán v ớiviệc áp dụng số nguyên tố, đặc biệt là ứng dụng số nguyên tố lớn, nó trở nên hữu íchcho mục đích bài toán. Trong chương này chúng ta đi tìm hiểu cách kiểm tra một sốnguyên tố cho trước và làm thế nào để xây dựng được số nguyên tố lớn. 3.1 Khái niệm về số nguyên tố Số tự nhiên p, lớn hơn 1 gọi là số nguyên tố nếu như nó chia hết cho 1 và chính nó.Định lý cơ bản của số học nói rằng, bất kỳ số tự nhiên n, lớn hơn 1 có thể phân tíchthành tích các số nguyên tố. Tức là một số tự nhiên có thể biểu diễn dưới dạng sau α α n = p1 1 ... pk k ,ở đây p1 < p2 < ... < pk - là các số nguyên tố khác nhau, α1 ,..., α k ∈ N . Bài toán kiểm tra số nguyên tố và xây dựng số nguyên tố lớn có ứng dụng rất quantrọng trong mã hóa. Trong phần này tác giả viết về các thuật toán khác nhau đ ể giảiquyết những bài toán này 3.2 Kiểm tra số nguyên tố theo phương pháp thử Cho n ∈ N . Kiểm tra xem n có phải là số nguyên tố hay không Phương pháp thử chia Nếu như n là hợp số, thì n=ab, với 1 < a ≤ b , điều kiên là a ≤ n . Cho nên đối với [ ]d = 2,3,..., n chúng ta kiểm tra xem n có chia hết cho d hay không? Nếu như ước s ốcủa n không tìm thấy, thì n là số nguyên tố, ngược lại thì n là hợp số, và ta có thể phântích n thành 2 thừa số. Độ phức tạp của phương pháp này là O( n ) . Sàng Eratosphen Nếu như chúng ta muốn thiết lập bảng tất cả các số nguyên tố giữa các số 2,3,…,N,thì đầu tiên cần gạch chân các số chia hết cho 2 ngọai trừ số 2. Sau đó ta lấy các số 3 vàgạch chân các số tiếp theo và chia hết cho 3. Sau đó chúng ta chọn số tiếp theo và khônggạch chân (có nghĩa là 5), và tiếp tục gạch chân các số chia hết cho 5, và tiếp tục nhưthế. Và cuối cùng chúng ta có được dãy các số nguyên tố. Phương pháp này thì t ốnnhiều bộ nhớ, nhưng để thành lập bảng nguyên tố thì đây là cách hiệu quả nhất. 3.3 Kiểm tra tính nguyên tố của số có dạng đặc biệt Chúng ta xem số n dạng n = 2 m + 1 , ở đây m ∈ N . Nếu m chia hết cho số nguyên tốp > 2 , tức là m = pm1 , m1 ≥ 1 , thì n = (2m1 ) p + 1 chia hết cho 2 m1 + 1 , có nghĩa là n là hợpsố. Cho nên số nguyên tố có thể chỉ khi m = 2k . k Định nghĩa 3.1. Số Fk = 2 2 + 1, k = 0,1,2,..., gọi là số Fermat. Hiện tại chúng ta biết được rằng F0 , F1 , F2 , F3 , F4 là số nguyên tố, còn các số Fermattiếp theo 5 ≤ k ≤ 32 là hợp số, còn các số tiếp theo thì chưa được kiểm tra. Để kiểm tra tính nguyên tố của số Fermat chúng ta xem định lý sau Định lý 3.1. Số n = Fk khi k>0 là số nguyên tố khi và chỉ khi: n −1 3 2 ≡ −1(mod n) . Chứng minh: Chúng ta chứng minh điều kiện đủ. Chúng ta có: n − 1 = 22 . Từ k n −1 n −13 2 ≡ −1(mod n) , nên 3 ≡ 1(mod n) , điều này có nghĩa là bậc của 3 (mod n) bằng *n − 1 = 2 2 . Nên nhóm nhân Z n có ít nhất là n-1 phần tử, và các phần tử khác không của kZn khả nghịch, hay n là số nguyên tố. k k −1 Bây giờ ta chứng minh phần nghịch. Chú ý rằng 2 2 ≡ 42 ≡ 1(mod 3) . Bởi vậy n>3,n ≡ 2(mod 3), n ≡ 1(mod 4) . Theo định luật bình phương (định lý Gausse) ta có ( n −1)( 3 −1) n−13 n n 2 3  =  .( −1) 4 =   =   = −1 . Theo tiêu chuẩn Euler thì  ≡3 2 (mod n) .n 3  3 3 n Kiểm tra theo định lý này độ phức tạp là O(log n) , thế nhưng số Fermat tăng lên rấtnhanh, nên cách kiểm tra này trở nên không hiệu quả. Bây giờ chúng ta xem số n dạng n = 2m − 1 . Nếu m là hợp số, m=ab, 1 < a ≤ b , thìn = 2 ab − 1 chia hết cho n = 2 a − 1 . Cho nên số n là nguyên tố chi khi m là số nguyên tố. Định nghĩa 3.2. Cho p là số nguyên tố, và M p= 2 − 1 cũng là số nguyên ...