Những Thuật Toán Kiểm Tra Tính Nguyên 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 tất cả chúng ta sẽ nghiên cứu và 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 ” tân tiến ” !

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 thuầ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 chiêu thức này vẫn chưa đủ dù chỉ so với những số nguyên 64 bit. Vì thế nên tất cả chúng ta cần những chiêu thức 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ới fp + 1 là số Fibonacci thứ p + 1 và p có dạng 5k ± 2)

Tuy nhiên, chỉ đơn thuần sử dụng những phép thử trên sẽ không giúp tất cả chúng ta Tóm lại đượ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 tiễn, trong hầu hết trường hợp, tất cả chúng ta chỉ cần phép thử thứ nhất cho những kiểm tra ” sừng sỏ ” mình sẽ ra mắt 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 Phần Trăm mà trên trong thực tiễn 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 thuầ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 như đinh 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 giải trí 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 Tỷ Lệ thông dụng 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 hoàn toàn có thể sử dụng đồng thời những kiểm tra trên để tăng tính đúng chuẩn 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 Tỷ Lệ Lucas .

Tạm kết

Trên đây là những giải pháp thông dụng để kiểm tra tính nguyên tố của một số ít. Mặc dù sử dụng chúng không hề giúp tất cả chúng ta tìm được số nguyên tố lớn nhất lúc bấy giờ, chúng có vẻ như thừa đủ để tương hỗ tất cả chúng ta trong những yếu tố lập trình hàng ngày .
Nguồn : Wikipedia

Source: https://vh2.com.vn
Category : Tin Học