Java循环处理短数值正常，长数值陷入死循环的问题排查

我写了一个求解离散对数的程序，用示例数值（exampleA、exampleB、exampleP）测试时能返回预期结果，但传入大数值（A、B、p）时循环会一直运行。我认为传入B和p应该返回2099，请问问题出在哪里？

public static void main(String[] args) {
        //g = 5//
        //let i run from 0 to p -1//
        //compute g^a mod p and see if it is A, if you find A, then a is the solution for A//
        //compute g^a mod p and see if it is B, if you find B, then a is the solution for B//
        long A = 1958258942L;
        long B = 670001116L;
        long p = 3267000013L;
        //example p to plug in for example a and example b//
        long exampleP = 23;
        //plugging this in should return 4//
        long exampleA = 4;
        //plugging this in should return 3//
        long exampleB = 10;
        int newNum;
        int a = 0;
        int g = 5;
        for (int i = 0; i < (p - 1); i++) {
                a = i;
                System.out.println(a);
                newNum = powMod(g, a, exampleP);
                if (newNum == exampleB) break;
            }
        System.out.println(a);
    }
    
    public static int powMod(int g, int exponent, long p) {
        int result = 1;

        while (exponent > 0)
        {
            // exponent is odd
            if (exponent % 2 == 1)
            {
                result = (int) ((result * g) % p);
            }

            // divide exponent in half
            exponent /= 2;

            // square base and take remainder 
            g = (int) ((g * g) % p);
        }
        return result;
    }

核心问题总结 #

1. 循环变量溢出导致无限循环
   p的值是3267000013，p-1等于3267000012，而int类型的最大值是2147483647，远小于这个数。循环变量i是int类型，当i增长到2147483647后，再自增就会溢出变成负数，此时i < (p-1)的条件永远成立，循环无限运行。

2. 测试变量未切换
   代码里的循环依然在使用exampleP和exampleB进行判断，没有切换到目标测试的p和B，即使循环正常结束，也不会匹配到目标值。

3. 数值溢出导致计算错误
   powMod方法里的g、result都是int类型，当计算g*g或者result*g时，结果可能超过int的范围，导致溢出，最终返回的模运算结果错误，无法匹配B的值，即使循环到正确的指数2099，也不会触发break。

修复方案 #

1. 修改循环变量类型为long
   把i的类型从int改成long，避免溢出，确保循环能正常遍历到p-1。

2. 切换到目标测试变量
   将powMod(g, a, exampleP)改为powMod(g, a, p)，判断条件newNum == exampleB改为newNum == B，让程序测试目标数值。

3. 修改powMod方法的数值类型
   把g、result的类型改为long，避免计算过程中的溢出问题，保证模运算结果正确。

修复后的代码 #

public static void main(String[] args) {
        long A = 1958258942L;
        long B = 670001116L;
        long p = 3267000013L;
        long exampleP = 23;
        long exampleA = 4;
        long exampleB = 10;
        long newNum;
        long a = 0;
        long g = 5;
        // 循环变量改为long类型
        for (long i = 0; i < (p - 1); i++) {
                a = i;
                // 切换到目标p和B
                newNum = powMod(g, i, p);
                if (newNum == B) break;
            }
        System.out.println(a);
    }
    
    // 修改参数和返回值类型为long
    public static long powMod(long g, long exponent, long p) {
        long result = 1;

        while (exponent > 0)
        {
            if (exponent % 2 == 1)
            {
                result = (result * g) % p;
            }

            exponent /= 2;
            g = (g * g) % p;
        }
        return result;
    }

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