Một giải thuật ngẫu nhiên giải bài toán xác định số nguyên tố

Bài báo này giới thiệu một giải thuật ngẫu nhiên để giải bài toán xác định tính nguyên tố của một số tự nhiên. Giải thuật được thiết kế dựa trên cơ sở định lý nhỏ Fermat với một tập đủ nhỏ mẫu thử ngẫu nhiên và một thủ tục tối ưu đế tính lũy thừa của một số tự nhiên bằng cách áp dụng hai chiến lược thiêt kế chia đề trị và qui hoạch động. Chúng tôi cũng hiện thực một chương trình thử nghiệm để so sánh tính hiệu quả của giải thuật ngẫu nhiên đã đề nghị và giải thuật |cố điến khi xác định tính nguyên tố của một số tự nhiên. Phân tích độ phức tạp cũng như thí nghiệm thực tế cho thay giải thuật ngẫu nhiên có thời gian chạy tốt hơn giải thuật cổ điến trên cùng một tập dừ liệu đầu vào.