如何高效计算大数x次平方后的素数模结果？（JS/Python）

核心思路是利用费马小定理简化指数计算，避免直接处理超大的2^x指数：

• 因为m是素数，对于与m互质的n，有n^k ≡ n^(k mod (m-1)) mod m；若n是m的倍数，结果直接为0。
• 我们需要计算的指数是2^x，可以先对m-1取模（记为exp），再用快速幂计算n^exp mod m即可。当exp为0时，由于n与m互质，n^0=1，结果为1。

步骤分解 #

1. 特殊情况处理：若n % m === 0，直接返回0。
2. 计算phi = m - 1（素数的欧拉函数值）。
3. 用快速幂计算exp = 2^x mod phi，避免生成2^x的超大值。
4. 若exp === 0，返回1 % m（等价于指数是phi的倍数，根据费马小定理结果为1）。
5. 用快速幂计算n^exp mod m，得到最终结果。

JavaScript 实现 #

function modularSquareRepeat(n, x, m) {
    if (n % m === 0) return 0;
    const phi = m - 1;
    // 计算2^x mod phi
    let exp = 1;
    let base = 2;
    let power = x;
    while (power > 0) {
        if (power % 2 === 1) {
            exp = (exp * base) % phi;
        }
        base = (base * base) % phi;
        power = Math.floor(power / 2);
    }
    if (exp === 0) return 1 % m;
    // 计算n^exp mod m
    let result = 1;
    base = n % m;
    power = exp;
    while (power > 0) {
        if (power % 2 === 1) {
            result = (result * base) % m;
        }
        base = (base * base) % m;
        power = Math.floor(power / 2);
    }
    return result;
}

// 测试示例：n=5, x=3, m=7，预期输出4
console.log(modularSquareRepeat(5, 3, 7)); // 4
// 测试超大x：x=10^12，m=7
console.log(modularSquareRepeat(5, 10**12, 7));

Python 实现 #

Python内置pow函数支持三参数快速幂，代码更简洁：

def modular_square_repeat(n, x, m):
    if n % m == 0:
        return 0
    phi = m - 1
    exp = pow(2, x, phi)
    if exp == 0:
        return 1 % m
    return pow(n, exp, m)

// 测试示例：n=5, x=3, m=7，预期输出4
print(modular_square_repeat(5, 3, 7))  # 4
// 测试超大x：x=10**12，m=7
print(modular_square_repeat(5, 10**12, 7))

原理验证 #

以示例n=5, x=3, m=7为例：

• phi=6，计算2^3 mod6=8 mod6=2
• 计算5^2 mod7=25 mod7=4，与直接计算结果一致。

当x=1e12时，2^1e12 mod6周期为2，1e12是偶数，故exp=4，计算5^4 mod7=625 mod7=4，结果正确。

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