Deterministic Primality Testing for Limited Bit Width
3 days ago
- #Miller-Rabin
- #deterministic-algorithm
- #primality-testing
- 使用确定性的Miller-Rabin素性检验方法，以{2, 3, 5, 7}为基底检验所有32位整数。
- 解释了强伪素数的概念，并说明通过检验多个基底如何降低假阳性风险。
- 提及历史背景：Miller-Rabin检验（1980年代）、Pomerance等人（1980年）的工作，以及SPRP基底竞争。
- 注记性能表现：简单实现能在约2分钟内完成对所有32位数的检验；使用primesieve工具可将时间缩短至60毫秒。
- 提供了32位与64位确定性检验的替代基底选项，并指出有关溢出的注意事项。