Các cách kiểm tra số nguyên tố

Trong đời sống, số nguyên tố được ứng dụng trong rất nhiều lĩnh vực của chúng ta. Nhờ vào tính chất số học của mình, nó đã được sử dụng nhiều trong lĩnh vực mã hóa, bảo mật, cũng như trong một số thuật toán tạo số ngẫu nhiên, bảng băm, hay trong giải thuật mã hóa RSA...Nhưng quan trọng nhất vẫn là làm sao để chúng ta biết được một số nào đó có phải là số nguyên tố? Vì vậy trong bài viết hôm nay chúng ta sẽ cùng điểm qua một số cách để kiểm tra tính nguyên tố của một số bất kì.

Lưu ý: các thuật toán trong bài viết này được sắp xếp theo độ phực tạp thời gian giảm dần.

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

Số nguyên tố là số tự nhiên  lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có đúng hai ước số  là 1 và chính nó. 

Tất cả số nguyên tố lớn hơn 3 đều có thể biểu diễn dưới dạng  6k ± 1.

Ngoại trừ số 2 các số nguyên tố lớn hơn đều là số lẻ.

    2. Môt số giải thuật kiểm tra số nguyên tố n:

• Giải thuật đơn giản O(n):

                    Dựa vào tính chất của số nguyên tố chỉ có 2 ước duy nhất là một và chính nó nên một  trong những phương pháp đơn giản là chúng ta sẽ duyệt qua các số từ 2 đến n-1 và kiểm tra xem với mỗi số duyệt qua n có chia hết cho số nào hay không? nếu có ta có thể kết luận ngây số n không là số nguyên tố ngược lại số n là một số nguyên tố.

• Giải thuật chia thử O(√n):

                      Chúng ta có thể cải tiến thuật toán ở trên như sau thay vì duyệt tới n-1 ta có thể duyệt tới √n vì  nếu n chia hết cho một thừa số nhỏ hơn thì cũng chia hết cho thừa số lớn hơn bé hơn n vì thừa số lớn hơn là bội của thừa số nhỏ hơn đã duyệt. Hay nói cách khác nếu n chia hết cho i cũng đồng nghĩa n chia hết cho n/i.

• Cải tiến giải thuật chia thử O(√n):

                    Chúng ta biết một tính chất quan trọng của số nguyên tố là với mọi số nguyên tố lớn hơn 3 chúng ta đều có thể biểu diễn dưới dạng  6k ± 1.Vì vậy để cải tiến thuật trên chúng ta sẽ xét xem số có chia hết cho 2 hoặc 3 hay không sau đó kiểm tra qua các số có dạng  6k ± 1 bé hơn hoặc bằng căn của n. Ngoài ra việc sử dụng hàm sqrt() có thể dẫn đến một số rất rối với số lớn vì hàm sqrt() trả về một kiểu dữ liệu số thực nên ta có thể cải tiến hàm sqrt() bằng i*i<=n việc đảm bảo tính an toàn hơn của thuật.

    

Qua việc cải tiến trên ta có thể thấy tốc độ kiểm tra bây giờ đã tăng gấp 3 lần so với ban đầu.

• Sàng nguyên tố Eratosthenes O(nlogn):

                    Giả sử chúng ta cố một bài toán yêu cầu kiểm tra các số từ 1 đến N có phải là số nguyên tố hay không với N khoảng 10^6. Nếu chúng ta áp dụng giải thuật chia thử đã cải tiến với các số từ 1 đến N độ phức tạp có thể đạt được là O(n√n) với N lến tới 10^6 thì đây với độ phức tạp này có thể xem là tương đối lớn. Tuy nhiên chúng ta có thể cải tiến bằng cách sử dụng sàng số nguyên tố với độ phức tạp là O(nlogn) với độ phức tạp này ta có thể giải quyết một số bài toàn trong 1s mà độ phức tạp trong không thể làm được.

                    Nguyên lý hoạt động của thuật toán này khá đơn giản:

                        +Đầu tiên ta sẽ dựng nên một sàng gồm các số tự nhiên từ 1 đến N

                        +Sau đó vào mỗi lần duyệt sàng ta sẽ chọn một số nguyên tố và loại ra khỏi sàng tất cả các bội của số nguyên tố đó mà lớn hơn số đó. Sau khi duyệt xong các số trong sàng sẽ đều là các số nguyên tố bé hơn N

Sau khi xây dựng sàn việc kiểm tra 1 số trong khoảng từ đến N có phải là số nguyên tố hay không chỉ mất O(1).

• Thuật toán Fermat:

• Thuật toán MillerRabin: