Modular Exponentiation

https://en.wikipedia.org/wiki/Modular_exponentiation

Applications is like Public-Key Cryptography

Modular Exponentiation This is from CPH The following function calculates the value of $x^n\mathrm{mod}m$:

int modpow(int x, int n, int m) {
	if (n == 0) return 1%m;
	long long u = modpow(x,n/2,m);
	u = (u*u)%m;
	if (n%2 == 1) u = (u*x)%m;
	return u;
}

There’s also this version from cp-algorithms, iterative

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

Both do binary exponentiation.

Related

• Binary Exponentiation