Những Thuật Toán Kiểm Tra Tính Nguyên Tố
NỘI DUNG BÀI VIẾT
Kiểm tra xem một số n có phải là số nguyên tố hay không vốn là một bài toán đơn giản chúng ta đều tiếp xúc từ khi mới bập bẹ những bài toán lập trình đầu tiên. Tuy nhiên, để đáp ứng những nhu cầu lớn lao của các ngành khoa học máy tính hiện nay như cryptography – mật mã hóa, những thuật toán kiểm tra số nguyên tố cần phải vượt xa giới hạn 32 bit nhỏ nhoi mà bình thường chúng ta hay sử dụng.
Hôm nay chúng ta sẽ phân tích những thuật toán nền tảng để kiểm tra số nguyên tố – từ “thô sơ” đến “hiện đại”!
1. Thuật toán kiểm tra nguyên tố là gì?
Thuật toán kiểm tra nguyên tố là những thuật toán để kiểm tra xem một số n có phải là số nguyên tố hay không. Không giống như thuật toán phân tích thừa số nguyên tố, kiểm tra nguyên tố đơn giản hơn nhiều về mặt tính toán, bước thực hiện, và thời gian chạy.
Hầu hết những thuật toán kiểm tra nguyên tố sẽ chứng minh số n có phải là hợp số hay không, vì thế tên gọi chính xác của những thuật toán như vậy sẽ là kiểm tra hợp số. Tuy nhiên chúng đều hướng tới một mục tiêu là tìm kiếm những số nguyên tố.
2. Những kiểm tra đơn giản
Dựa vào định nghĩa của số nguyên tố (là số chỉ chia hết cho 1 và chính nó), ta sẽ có được thuật toán kiểm nguyên tố đơn giản nhất:
Kiểm tra các số từ 2 đến n - 1, nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.
Độ phức tạp thời gian (ĐPT) của thuật toán trên là O(n)
Tuy nhiên, giống như thuật toán đếm số ước của n, ta hoàn toàn có thể cải tiến để giảm ĐPT:
Kiểm tra các số từ 2 đến √n, nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.
ĐPT: O(√n)
Tuy nhiên, chúng ta còn có thể phát triển tiếp thuật toán trên bằng cách chứng minh n không chia hết cho những số nguyên tố nhỏ hơn nó.
Để ý rằng tất cả những số nguyên tố lớn hơn 3 đều có dạng 6k ± 1 (vì 6k, 6k ± 2, là những số chẵn; 6k + 3 chia hết cho 3). Vậy phương pháp kiểm tra lúc này sẽ là:
Kiểm tra các số có dạng 6k ± 1 từ 2 đến √n, nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.
// pseudocode - mã giả cho phương pháp kiểm tra nguyên tố trên
function is_prime(n)
if n ≤ 3 then
return n > 1
else if n mod 2 = 0 or n mod 3 = 0
return false
let i = 5
while i × i ≤ n do
if n % i = 0 or n % (i + 2) = 0
return false
i = i + 6
return trueĐể ý rằng chúng ta bắt đầu vòng lặp từ i = 5 (có dạng 6k - 1), kiểm tra n chia i và n chia i + 2, và tăng i lên 6 sau mỗi bước. Như vậy ta có thể duyệt tất cả các số có dạng 6k ± 1 không vượt quá √n.
ĐPT: O(√n / 6) (cũng là O(√n), nhưng nhanh hơn vài mili giây)
Bây giờ, thay vì 6, chúng ta có thể sử dụng 30. Thay vì 30, chúng ta có thể sử dụng tích của n số nguyên tố đầu tiên.
Thế nhưng phương pháp này vẫn chưa đủ dù chỉ đối với những số nguyên 64 bit. Vì thế nên chúng ta cần những phương pháp mạnh hơn với ĐPT thấp hơn.
3. Những phép thử nền tảng
Thường thì những kiểm tra nguyên tố mạnh sẽ hoạt động trong thời gian log n, đó là bởi vì hầu hết những phép thử nguyên tố đơn giản sau đều chạy trong thời gian ngắn nhất là log n:
Nếu p là một số nguyên tố thì:
2p - 1 ≡ 1 (mod p)(đây là nội dung của định lí Fermat nhỏ, ngoài ra số 2 có thể là một số khác không chia hết cho p)fp + 1 ≡ 0 (mod p)(vớifp + 1là số Fibonacci thứp + 1vàpcó dạng5k ± 2)
Tuy nhiên, chỉ đơn thuần sử dụng những phép thử trên sẽ không giúp chúng ta kết luận được số đang thử là số nguyên tố.
Ngoài ra còn phép thử: (p - 1)! ≡ -1 (mod p) khi và chỉ khi p nguyên tố. Đây là nội dung của định lí Wilson, nhưng việc tính toán biểu thức (n - 1)! % n sẽ có ĐPT lớn hơn log n.
Trên thực tế, trong hầu hết trường hợp, chúng ta chỉ cần phép thử thứ nhất cho các kiểm tra “sừng sỏ” mình sẽ giới thiệu sau đây.
4. Những kiểm tra xác suất
Chúng được gọi là “xác suất” vì sau khi kiểm tra, chúng ta không thể thực sự chắc chắn liệu n có nguyên tố hay không như những phương pháp đơn giản trên. Tuy nhiên, chúng lại được dùng nhiều hơn những phương pháp đảm bảo độ chắc chắn vì tốc độ thực hiện của chúng.
Những số vượt qua kiểm tra xác suất mà trên thực tế không phải là số nguyên tố được gọi là những số “giả nguyên tố”.
Kiểm tra Fermat
Đây là kiểm tra xác suất đơn giản nhất. Nó trực tiếp sử dụng định lí Fermat nhỏ:
Chọn số a sao cho (a, n) = 1. Nếu an - 1 ≠ 1 (mod n) thì n là hợp số. Ngược lại, n có thể là số nguyên tố.
Với a = 2, n = 341, dù 341 là hợp số (341 = 11 x 31), đẳng thức sau vẫn đúng: 2341 - 1 ≡ 1 (mod 341). Vì vậy, càng nhiều số a đúng với đẳng thức trên, khả năng n là số nguyên tố càng tăng. Tuy nhiên, vẫn có những hợp số n thỏa mãn đẳng thức an - 1 ≡ 1 (mod n) với mọi số a nguyên tố cùng nhau với n, như số 561. Những số như vậy gọi là số Carmichael.
Kiểm tra Miller-Rabin
Đây là kiểm tra rườm rà hơn nhưng chắc chắn hơn kiểm tra Fermat, vì đây là kiểm tra số giả nguyên tố mạnh. Kiểm tra này hoạt động như sau:
Chọn 1 số a bất kì nhỏ hơn n. Giả sử n - 1 = 2sd với d lẻ. Nếu:
ad ≠ 1 (mod n)a(2 ^ r)d ≠ -1 (mod n)(^ là kí hiệu phép lũy thừa, không phải phép XOR đâu)
thì n là hợp số. Ngược lại, n có thể là số nguyên tố.
Kiểm tra Solovay-Strassen
Kiểm tra này phức tạp hơn nhưng lại yếu hơn kiểm tra Miller-Rabin.
Chọn 1 số a bất kì nhỏ hơn n. Nếu thì n là hợp số. Ngược lại, n có thể là số nguyên tố. (vế phải là kí hiệu Jacobi)
Ngoài những kiểm tra xác suất phổ biến trên, còn những kiểm tra khác phức tạp hơn như kiểm tra Frobenius hay kiểm tra Baillie-PSW. Ta cũng có thể sử dụng đồng thời các kiểm tra trên để tăng tính chính xác của thuật toán. Ví dụ như kiểm tra Baillie-PSW sử dụng kiểm tra Miller-Rabin và kiểm tra xác suất Lucas.
Tạm kết
Trên đây là những phương pháp phổ biến để kiểm tra tính nguyên tố của một số. Mặc dù sử dụng chúng không thể giúp chúng ta tìm được số nguyên tố lớn nhất hiện nay, chúng có vẻ thừa đủ để hỗ trợ chúng ta trong những vấn đề lập trình hàng ngày.
Nguồn: https://codelearn.io/sharing/thuat-toan-kiem-tra-tinh-nguyen-to
Leave a Reply