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;
}
}