素数判定器(Miller-Rabin)

数字输入

示例数字:

检测结果

输入数字后点击"开始检测"

Miller-Rabin 算法说明:

算法原理: Miller-Rabin 是一种概率性素数判定算法,基于费马小定理的推广。对于奇数 n,将 n-1 写成 2^r × d 的形式,然后测试是否满足:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
测试轮数与准确性:
  • 概率性测试:随机选择底数 a,每轮测试将错误率降低到 1/4
  • k 轮测试:理论错误率 ≤ (1/4)^k,实际远低于此
  • 确定性测试:对于 n < 3,317,044,064,679,887,385,961,981,使用特定底数集合 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 可得到 100% 准确结果
特殊情况:
  • 小素数:2, 3, 5, 7 等直接判定
  • 偶数:除 2 外均为合数
  • Carmichael 数:能通过费马测试但实际是合数的数字(如 561),Miller-Rabin 可以正确识别

应用场景:

  • 密码学:RSA 密钥生成时需要快速判定大素数
  • 数论研究:梅森素数、双素数、孪生素数等的搜索
  • 竞赛编程:快速判定素数,时间复杂度 O(k log³n)
  • 随机数生成:生成符合特定条件的大素数