Go math/big.Int.ProbablyPrime 怎样做素性概率判断

处理超出 int64 范围的大整数时，Go 标准库可以直接用 math/big.Int.ProbablyPrime 做素性概率判断。它返回 true 时表示“很可能是素数”，不是对所有输入都给出绝对证明；返回 false 时则表示该数不是素数。官方地址：https://pkg.go.dev/math/big#Int.ProbablyPrime

这一区别决定了 rounds 不能随便写成一个“越大越安全”的常数。正确做法是先弄清输入来源，再结合数值范围解释结果。

先把 true 和 false 的含义说清楚

ProbablyPrime 接收一个 int 参数 n，内部会结合 Miller-Rabin 测试和 Baillie-PSW 测试。对真正的素数，它会返回 true；对随机选择的合数，返回 true 的概率上界是 1/4^n。因此，方法名中的 “Probably” 是 API 语义的一部分。

下面的例子把解析失败与素性判断分开处理，避免把空指针或错误字符串误认为“不是素数”。代码注释只保留关键的输入、参数和返回语义：

package main

import (
    "fmt"
    "math/big"
)

func main() {
    // SetString 返回第二个布尔值，先确认输入确实能解析成大整数。
    n, ok := new(big.Int).SetString("170141183460469231731687303715884105727", 10)
    if !ok {
        fmt.Println("输入不是合法的十进制整数")
        return
    }

    // 20 表示 Miller-Rabin 的轮数；true 代表可能为素数，而不是错误值。
    const rounds = 20
    fmt.Printf("n=%s, probablyPrime=%t\n", n.String(), n.ProbablyPrime(rounds))
}

这里的 20 是一个常见的工程起点，但它不是“所有输入都必须使用”的协议值。文章后面的边界条件比这个数字本身更重要。

rounds 怎么选，概率上界怎么看

对于随机选择的合数，文档给出的误判上界是 1/4^n。增加一轮会把这个上界再缩小四倍，所以 rounds 体现的是你愿意为概率误判付出多少计算成本。它不是把一个未知输入变成数学意义上的绝对证明。

可以把参数选择写成一个与业务边界绑定的常量，而不是散落在调用处：

package primecheck

import "math/big"

// IsProbablyPrime 面向随机来源的大整数，固定统一的测试轮数。
func IsProbablyPrime(decimal string) (bool, bool) {
    // 解析失败时第二个返回值为 false，调用方不应继续使用 nil 的整数。
    n, ok := new(big.Int).SetString(decimal, 10)
    if !ok {
        return false, false
    }

    // 20 只表示测试强度；第一个返回值仍然是概率判断。
    return n.ProbablyPrime(20), true
}

这个包装函数用两个布尔值区分“输入可解析”和“可能为素数”：第一个值是素性判断，第二个值是输入状态。真实项目中也可以把输入错误改成 error，但不要把解析失败与合数混成同一条分支。

小于 2⁶⁴ 时，为什么可以当作确定结果

当前文档明确说明：对小于 2^64 的输入，ProbablyPrime 是 100% 准确的。这是数值范围带来的确定性边界，不是因为把 rounds 写得足够大。因此，处理 64 位以内的候选数时，true 可以按确定的素数结果使用；超过这个范围后，仍应回到概率语义。

如果业务要显式记录边界，可以先比较位长。下面的判断只负责标注范围，不改变 ProbablyPrime 的行为：

func classify(n *big.Int) string {
    // BitLen 是非负绝对值的位数；这里只把小于 2^64 的输入标成确定范围。
    if n.Sign() >= 0 && n.BitLen() 

严格按文档边界写业务条件时要注意“小于 2^64”而不是把所有 64 位无符号最大值都无条件归入同一表述。若需要覆盖边界值，应直接以 Cmp 与 2^64 的大整数常量比较，避免机器整数溢出。

哪些输入不能把 true 当作最终证明

文档还特别提醒：ProbablyPrime 不适合判断“可能由对手专门构造来欺骗测试”的素数候选。也就是说，rounds 的概率上界建立在随机输入假设上；当输入来自不可信请求、对抗性数据或需要密码学保证的流程时，不能只凭返回的 true 放行。

如果目标是生成密码学用途的素数，应该使用 crypto/rand.Prime 这类面向密码学随机源的 API；如果只是对随机生成或离线计算得到的普通大整数做筛选，ProbablyPrime 的概率语义通常更贴合任务。两者的职责不要混用。

常见问题

ProbablyPrime(0) 能不能调用？

可以。当前文档说明从 Go 1.8 起 ProbablyPrime(0) 被允许，此时只应用 Baillie-PSW 测试。它不等同于“关闭检查”，也不等同于对任意超大输入给出绝对证明。

返回 false 是否也只是概率结论？

工程解释上，返回 false 可以视为该值不是素数；需要重点保留概率语义的是返回 true 的路径，尤其是输入超过 2^64 或输入可能被对手构造时。

小结

• 先用 SetString 检查大整数输入，再调用 ProbablyPrime(rounds)。
• rounds 控制随机合数误判上界，文档给出的上界是 1/4^rounds。
• 小于 2^64 的输入是 100% 准确边界；对可能被对手构造的输入，不要把 true 当作密码学证明。