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 dĩ là một bài toán dễ dàng tất cả 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 trước nhất. Bên cạnh đó, để thỏa mãn những nhu cầu to lớn của các nghề khoa học laptop hiện tại như cryptography – mật mã hóa, những thuật toán kiểm soát số nguyên tố cần phải vượt xa hạn chế 32 bit nhỏ nhoi mà bình bình tất cả chúng ta hay sử dụng.

Lúc này tất cả chúng ta sẽ nghiên cứu những thuật toán nền móng để kiểm soát số nguyên tố – từ “thô sơ” đến “hiện đại”!

1. Thuật toán kiểm soát nguyên tố là gì?

Thuật toán kiểm soát nguyên tố là những thuật toán để kiểm soát 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 nghiên cứu thừa số nguyên tố, kiểm soát nguyên tố dễ dàng hơn nhiều về mặt tính toán, bước thực hiện, & thời gian chạy.

Chủ yếu những thuật toán kiểm soát nguyên tố sẽ minh chứng số n có phải là hợp số hay không, chính vì như vậy cái tên chuẩn xác của những thuật toán như thế sẽ là kiểm soát hợp số. Bên cạnh đó chúng đều nhắm tới một mục tiêu là tìm kiếm những số nguyên tố.

2. Những kiểm soát dễ dàng

Dựa theo khái niệm của số nguyên tố (là số chỉ chia hết cho 1 & chính nó), ta sẽ có được thuật toán kiểm nguyên tố dễ dàng 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ố. Trái lại thì n là số nguyên tố.

Độ cầu kỳ thời gian (ĐPT) của thuật toán trên là O(n)

Bên cạnh đó, giống như thuật toán đếm số ước của n, ta tuyệt đối có thể cải tạo để giảm ĐPT:

Xem Thêm  -attributes-and-apis:cereactions-7"">CEReactions] attribute [

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ố. Trái lại thì n là số nguyên tố.

ĐPT: O(√n)

Bên cạnh đó, tất cả chúng ta còn tồn tại thể tiến triển tiếp thuật toán trên bằng cách minh chứng n không chia hết cho những số nguyên tố bé hơn nó.

Chú tâm rằng toàn bộ những số nguyên tố to 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 thức kiểm soát giờ đâ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ố. Trái lại thì n là số nguyên tố.

// pseudocode - mã giả cho phương thức kiểm soát 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

Chú tâm rằng tất cả chúng ta khởi đầu vòng lặp từ i = 5 (có dạng 6k - 1), kiểm soát n chia i & n chia i + 2, & tăng i lên 6 sau mỗi bước. Như thế ta có thể duyệt toàn bộ 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 mau hơn vài mili giây)

Giờ đây, thay vì 6, tất cả chúng ta có thể sử dụng 30. Thay vì 30, tất cả chúng ta có thể sử dụng tích của n số nguyên tố trước nhất.

Thế nhưng phương thức này vẫn chưa đủ dù chỉ so với những số nguyên 64 bit. Vì vậy nên tất cả chúng ta cần những phương thức mạnh hơn với ĐPT ít hơn.

3. Những phép thử nền móng

Thường thì những kiểm soát nguyên tố mạnh sẽ hoạt động trong thời gian log n, này là bởi vì đa phần những phép thử nguyên tố dễ dàng sau đều chạy trong khoảng thời gian ngắn đặc biệt là log n:

Nếu p là một số nguyên tố thì:

  • 2p - 1 ≡ 1 (mod p) (đây là bài viết của định lí Fermat nhỏ, tuy nhiên 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 & p có dạng 5k ± 2)

Bên cạnh đó, 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ổng kết được số đang thử là số nguyên tố.

Xem Thêm  Định dạng HTML: in đậm, in nghiêng, gạch chân, chỉ số trên, chỉ số dưới trong HTML

không dừng lại ở đó còn phép thử: (p - 1)! ≡ -1 (mod p) khi & chỉ khi p nguyên tố. Đây là bài viết của định lí Wilson, nhưng việc tính toán biểu thức (n - 1)! % n sẽ có ĐPT to hơn log n.

Trên thực tiễn, trong đa phần trường hợp, tất cả chúng ta chỉ cần phép thử đầu tiên cho các kiểm soát “sừng sỏ” mình sẽ giới thiệu sau đây.

4. Những kiểm soát xác suất

Chúng được gọi là “xác suất” vì sau thời điểm kiểm soát, tất cả chúng ta chẳng thể thực sự chắc rằng liệu n có nguyên tố hay không như những phương thức dễ dàng trên. Bên cạnh đó, chúng lại được dùng nhiều hơn những phương thức bảo đảm độ chắc rằng vì vận tốc thực hiện của chúng.

Những số vượt mặt kiểm soát xác suất mà trên 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 soát xác suất dễ dàng 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ố. Trái 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). Chính vì thế, 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. Bên cạnh đó, vẫn có những hợp số n đáp ứng đẳng thức an - 1 ≡ 1 (mod n) với mọi số a nguyên tố bên nhau với n, như số 561. Những số như thế gọi là số Carmichael.

Xem Thêm  iframe

Kiểm tra Miller-Rabin

Đây là kiểm soát rắc rối hơn nhưng chắc rằng hơn kiểm soát Fermat, vì đây là kiểm soát số giả nguyên tố mạnh. Kiểm tra này hoạt động như sau:

Chọn 1 số a bất cứ bé 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ố. Trái lại, n có thể là số nguyên tố.

Kiểm tra Solovay-Strassen

Kiểm tra này cầu kỳ hơn nhưng lại yếu hơn kiểm soát Miller-Rabin.

Chọn 1 số a bất cứ bé hơn n. Nếu  thì n là hợp số. Trái lại, n có thể là số nguyên tố. (vế phải là kí hiệu Jacobi)

Ngoài những kiểm soát xác suất thông dụng trên, còn những kiểm soát khác cầu kỳ hơn như là kiểm soát Frobenius hay kiểm soát Baillie-PSW. Ta cũng có thể sử dụng song song các kiểm soát trên để tăng tính chuẩn xác của thuật toán. Chẳng hạn như kiểm soát Baillie-PSW sử dụng kiểm soát Miller-Rabin & kiểm soát xác suất Lucas.

Tạm kết

Trên đây là những phương thức thông dụng để kiểm soát tính nguyên tố của một số. Mặc dầu sử dụng chúng chẳng thể giúp tất cả chúng ta tìm được số nguyên tố lớn nhất hiện tại, chúng có lẽ thừa đủ để suport tất cả chúng ta trong những vấn đề lập trình mỗi ngày.

Nguồn: Wikipedia

Viết một bình luận