Trình kiểm tra tính nguyên thủy

Trình kiểm tra tính nguyên tố cho bạn biết liệu một số nguyên có phải là số nguyên tố hay không và — không giống như hầu hết các máy tính trực tuyến — hiển thị cho bạn 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 trong bộ nhớ đệm. Nhập bất kỳ số nguyên nào, dương hoặc âm, nhỏ hay lớn và công cụ sẽ quyết định thuật toán thực nào sẽ chạy 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ỷ), nó chạy phép chia thử thực sự: bắt đầu từ 2, nó thử mọi ứng cử viên số nguyên cho đến tầng √n làm ước số có thể, dừng thời điểm một số chia đều (tổng hợp) hoặc xác nhận không có số nào thực hiện khi mọi ứng cử viên lên đến √n đã được kiểm tra (số nguyên tố). Đối với số lượng ứng cử viên khổng lồ, dấu vết hiển thị được giới hạn ở ~18 lần thử đầu tiên cộng với lần thử cuối cùng, kèm theo ghi chú trung thực về số lượng ứng cử viên bị bỏ qua trong màn hình - nhưng mỗi ứng cử viên thực sự vẫn được kiểm tra bằng mã, không có ứng cử viên nào bị bỏ qua trong quá trình tính toán.

Đối với các số ở hoặc trên ngưỡng đó — phạm vi kích thước được sử dụng trong mật mã — việc phân chia thử nghiệm sẽ mất quá nhiều thời gian, do đó, công cụ sẽ chuyển sang kiểm tra tính nguyên tố Miller–Rabin với một tập hợp xác định, cố định gồm 13 nhân chứng chính (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Tập nhân chứng chính xác này là một kết quả nổi tiếng: nó không có kết quả dương tính giả đối với bất kỳ n nào 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ằng xác minh tính toán (xem Sorenson & Webster, 2015 và bảng nhân chứng xác định được sao chép rộng rãi mà nó thuộc về). Trên giới hạn đó, bài kiểm tra tương tự vẫn chạy, nhưng công cụ này thành thật cho bạn biết rằng sự đảm bảo trở thành một xác suất cực kỳ mạnh mẽ chứ không phải là sự chắc chắn về mặt toán học.

Dấu vết Miller–Rabin viết n − 1 = 2ˢ × d với d lẻ, sau đó thực hiện phép lũy thừa mô-đun BigInt thực — bình phương và nhân, giảm mô-đun n ở mỗi bước để các số không bao giờ bùng nổ — từng chút một cho nhân chứng đầu tiên và báo cáo phán quyết của từng nhân chứng, bao gồm cả nhân chứng nào chứng minh tính tổng hợp nếu số đó không phải là số nguyên tố. Mọi thứ đều chạy cục bộ trong trình duyệt của bạn: không có máy chủ, không có API bên ngoài, không có dữ liệu nào rời khỏi thiết bị của bạn.