long mod opertaion returns an int Java

Question

So I am using this modular exponentiation algorithm I saw on Wikipedia somewhere and it has been working fine for me for small numbers. But when I use larger numbers (E.g. 7000000000) it always returns a 0.

public static void main(String[] args) {
    System.out.println(modPow(2L, 7000000000L - 1L, 7000000000L));
}

public static long modPow(long base, long exponent, long modulus) {
    long result = 1L;
    base = base % modulus;
    while(exponent > 0) {
        if(exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        exponent = exponent >> 1;
        System.out.println(result);
        base = (base*base) % modulus;
    }
    return result;
}

I tracked the problem down to the result variable, as the function loops it has the values:

2
8
128
32768
2147483648
-4854775808
0
0
...0s onward

This clearly shows that the result variable is being stored as an int, but I have clearly defined it as a long. I have tried adding (long) to all the calculations in case it was casting it to an int for some reason but that doesn't work.

It is probably something simple or basic that I am missing but I can't see why this isn't working. Any help is greatly appreciated.

Answer 1

Your result * base overflows long.

Add something like the below statement inside your if

System.out.println("result * base = " + result*base);`

and you will see:

result * base = 2
2
result * base = 8
8
result * base = 128
128
result * base = 32768
32768
result * base = 2147483648
2147483648
result * base = -9223372036854775808
-4854775808

Note that Long.MAX_VALUE is 9223372036854775807