CODEWITHSUNDEEP
javamathlong-integer
Duke
Duke

Reputation: 416

computing (a^b)%m in java

While trying to implement the Miller-Rabin primality test I came across a strange behaviour of java. Regard the following code:
long x = (long) (Math.pow(a, b));
For a and b large enough (doesn't need that much) you will always get x = 9223372036854775807 = Long.MAX_VALUE instead of an overflow value.
This result is completely useless and won't help calculating (a^b)%m, which is what we need.
Now since (a^b)%m would easily fit into 64 bits when (a^b) doesn't, I wonder if there is a way to calculate this number without using BigInteger?

Upvotes: 0

Views: 183

Answers (2)

luk2302
luk2302

Reputation: 57124

You can always implement the pow(...) yourself and mod as often as possible. Generally speaking (in pseudo-code):

powMod(a, b, m) {
    result = 1
    for (i = 0; i < b; i++) {
        result = (result * a) % m
    }
    return result
}

If result * a may be too large then you may want to implement * by repeated addition and modding after each +. Furthermore you can (and should) always use a' = a % m and b' = b % m if you don't do that already.

Upvotes: 1

cameron1024
cameron1024

Reputation: 10156

Use BigInteger, in particular the method modPow(). From the javadocs:

public BigInteger modPow(BigInteger exponent, BigInteger m) - Returns a BigInteger whose value is (this^exponent mod m). (Unlike pow, this method permits negative exponents.)

https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#modPow(java.math.BigInteger,%20java.math.BigInteger)

For Example:

BigInteger a = BigInteger.valueOf(2);
BigInteger b = BigInteger.valueOf(3);
BigInteger m = BigInteger.valueOf(7);

BigInteger result = a.modPow(b, m);  // i.e. 2 ^ 3 mod 7 -> 8 mod 7 -> 1
System.out.println(result);  // prints 1

Upvotes: 1

Related Questions