素性检查器

素数检查器会告诉您一个整数是否是素数，并且与大多数在线计算器不同的是，它会向您显示证明它的实际算法，而不是缓存的查找表。输入任何整数，无论​​是正数还是负数，无论是小还是大，该工具都会根据其大小决定运行哪种实际算法。

对于 10^2（一万亿）以下的数字，它会运行真正的试除法：从 2 开始，它会尝试将 √n 的下限以内的每个整数候选作为可能的除数，在被整除的那一刻停止（合数），或者在检查了直到 √n 的每个候选（素数）后确认没有一个除法。对于大量候选者计数，显示的跟踪上限为第一个尝试的约 18 个加上最后一个，并诚实地说明显示中跳过了多少个候选者 - 但实际上每个候选者仍然由代码检查，在计算中没有跳过。

对于等于或高于该阈值（密码学中使用的大小范围）的数字，试除会花费太长时间，因此该工具切换到米勒-拉宾素性测试，使用一组固定的、确定性的 13 个主要见证人（2、3、5、7、11、13、17、19、23、29、31、37、41）。这个确切的见证集是一个众所周知的结果：对于任何低于 3,317,044,064,679,887,385,961,981（约 3.3×10²⁴）的 n 都没有误报，这是通过计算验证建立的界限（参见 Sorenson & Webster，2015，以及它所属的广泛复制的确定性见证表）。高于该界限，相同的测试仍然运行，但该工具诚实地告诉您，保证变成了极强的概率性保证，而不是数学确定性。

Miller–Rabin 迹线将 n − 1 = 2ˢ × d 写为 d 奇数，然后遍历真正的 BigInt 模幂（平方乘法），在每一步减少模 n，这样数字就不会爆炸（对于第一个见证人来说，一点一点地报告），并报告每个见证人的结论，包括如果数字不是质数，则由哪个见证人证明复合性。一切都在您的浏览器本地运行：没有服务器，没有外部 API，没有数据离开您的设备。