Chứng minh tính nguyên thủy của các số nguyên tố có thể xảy ra mạnh mẽ

Question

Sử dụng phiên bản xác suất của phép thử Miller-Rabin, tôi đã tạo danh sách các số nguyên tố có thể có kích thước trung bình (200-300 chữ số). Nhưng có thể xảy ra không đủ tốt! Tôi cần phải biết những số này là số nguyên tố. Có một thư viện nào đó - tốt nhất là gói hoặc bọc trong Python - mà thực hiện một trong các thuật toán chứng minh nguyên thủy hiệu quả hơn?

Ngoài ra, không ai biết nơi tôi có thể tìm thấy một rõ ràng, chi tiết, và hoàn mô tả về ECPP (hoặc một thuật toán nhanh tương tự) mà không giả định rất nhiều kiến ​​thức trước?

Cập nhật: Tôi đã tìm thấy một Java implementation của một thử nghiệm khác, APRT-CLE, chứng minh hoàn toàn tính nguyên thủy. Nó đã xác minh một ứng cử viên chính gồm 291 chữ số trong vòng chưa đầy 10 phút trên một bộ xử lý nguyên tử. Vẫn hy vọng điều gì đó nhanh hơn, nhưng điều này có vẻ như là một khởi đầu đầy hứa hẹn.

Answer 1

Là một thuật toán cung cấp thử nghiệm nguyên sinh đa thức đáng tin cậy, hãy xem xét AKS. Có older SO article tham chiếu các triển khai và bản trình bày thuật toán.

Answer 2

Tôi nhận thấy rằng thư viện Pari/GP và ngôn ngữ sử dụng APR-CL để chứng minh tính nguyên thủy, vốn thực sự là thuật toán ưu tiên cho các số trong phạm vi kích thước này. GP chứng minh một ứng cử viên 291 chữ số chính trong dưới 20 giây trên một bộ vi xử lý nguyên tử, đó là đủ cho nhu cầu của tôi, và nó đi kèm với một thư viện c mà tôi có thể truy cập bằng cách sử dụng ctypes.

import ctypes 

def pari_isprime(self, n): 
    try: pari = ctypes.cdll.LoadLibrary("libpari.so") 
    except OSError: 
     print "pari_isprime: couldn't load libpari!" 
     exit() 
    int(n) 
    pari.pari_init(4000000, 2) 
    ret = bool(pari.isprime(pari.gp_read_str(str(n)))) 
    pari.pari_close() 
    return ret 

Tôi cũng có thể sử dụng mô-đun instant. Đây là hàm c đơn giản chạy chuỗi thông qua trình phân tích cú pháp của pari và trả về kết quả dưới dạng chuỗi:

from instant import inline 

runpari_code = """ 
PyObject* runpari(PyObject *args) { 
    pari_init(40000000, 2); 
    char *pari_code; 
    char *outstr; 

    if (!PyArg_Parse(args, "s", &pari_code)) { return NULL; } // instant uses old-style args; for a module, use PyArg_ParseTuple 
    outstr = GENtostr(gp_read_str(pari_code)); 
    pari_close(); 
    return Py_BuildValue("s", outstr); 
} 
""" 
runpari = inline(runpari_code, system_headers=['pari/pari.h'], libraries=['pari']) 

Ở trên cũng có thể được sử dụng làm cơ sở cho phần mở rộng CPython thích hợp.