Lua实现Miller-Rabin素性检测一致性问题求助

架构老林

2026-5-29

调试你的Lua版Miller-Rabin素性检测

我帮你梳理几个关键的调试方向，应该能解决你遇到的半数判定错误问题：

循环次数不符合算法逻辑：在isNotWitness函数里，你的循环是for _=0, exponent do，这多执行了一次平方操作。按照Miller-Rabin的标准流程，我们已经计算出witness = (possibleWitness^remainder)%n，接下来只需要平方exponent-1次来检查是否出现n-1。多余的平方会导致原本是素数的数被误判为合数。修正方法是把循环改为for _=1, exponent-1 do（确保总共执行exponent-1次平方）。
随机数种子重复初始化：你在isProbablyPrime的循环里每次都调用math.randomseed(os.time())，但os.time()返回的是秒级时间戳。如果循环在1秒内完成（比如accuracy设为30时很容易发生），每次生成的随机数都会完全相同，相当于只做了一次检测，直接拉低了算法的准确性。应该把math.randomseed(os.time())移到程序最开头，或者isProbablyPrime函数的外层，只初始化一次。
全局变量污染问题：代码里很多变量（比如exponent、remainder、witness）没有用local声明，会变成全局变量。多次调用函数时，这些变量可能被意外覆盖，导致不可预测的结果。比如decompose函数里的exponent, remainder要改成local exponent, remainder，isNotWitness里的witness也要加上local修饰。
大数幂运算的精度问题：Lua的number是双精度浮点数，当测试的n超过2^53时，直接用^计算大数幂会丢失精度，导致后续取模结果错误。你需要实现一个快速幂取模函数，每一步运算都取模，避免大数溢出。比如：

local function pow_mod(base, exp, mod)
    local result = 1
    base = base % mod
    while exp > 0 do
        if exp % 2 == 1 then
            result = (result * base) % mod
        end
        exp = exp // 2
        base = (base * base) % mod
    end
    return result
end

然后把代码里的(possibleWitness^remainder)%n替换成pow_mod(possibleWitness, remainder, n)，(witness^2)%n替换成pow_mod(witness, 2, n)。

你可以先从循环次数和随机数种子这两个点入手调试，这两个是最容易导致半数判定错误的核心原因。

内容的提问来源于stack exchange，提问作者uninformed