Java大数场景下模运算符正确用法及求指数问题修复

使用示例小数值（exampleA、exampleB、exampleP）时能正确得到目标指数，但传入长整型的A、B、p时无法得到正确结果，代码逻辑为遍历指数i从0到p-1，计算g^i mod p，当结果等于目标值时返回对应的i。

错误原因分析 #

• 类型溢出：原powMod方法用int存储底数、结果，当计算g*g时，大p（如3267000013）场景下中间结果会超出int最大值（2^31-1），强制转换导致数值失真。
• 循环范围不足：i和a使用int类型，而p-1（3267000012）远大于int上限，循环无法完整遍历到目标范围。
• 硬编码测试值：循环内固定使用exampleP而非传入的目标p，导致长整型测试时实际计算的是对exampleP取模，而非目标p。
• 类型不匹配：计算结果newNum是int类型，与long类型的目标值A、B直接对比，会因类型转换错误导致匹配失败。

修复后的代码 #

public static void main(String[] args) {
    long g = 5;
    // 目标长整型数值
    long A = 1958258942L;
    long B = 670001116L;
    long p = 3267000013L;
    // 示例测试数值
    long exampleP = 23;
    long exampleA = 4; // 预期返回4
    long exampleB = 10; // 预期返回3

    // 测试示例值
    long aForExampleB = findDiscreteLog(g, exampleB, exampleP);
    System.out.println("示例B对应的指数: " + aForExampleB);

    // 测试长整型值
    long aForA = findDiscreteLog(g, A, p);
    long aForB = findDiscreteLog(g, B, p);
    System.out.println("A对应的指数: " + aForA);
    System.out.println("B对应的指数: " + aForB);
}

// 查找离散对数：找到最小的i，使得 g^i mod p == target
public static long findDiscreteLog(long g, long target, long p) {
    for (long i = 0; i < p - 1; i++) {
        long result = powMod(g, i, p);
        if (result == target) {
            return i;
        }
    }
    // 未找到时返回-1（可根据需求调整）
    return -1;
}

// 改进的模幂运算，使用long避免溢出
public static long powMod(long g, long exponent, long p) {
    long result = 1;
    // 先对底数取模，减少计算量
    g = g % p;
    while (exponent > 0) {
        // 指数为奇数时，将当前底数乘入结果
        if (exponent % 2 == 1) {
            result = (result * g) % p;
        }
        // 指数折半
        exponent = exponent / 2;
        // 底数平方后取模
        g = (g * g) % p;
    }
    return result;
}

修复说明 #

• 所有参与模幂运算的变量改为long类型，彻底避免中间计算溢出。
• 提取findDiscreteLog方法，复用逻辑，消除硬编码测试值的问题。
• 循环变量i改为long，确保能覆盖p-1的超大范围。
• 模幂运算前先对底数取模，优化计算效率并减少大数值操作。
• 使用long类型结果直接与目标值对比，避免类型转换错误。

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