biginteger.isprobableprime(int certainty) 是概率性素数判定,错误率≤0.5^certainty;返回false必为合数,true则可能为合数;certainty=100时误判率≤0.5^100,适用于rsa密钥生成。

直接说结论: BigInteger.isProbablePrime(int certainty) 不是确定性质数判定,而是基于 Miller-Rabin(对奇合数)和 Lucas-Lehmer 类变种(Java 8+ 对某些偶数/小数补充)的随机化测试;certainty 参数不是“准确率百分比”,而是错误概率上限 —— 错判合数为质数的概率 ≤ 0.5certainty。想快速筛掉明显合数,用 certainty = 10 就够;生产环境验大素数(如 RSA 密钥生成),至少用 certainty = 100。
为什么 isProbablePrime() 会返回 false 正常但让人困惑
常见误解是“返回 false 就说明一定是合数”,其实不然:它只保证「若返回 false,则输入必为合数」;但返回 true 时,仍可能为合数(只是概率极低)。这个单向确定性容易被忽略。
- 输入是偶数且 > 2 → 必然返回
false(不走随机测试) - 输入是
1、0、负数 → 直接返回false(1不是质数,Java 严格遵循数学定义) - 输入是
2→ 立即返回true(硬编码特例) - 输入是小奇数(如
3,5,7)→ 可能跳过随机测试,用查表或试除法快速判定
certainty 参数怎么选:速度 vs 误判风险
这个参数控制 Miller-Rabin 的轮数(大致等价),每轮独立随机选取底数 a;增大它会让执行时间线性增长(不是指数),但误判率呈指数下降。
-
certainty = 0→ 至少做 1 轮,误判率 ≤ 0.5 —— 完全不可靠,仅用于调试 -
certainty = 10→ 误判率 ≤ 1/1024 ≈ 0.001,适合预筛选(比如从 10⁵⁰ 范围里快速捞出候选) -
certainty = 20→ 误判率 ≤ 1e-6,常见工具类可接受 -
certainty = 100→ 误判率
注意:certainty 为负数时,行为未定义(OpenJDK 实现会抛 IllegalArgumentException)。
实际使用时必须配合的检查
单独调用 isProbablePrime() 很容易漏掉边界或语义陷阱。真实代码中应前置校验:
- 先确认
BigInteger非 null(否则 NPE) - 用
compareTo(BigInteger.ONE) 排除 ≤ 1 的数(它们都不是质数) - 如果业务需要「确定性结果」,不能只依赖此方法;对 ≤ 10⁶ 的数,可补试除法;对更大数,需用 AKS 或 ECPP(但 Java 标准库不提供)
- 并发场景下无状态,可安全复用同一
BigInteger实例多次调用
示例片段:
BigInteger n = new BigInteger("...");
if (n == null || n.compareTo(BigInteger.ONE)
<p>真正难的不是调用这行代码,而是理解「probable」在这里是严格的概率上界定义,不是模糊的日常用语;而且 Java 不保证不同版本底层使用的素性测试组合完全一致(尤其小数值优化路径),所以跨 JDK 版本做一致性断言要小心。</p>Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南











