哪一组证人足以让 Miller-Rabin 检验对 10¹⁸ 以内的所有数字都正确？我知道使用不超过 17 的素数作为见证足以满足 n < 341550071728321。
问问题
370 次
3 回答
2
根据此记录页面，7 个 SPRP 基础的集合：{2, 325, 9375, 28178, 450775, 9780504, 1795265022}至少足以进行确定性测试n = 2^64 ( > 10^19)。
于 2014-03-05T10:56:22.290 回答
0
如果您愿意使用 Baillie-Wagstaff 测试而不是 Miller-Rabin 测试，那么它已被证明在对高达 2^64 的素数进行分类时没有错误。编码并不复杂，函数执行比 Miller-Rabin 测试更快，并且没有已知的分类错误。
于 2014-03-05T13:33:53.163 回答
0
根据OEIS，使用最多 23 个见证人就足够了 3825123056546413051 的数字
于 2014-03-05T10:00:02.690 回答