Thuật toán tìm số nguyên tố nhanh nhất năm 2024

Thuật toán kiểm tra Số Nguyên Tố

Thuật toán kiểm tra Số Nguyên Tố của một số nguyên dương, cùng với thuật toán tìm UCLN của hai số tự nhiên là những bài toán quan trọng trong Lập trình.

Kiểm tra tính nguyên tố là bài toán kiểm tra xem một số tự nhiên n có phải là số nguyên tố hay không. Bài toán này đặc biệt trở nên quan trọng khi các hệ mật mã khoá công khai ra đời.

1. Số nguyên tố là gì?

Số nguyên tố (prime) là số tự nhiên lớn hơn 1, chỉ có hai ước số là 1 và chính nó. Theo định nghĩa này thì các số 2, 3, 5, 7, 11,… là các số nguyên tố, trong đó số 2 là số nguyên tố chẵn duy nhất.

Ví dụ: 7 là số nguyên tố vì trong khoảng từ 2 đến 6 không tồn tại số nào mà 7 chia hết cả.

2. Các Thuật toán kiểm tra Số Nguyên Tố Đơn Giản

Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số m nằm trong khoảng 2 đến n-1 hay không.

Nếu n chia hết cho một trong các số m nào đó thì n không là số nguyên tố (còn được gọi là hợp số composite). Ngược lại, nếu n không chia hết cho bất kì số m nào thì kết lianaj n là số nguyên tố.

Thực ra việc kiểm tra với m từ 2 đến n-1 là không cần thiết, mà chỉ cần kiểm tra đến $\sqrt{n}$ là đủ. Vì nếu n là hợp số thì nó chắc chắn có ước số không vượt quá `n`5.

Lặp từng phần tử với bước nhảy 1 đến n-1

Giả sử cần kiểm tra số n có phải là số nguyên tố hay không thì các bước thực hiện như sau:

• Bước 1: Nhập vào n
• Bước 2: Kiểm tra nếu n`8 thì kết luận `n không phải là số nguyên tố
• Bước 3: Lặp từ 2 tới n`1, nếu trong khoảng này tồn tại số mà `n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.

Độ phức tạp của thuật toán trên là $O(n)$.

Lặp từng phần tử với bước nhảy 2

Theo định nghĩa thì số 2 là số nguyên tố chẵn duy nhất, vì vậy ta sẽ loại 2 ra khỏi vòng lặp và trong thân vòng lặp chỉ kiểm tra các số lẻ mà thôi, cách này sẽ tối ưu hơn cách 1 rất nhiều.

• Bước 1: Nhập vào n;
• Bước 2: Kiểm tra nếu n`8 thì kết luận `n không phải là số nguyên tố;
• Bước 3: Kiểm tra nếu `n`8 thì kết luận n là số nguyên tố;
• Bước 4: Kiểm tra nếu n`9 và chẵn thì kết luận `n không phải là số nguyên tố;
• Bước 5. Lặp từ m`1 tới `n`1, bước nhảy là `2 nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.

Lặp từng phần tử đến $\sqrt{n}$

Để tối ưu hơn, thay vì lặp tới n-1, chúng ta chỉ cần lặp các số từ 2 đến n`5, 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 của thuật toán trên là $O(\sqrt{n})$.

Xem mã nguồn viết bằng ngôn ngữ Dart tại đây https://divin.dev/dart/2021/10/14/bai-tap-dart-17.html

3. Tối ưu thuật toán kiểm tra số nguyên tố

Chúng ta có thể tối ưu thuật toán trên bằng cách chỉ ra n không chia hết cho những số nguyên tố nhỏ hơn nó. Tuy nhiên, chúng ta lại chưa biết được các số nguyên tố nhỏ hơn nó là những số nào (Bạn có thể sử dụng phương pháp sàng số nguyên tố – Sàng Eratosthenes để tìm ra các số nguyên tố nhỏ hơn số n cho trước). Nên ta sử dụng kết quả sau đây:

Tất cả những số nguyên tố lớn hơn `m`1 đều có dạng `2`6 (vì `2`7 là những số chẵn; `2`8 thì chia hết cho `m`1).

Do đó, chúng ta chỉ cần kiểm tra các số có dạng n-1`0 từ `2 đến n-1`2, 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ố.

def is_prime(n: int) -> bool:

"""Primality test using 6k+-1 optimization."""  
if n <= 3:  
    return n > 1  
if n % 2 == 0 or n % 3 == 0:  
    return False  
i = 5  
while i ** 2 <= n:  
    if n % i == 0 or n % (i + 2) == 0:  
        return False  
    i += 6  
return True

4. Các Thuật toán kiểm tra Số Nguyên Tố Nâng Cao

Các cách kiểm tra số nguyên tố kể trên có độ chính xác tuyệt đối nhưng khối lượng tính toán rất lớn. Theo Wiki thì chúng ta còn có những cách khác để kiểm tra tính nguyên tố của một số với một độ chính xác cho trước.

Kiểm tra theo xác suất

Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên.

Giả sử có một mệnh đề n-1`6 nào đó đúng với mọi số nguyên tố `n-1`7 và một số tự nhiên `n-1`8. Nếu `n là một số tự nhiên lẻ và mệnh đề `n`0 đúng với một `n`1 được lấy ngẫu nhiên, khi đó `n`2 có khả năng là một số nguyên tố.

Ta đưa ra một thuật toán, kết luận rằng n là số nguyên tố. Nó là một thuật toán ngẫu nhiên hay thuật toán xác suất. Trong các thuật toán loại này, dùng một kiểm tra ngẫu nhiên sẽ không bao giờ kết luận một số nguyên tố là hợp số nhưng lại có thể kết luận một hợp số là số nguyên tố. Do đó, phương pháp này không chính xác một cách tuyệt đối.

Xác suất sai của phép kiểm tra có thể giảm xuống nhờ việc chọn một dãy độc lập các số `n`2; nếu với mỗi số `n`2 xác suất để thuật toán kết luận một hợp số là số nguyên tố là nhỏ hơn một nửa thì sau `n`6 lần thử độc lập, xác suất sai là nhỏ hơn `n`7, độ tin cậy của thuật toán sẽ tăng lên theo `n`6.

Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là:

• Chọn một số ngẫu nhiên `n`2.
• Kiểm tra một hệ thức nào đó giữa số n`2 và số `n đã cho. Nếu hệ thức sai thì chắc chắn n là một hợp số (số n`2 là “bằng chứng” chứng tỏ `n là hợp số) và dừng thuật toán.
• Nếu hệ thức đúng, chúng ta lặp lại hai bước trên cho đến khi đạt được một số lần định trước hoặc gặp trường hợp dừng thuật toán.

Sau nhiều lần thử, nếu hệ thức đúng với nhiều giá trị của n`2, ta có thể nói rằng `n “có khả năng cao” là số nguyên tố chứ không thể chắc chắn n là số nguyên tố. Tất nhiên là chúng ta sẽ tìm cách tăng “khả năng” này lên bằng cách thực hiện nhiều tính toán hơn.

Các hệ thức thường sử dụng

Nếu `n-1`7 là một số nguyên tố thì

• 2 `n`1`n`2 (đây là nội dung của định lí Fermat nhỏ)
• `n`3`n`4`n`5 (với `n`3`n`4 là số Fibonacci thứ `n`4 và `n-1`7 có dạng `n`0)
• `n`1 khi và chỉ khi `n-1`7 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`3 sẽ có độ phức tạp lớn hơn `n`4.

Các phép kiểm tra tính nguyên tố ngẫu nhiên là:

• Phép kiểm tra tính nguyên tố của Fermat (kiểm tra Fermat). Đây là phép thử heuristic; tuy nhiên ít người sử dung phép thử này.
• Kiểm tra Miller-Rabin và Kiểm tra Solovay-Strassen. Với mỗi hợp số n, ít nhất 3/4 (với kiểm tra Miller-Rabin) hoặc 1/2 (Với kiểm tra Solovay-Strassen) các số n`2 là bằng chứng chứng tỏ `n là hợp số).

Các phép kiểm tra tất định

Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log n)12). Trên thực tế thuật toán này chạy chậm hơn các phương pháp xác suất.