How to calculate x^y mod z?

Question

I am wondering how to calculate x^y mod z. x and y are very large (can't fit in 64 bit integer) and z will fit 64 bit integer. And one thing don't give answers like x^y mod z is same as (x mod z)^y mod z.

Answer 1

Here is the standard method, in pseudo-code:

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
            e := e - 1
        else
            b := (b * b) % m
            e := e / 2
    return x

The algorithm is known as exponentiation by squaring or the square and multiply method.

Answer 2

If you are using Java, then turn x, y, and z into BigInteger.

BigInteger xBI = new BigInteger(x);
BigInteger yBI = new BigInteger(y);
BigInteger zBI = new BigInteger(z);
BigInteger answer = xBI.modPow(yBI,zBI);