Fast exponentiation modulo method

Viewed 21

I wrote a method for fast exponentiation modulo, but it does not work correctly on the example: 5 ^ 20 mod 7. What is the error? Outputs answer 3 instead of 4

public class cryptoLab1 {
    //y = a^x mod p
    public static BigInteger Mod(BigInteger a, int x, int p) throws Exception {
        if(x == 0) {
            return BigInteger.valueOf(1);
        }
        if(p == 0) {
            throw new Exception("P cannot be 0");
        }

        var t = Integer.toString(x, 2);
        var result = BigInteger.valueOf(1);
        var s = a;

        for (int i = 0; i <= t.length() - 1; i++) {
            if(t.charAt(i) == '1') {
                result = (result.multiply(s)).mod(BigInteger.valueOf(p));
            }
            s = (s.multiply(s)).mod(BigInteger.valueOf(p));
        }

        return result;
    }
}
1 Answers

It looks like you're interpreting the digits of x backwards (in addition to converting it using a string, which is a little weird). If you're going to convert x to a String, you'll need to iterate through its digits lowest-to-highest-significance order, meaning backwards.

Related