Tôi đang tìm kiếm một thuật toán để kiểm tra tính nguyên thủy lớn (như số 10). Có bất kỳ thuật toán tốt nào không?Xác định một cách xác định xem một số lớn là số nguyên tố hay composite?
Lý tưởng nhất, tôi thích một thuật toán không phải là probabalistic.
Lưu ý: Số có trên 50 và nhỏ hơn 200 chữ số.
Nếu bạn đang tìm kiếm một thử nghiệm phi probabalistic, bạn có thể muốn kiểm tra các AKS primality testing algorithm, chạy trong khoảng O (log n) thời gian. Đối với số chữ số bạn có, điều này có thể khả thi.
Điều đó nói rằng, kiểm tra tính nguyên thủy của probabalistic là cực kỳ tốt và nhiều người có tỷ lệ lỗi nhỏ theo cấp số nhân. Tôi sẽ đề nghị sử dụng một trong những điều đó trừ khi có lý do chính đáng để không.
EDIT: Tôi vừa tìm thấy this page containing several C++ implementations of AKS. Tôi không biết họ có hoạt động chính xác hay không, nhưng chúng có thể là một điểm khởi đầu tốt.
Hy vọng điều này sẽ hữu ích!
về thuật toán AKS: thuật toán này sử dụng hàm log() và sqrt() cho số lớn (như 10^200). nó là tốn kém cho việc thực hiện. kiểm tra bằng lời nói là tốt, cảm ơn bạn! tôi sẽ dùng nó! – gaussblurinc
Chi phí có thể được tính toán như thế nào để tính 'sqrt (10^200)'? –
Thông thường chúng tôi sẽ sử dụng thử nghiệm chính có thể xảy ra. Tôi khuyên bạn nên BPSW, bạn có thể làm theo bài kiểm tra Frobenius và/hoặc một số bài kiểm tra Miller-Rabin ngẫu nhiên nếu bạn muốn chắc chắn hơn. Điều này sẽ nhanh chóng và được cho là nhiều hơn nhất định hơn là chạy một số triển khai bằng chứng.
Giả sử bạn nói điều đó không đủ tốt. Sau đó, bạn thực sự muốn sử dụng ECPP và nhận được chứng chỉ. Triển khai hợp lý là Primo hoặc ecpp-dj. Đây có thể chứng minh tính nguyên thủy của 200 chữ số trong vòng chưa đầy một giây và trả lại chứng chỉ có thể được xác minh độc lập.
APR-CL là một phương pháp hợp lý khác. Nhược điểm là nó không trả lại một chứng chỉ để bạn tin tưởng việc thực hiện - bạn nhận được một "có" hoặc "không" đầu ra đó là xác định chính xác nếu việc thực hiện là chính xác. Pari/GP sử dụng APR-CL với lệnh isprime và David Cleaver có một triển khai mã nguồn mở tuyệt vời: mpz_aprcl. Những triển khai đã có một số xem xét mã và sử dụng hàng ngày trong các phần mềm khác nhau vì vậy nên được tốt.
AKS là phương pháp kinh khủng để sử dụng trong thực tế. Nó không trả lại một chứng chỉ, và không quá khó để tìm ra các triển khai bị hỏng, mà hoàn toàn đánh bại điểm của việc sử dụng một phương pháp chứng minh so với các thử nghiệm nguyên tố tốt có thể xảy ra ngay từ đầu. Nó cũng rất chậm. 200 chữ số cũng vượt qua điểm thực tế cho bất kỳ triển khai nào mà tôi biết. Có một "nhanh" một bao gồm trong phần mềm ecpp-dj đã đề cập trước đó, do đó bạn có thể thử nó ra, và có khá một vài triển khai khác được tìm thấy.
Đối với một số ý tưởng về tốc độ, đây là thời gian của một số triển khai. Tôi không biết bất kỳ triển khai nào của AKS, APR-CL, hoặc BPSW nhanh hơn so với những gì được hiển thị (xin vui lòng bình luận nếu bạn biết). Primo bắt đầu chậm hơn một chút so với ecpp-dj được hiển thị, nhưng ở 500 hoặc hơn chữ số nó là nhanh hơn, và có một dốc tốt hơn qua đó. Đây là chương trình lựa chọn cho đầu vào lớn (2.000-30.000 chữ số).
Chỉ cần tra cứu trên wikipedia.Nhưng tôi có thể sử dụng một thuật toán xác suất. Bạn có thể nhận được cơ hội lỗi theo cấp số nhân nhỏ, do đó cơ hội lỗi do bản thân bài kiểm tra là nhỏ so với khả năng xảy ra lỗi phần cứng. – CodesInChaos