Trình kiểm tra tính nguyên tố
Kiểm tra xem một số có phải là số nguyên tố hay không và xem chính xác lý do: phép chia thử thực sự đến √n cho các số nhỏ và trung bình, cùng hướng dẫn chi tiết Miller–Rabin chuẩn mực cho các số ở cấp độ mật mã.
🔒 Được xử lý hoàn toàn trong trình duyệt của bạn — không có nội dung nào bạn nhập ở đây được tải lên.
Kết quả
Trình kiểm tra tính nguyên tố cho bạn biết một số nguyên có phải là số nguyên tố hay không, và — khác với hầu hết các máy tính trực tuyến — hiển thị thuật toán thực tế đã chứng minh điều đó, chứ không phải bảng tra cứu được lưu sẵn. Nhập bất kỳ số nguyên nào, dương hay âm, nhỏ hay cực lớn, và công cụ sẽ quyết định chạy thuật toán thực sự nào dựa trên kích thước của nó.
Đối với các số dưới 10¹² (một nghìn tỷ), công cụ chạy phép chia thử thực sự: bắt đầu từ 2, thử lần lượt từng số nguyên ứng viên đến phần nguyên của √n làm ước số khả dĩ, dừng ngay khi một số chia hết (hợp số) hoặc xác nhận không có số nào khi đã kiểm tra hết mọi ứng viên đến √n (nguyên tố). Đối với số lượng ứng viên rất lớn, vết hiển thị sẽ giới hạn ở khoảng 18 ứng viên đầu tiên cộng với ứng viên cuối cùng, kèm theo ghi chú trung thực về số lượng đã bị bỏ qua trong hiển thị — nhưng mọi ứng viên thực tế vẫn được mã kiểm tra, không bỏ sót ứng viên nào trong tính toán.
Đối với các số ở hoặc trên ngưỡng đó — phạm vi kích thước dùng trong mật mã — phép chia thử sẽ mất quá nhiều thời gian, vì vậy công cụ chuyển sang kiểm tra Miller–Rabin với một bộ 13 nhân chứng nguyên tố cố định, tất định (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Bộ nhân chứng chính xác này là một kết quả đã được công nhận rộng rãi: nó không có kết quả dương tính giả nào cho mọi n dưới 3.317.044.064.679.887.385.961.981 (khoảng 3,3×10²⁴), một giới hạn được thiết lập bởi kiểm chứng tính toán (xem Sorenson & Webster, 2015, và bảng nhân chứng tất định được sao chép rộng rãi mà nó thuộc về). Trên giới hạn đó, kiểm tra tương tự vẫn chạy, nhưng công cụ sẽ trung thực cho bạn biết rằng sự đảm bảo trở thành một đảm bảo xác suất cực kỳ mạnh thay vì sự chắc chắn toán học.
Vết Miller–Rabin viết n − 1 = 2ˢ × d với d lẻ, sau đó đi qua phép tính lũy thừa mô-đun BigInt thực sự — bình phương và nhân, rút gọn theo mô-đun n ở mỗi bước để các con số không bao giờ bùng nổ — từng bit cho nhân chứng đầu tiên, và báo cáo phán quyết của mỗi nhân chứng, bao gồm nhân chứng nào chứng minh tính hợp số nếu số đó không phải là nguyên tố. Mọi thứ chạy cục bộ trong trình duyệt của bạn: không máy chủ, không API bên ngoài, không dữ liệu nào rời khỏi thiết bị của bạn.