CÁCH TÌM SỐ NGUYÊN TỐ

     

Kiểm tra xem một trong những n liệu có phải là số nguyên tố hay không vốn là một trong bài toán đối kháng giản bọn họ đều xúc tiếp từ khi new bập bẹ những vấn đề lập trình đầu tiên. Mặc dù nhiên, để đáp ứng những nhu cầu mập mạp của những ngành công nghệ máy tính hiện thời như cryptography - mật mã hóa, đều thuật toán đánh giá số nguyên tố cần được vượt xa số lượng giới hạn 32 bit bé dại nhoi mà bình thường chúng ta xuất xắc sử dụng.

Hôm nay họ sẽ phân tích các thuật toán căn cơ để đánh giá số thành phần - tự "thô sơ" cho "hiện đại"!

1. Thuật toán soát sổ nguyên tố là gì?

Thuật toán kiểm tra nguyên tố là phần đa thuật toán để bình chọn xem một trong những n liệu có phải là số nguyên tố hay không. Không giống như thuật toán đối chiếu thừa số nguyên tố, khám nghiệm nguyên tố dễ dàng và đơn giản hơn những về khía cạnh tính toán, cách thực hiện, và thời gian chạy.

Bạn đang xem: Cách tìm số nguyên tố

Hầu hết gần như thuật toán kiểm tra nguyên tố sẽ minh chứng sốncó phải là hòa hợp số xuất xắc không, vì vậy tên gọi đúng mực của phần đông thuật toán như vậy sẽ là kiểm soát hợp số. Tuy vậy chúng đều nhắm đến một kim chỉ nam là tra cứu kiếm rất nhiều số nguyên tố.

2. Những kiểm tra đối kháng giản

Dựa vào khái niệm của số yếu tố (là số chỉ phân tách hết cho 1 và thiết yếu nó), ta sẽ có được được thuật toán kiểm nguyên tố dễ dàng nhất:

Kiểm tra các số từ 2 mang lại n - 1, nếu n phân chia hết cho giữa những số kia thì n chưa hẳn là số nguyên tố. Ngược lại thì n là số nguyên tố.

Độ phức hợp thời gian (ĐPT) của thuật toán trên là O(n)

Tuy nhiên, y như thuật toán đếm số cầu củan, ta hoàn toàn có thể đổi mới để bớt ĐPT:

Kiểm tra các số từ 2 mang đến √n, nếu như n chia hết cho trong những số kia thì n không hẳn là số nguyên tố. Trái lại thì n là số nguyên tố.

ĐPT: O(√n)

Tuy nhiên, bọn họ còn hoàn toàn có thể phát triển tiếp thuật toán trên bằng phương pháp chứng minh nkhông phân chia hết cho mọi số nguyên tố nhỏ dại hơn nó.

Để ý rằng tất cả những số nguyên tố lớn hơn 3 đều phải có dạng 6k± 1(vì 6k,6k± 2,là đều số chẵn; 6k + 3chia hết cho 3). Vậy cách thức kiểm tra lúc này sẽ là:

Kiểm tra những số bao gồm dạng6k ± 1 từ bỏ 2 mang đến √n, nếu như n phân tách hết cho trong những số kia thì n chưa phải là số nguyên tố. Trái lại thì n là số nguyên tố.

// pseudocode - mã đưa cho phương pháp kiểm tra yếu tắc trênfunction is_prime(n) if n ≤ 3 then return n > 1 else if n hack 2 = 0 or n gian lận 3 = 0 return false let i = 5 while i × i ≤ n vì if n % i = 0 or n % (i + 2) = 0 return false i = i + 6 return trueĐể ý rằng chúng ta ban đầu vòng lặp trường đoản cú i = 5 (có dạng 6k - 1), bình chọn n phân chia i với n phân tách i + 2, và tăng i lên 6 sau từng bước. Do đó ta có thể duyệt tất cả các số bao gồm dạng6k± 1không quá 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ày 6, bạn cũng có thể sử dụng 30. Thay vày 30, bạn có thể sử dụng tích của n số yếu tố đầu tiên.

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

3. Gần như phép test nền tảng

Thường thì các kiểm tra nguyên tố bạo gan sẽ chuyển động trong thời gian log n, đó là bởi vì hầu hết mọi phép thử nguyên tố đơn giản và dễ dàng sau số đông chạy trong thời hạn ngắn duy nhất là log n:

Nếu phường là một số trong những nguyên tố thì:

fp + 1≡ 0 (mod p) (với fp + 1 là số Fibonacci thứ phường + 1 và p có dạng 5k± 2)

Tuy nhiên, chỉ đối kháng thuần áp dụng những phép thử trên sẽ không giúp họ kết luận được số đang thử là số nguyên tố.

Xem thêm: Sakura Thủ Lĩnh Thẻ Bài Tập 71, Xem Phim Hoat Hinh Thu Linh The Bai Sakura Tap 72

Ngoài ra còn phép thử: (p - 1)! ≡ -1 (mod p)khi còn chỉ khipnguyên tố. Đây là ngôn từ của định lí Wilson, nhưng việc giám sát và đo lường biểu thức(n - 1)! % nsẽ bao gồm ĐPT bự hơnlog n.

Trên thực tế, trong phần nhiều trường hợp, chúng ta chỉ buộc phải phép thử đầu tiên cho những kiểm tra "sừng sỏ" bản thân sẽ giới thiệu sau đây.

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

Chúng được hotline là "xác suất" vì sau khoản thời gian kiểm tra, bọn họ không thể thực sự chắc chắn liệu ncó nguyên tố hay không như những cách thức đơn giản trên. Tuy nhiên, bọn chúng lại được dùng nhiều hơn thế nữa những phương pháp bảo đảm an toàn độ chắc chắn vì tốc độ thực hiện của chúng.

Những số quá qua kiểm tra tỷ lệ mà trên thực tiễn không nên là số thành phần được điện thoại tư vấn là mọi số "giả nguyên tố".

Kiểm tra Fermat

Đây là khám nghiệm xác suất đơn giản dễ dàng nhất. Nó trực tiếp sử dụng định lí Fermat nhỏ:

Chọn số a làm thế nào cho (a, n) = 1. Nếuan - 1 ≠ 1 (mod n)thì nlà phù hợp số. Ngược lại,ncó thểlà số nguyên tố.

Với a = 2, n = 341, dù 341 là hòa hợp số (341 = 11 x 31), đẳng thức sau vẫn đúng:2341 - 1≡ 1 (mod 341). Bởi vậy, càng những số a đúng với đẳng thức trên, kỹ năng n là số yếu tắc càng tăng. Tuy nhiên, vẫn có những hòa hợp số n vừa lòng đẳng thứcan - 1≡ 1 (mod n)với các số anguyên tố bên nhau vớin, như số 561. Những số bởi vậy gọi là số Carmichael.

Kiểm tra Miller-Rabin

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

Chọn một số a bất kì bé dại hơn n. đưa 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, chưa phải phép XOR đâu)

thì nlà hòa 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 hợp hơn mà lại lại yếu hơn khám nghiệm Miller-Rabin.

Chọn một số ít a bất kì nhỏ tuổi hơn n. Nếu

*
thìnlà đúng theo số. Ngược lại,n có thểlà số nguyên tố. (vế nên làkí hiệu Jacobi)

Ngoài những kiểm tra phần trăm phổ thay đổi trên, còn những kiểm tra khác phức tạp hơn hoàn toàn như là kiểm tra Frobenius hay đánh giá Baillie-PSW. Ta cũng có thể sử dụng đồng thời các kiểm tra trên để tăng tính đúng đắn của thuật toán. Ví như kiểm tra Baillie-PSW áp dụng kiểm tra Miller-Rabin và kiểm tra tỷ lệ Lucas.

Xem thêm: Khoai Lang Nghệ Và Khoai Lang Mật, Phân Biệt Khoai Lang Mật Và Khoai Lang Bột

Tạm kết

Trên đấy là những phương pháp phổ biến đổi để khám nghiệm tính thành phần của một số. Tuy nhiên sử dụng chúng cấp thiết giúp họ tìm được số nguyên tố lớn nhất hiện nay, chúng dường như thừa đủ nhằm hỗ trợ họ trong những sự việc lập trình hàng ngày.