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 là không vốn là một trong những bài toán solo giản họ đều xúc tiếp từ khi bắt đầu bập bẹ những bài toán lập trình đầu tiên. Tuy nhiên, để đáp ứng nhu cầu những nhu cầu lớn tưởng của những ngành kỹ thuật máy tính bây giờ như cryptography - mật mã hóa, hầu hết thuật toán chất vấn số nguyên tố rất cần phải vượt xa số lượng giới hạn 32 bit nhỏ dại nhoi mà thông thường chúng ta xuất xắc sử dụng.
Hôm nay chúng ta sẽ phân tích các thuật toán căn cơ để kiểm tra số yếu tố - từ "thô sơ" mang đến "hiện đại"!
1. Thuật toán đánh giá nguyên tố là gì?
Thuật toán soát sổ nguyên tố là hầu hết thuật toán để khám nghiệm xem một số trong những n có phải là số nguyên tố tốt không. Không y như thuật toán so sánh thừa số nguyên tố, kiểm tra nguyên tố dễ dàng hơn các về phương diện tính toán, bước 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 đa số thuật toán kiểm soát nguyên tố sẽ minh chứng sốncó cần là hòa hợp số tuyệt không, vì thế tên gọi đúng chuẩn của rất nhiều thuật toán vậy nên sẽ là soát sổ hợp số. Tuy vậy chúng đều hướng đến một mục tiêu là tra cứu kiếm phần đa số nguyên tố.
2. Hồ hết kiểm tra đối chọi giản
Dựa vào khái niệm của số nguyên tố (là số chỉ phân chia hết cho 1 và thiết yếu nó), ta sẽ có được được thuật toán kiểm nguyên tố đơn giản và dễ dàng nhất:
Kiểm tra những số từ bỏ 2 mang đến n - 1, nếu như n phân chia hết cho giữa những số đó thì n chưa hẳn là số nguyên tố. Ngược lại thì n là số nguyên tố.
Độ tinh vi thời gian (ĐPT) của thuật toán trên là O(n)
Tuy nhiên, giống hệt như thuật toán đếm số mong củan, ta hoàn toàn có thể cách tân để giảm ĐPT:
Kiểm tra những số từ bỏ 2 đến √n, nếu như n phân chia hết cho trong những số kia 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)
Tuy nhiên, họ còn rất có thể phát triển tiếp thuật toán trên bằng cách chứng minh nkhông phân chia hết cho phần lớn số nguyên tố nhỏ hơn nó.
Để ý rằng toàn bộ những số nguyên tố to hơn 3 đều phải sở hữu dạng 6k± 1(vì 6k,6k± 2,là đông đảo số chẵn; 6k + 3chia hết đến 3). Vậy phương thức kiểm tra từ bây giờ sẽ là:
Kiểm tra những số tất cả dạng6k ± 1 từ 2 mang lại √n, ví như n phân chia hết cho trong những số kia thì n không phải là số nguyên tố. Trái lại thì n là số nguyên tố.
// pseudocode - mã mang cho phương pháp kiểm tra thành phần trênfunction is_prime(n) if n ≤ 3 then return n > 1 else if n mod 2 = 0 or n hack 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 bọn chúng ta ban đầu vòng lặp trường đoản cú i = 5 (có dạng 6k - 1), khám nghiệm 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 vậy ta rất có thể duyệt toàn bộ các số có dạng6k± 1không quá quá√n.
ĐPT:O(√n / 6)(cũng là O(√n), nhưng nhanh hơn vài ba mili giây)
Bây giờ, thay bởi vì 6, chúng ta có thể sử dụng 30. Thay bởi 30, chúng ta có thể sử dụng tích của n số thành phần đầu tiên.
Thế nhưng phương pháp này vẫn không đủ mặc dù chỉ đối với những số nguyên 64 bit. Vì thế nên bọn họ cần những phương thức mạnh hơn với ĐPT tốt hơn.
3. đầy đủ phép thử nền tảng
Thường thì những kiểm tra nguyên tố dạn dĩ sẽ chuyển động trong thời hạn log n, đó là chính vì hầu hết đều phép test nguyên tố đơn giản sau các chạy trong thời gian ngắn nhất là log n:
Nếu p. Là một số trong những nguyên tố thì:
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 thực hiện những phép thử trên sẽ không giúp bọn họ kết luận được số sẽ thử là số nguyên tố.
Xem thêm: Ca Sĩ La Vĩnh Khiêm Lên Tiếng Về Tin Vợ Chưa Cưới Bán Dâm 1000 Đô
Ngoài ra còn phép thử: (p - 1)! ≡ -1 (mod p)khi và chỉ còn khipnguyên tố. Đây là ngôn từ của định lí Wilson, mà lại việc thống kê giám sát biểu thức(n - 1)! % nsẽ tất cả ĐPT béo hơnlog n.
Trên thực tế, trong hầu hết trường hợp, bọn họ chỉ yêu cầu phép thử thứ nhất cho các kiểm tra "sừng sỏ" bản thân sẽ trình làng sau đây.
4. Những soát sổ xác suất
Chúng được điện thoại tư vấn là "xác suất" vì sau khoản thời gian kiểm tra, chúng ta không thể thực sự chắc chắn liệu ncó nguyên tố hay là 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 nữa những phương pháp bảo vệ độ chắc hẳn rằng vì tốc độ tiến hành của chúng.
Những số quá qua kiểm tra phần trăm mà trên thực tế không phải là số nhân tố được call là mọi số "giả nguyên tố".
Kiểm tra FermatĐây là đánh giá xác suất đơn giản dễ dàng nhất. Nó trực tiếp thực hiện đị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à vừa lòng số. Ngược lại,ncó thểlà số nguyên tố.
Với a = 2, n = 341, mặc dù 341 là vừa lòng số (341 = 11 x 31), đẳng thức sau vẫn đúng:2341 - 1≡ 1 (mod 341). Bởi vì vậy, càng nhiều số a đúng cùng với đẳng thức trên, kỹ năng n là số nguyên tố càng tăng. Mặc dù nhiên, vẫn có những thích hợp số n vừa lòng đẳng thứcan - 1≡ 1 (mod n)với mọi số anguyên tố cùng cả nhà vớin, như số 561. Phần đông số bởi thế 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 chắn thêm kiểm tra Fermat, vì đây là kiểm tra số đưa nguyên tố mạnh. đánh giá này chuyển động như sau:
Chọn một số ít a bất kì nhỏ tuổi hơn n. Mang sử n - 1 = 2sd cùng 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ợp số. Ngược lại,n có thểlà số nguyên tố.
Kiểm tra Solovay-StrassenKiểm tra này tinh vi hơn dẫu vậy lại yếu hèn hơn kiểm tra Miller-Rabin.
Chọn 1 số a bất kì nhỏ dại hơn n. Nếu
Ngoài hầu hết kiểm tra tỷ lệ phổ phát triển thành trên, còn những chất vấn khác phức tạp hơn hoàn toàn như kiểm tra Frobenius hay kiểm soát Baillie-PSW. Ta cũng rất có thể sử dụng đồng thời các kiểm tra trên nhằm tăng tính đúng đắn của thuật toán. Ví dụ như kiểm tra Baillie-PSW thực hiện kiểm tra Miller-Rabin với kiểm tra phần trăm Lucas.
Tạm kết
Trên đây là những cách thức phổ biến để khám nghiệm tính yếu tắc của một số. Mặc dù sử dụng chúng thiết yếu giúp chúng ta tìm được số nguyên tố lớn số 1 hiện nay, chúng có vẻ như thừa đủ nhằm hỗ trợ bọn họ trong những vụ việc lập trình hàng ngày.
