calculating modulo of a^n faster than o(n)

Question

I need to calculate (a^n) mod b. I used this java code but it's not fast enough when n is too large.

for (long i = 0; i < n; i++) {
    ans = (ans * a) % b;
}

As you can see in above code, n is a long number so this algorithm is not fast enough. Do you suggest any faster algorithm? It may seems like this problem but a little different: Fast way to calculate n! mod m where m is prime?

score 7 · Accepted Answer · edited Jan 04 '19 at 20:08

Take advantage of property of modular arithmetic

(x × y) modulo b == ((x modulo b) × (y modulo b)) modulo b

By using above multiplication rule

(a^n) modulo b
= (a × a × a × a ... × a) modulo b 
= ((a modulo b) × (a modulo b) × (a modulo b) ... × (a modulo b)) modulo b

Calculate the result by divide and conquer approach. The recurrence relation will be:

f(x, n) = 0                     if n == 0

f(x, n) = (f(x, n / 2))^2       if n is even
f(x, n) = (f(x, n / 2))^2 * x   if n is odd

Here is the C++ implementation:

int powerUtil(int base, int exp, int mod) {
    if(exp == 0) return 1;
    int ret = powerUtil(base, exp / 2, mod) % mod;
    ret = 1LL * ret * ret % mod;
    if(exp & 1) {
        ret = 1LL * ret * base % mod;
    }
    return ret;
}

double power(int base, int exp, int mod) {
    if(exp < 0) {
        if(base == 0) return DBL_MAX; // undefined
        return 1 / (double) powerUtil(base, -exp, mod);
    }
    return powerUtil(base, exp, mod);
}

Time complexity is O(logn).

Here is my original answer. Hope it helps!

As the result is `mod` and you want the precision, I would use `long` (or `long long`) rather than `double` — Peter Lawrey, Dec 27 '18 at 17:08

score -4 · Answer 2 · answered Dec 27 '18 at 16:58

You can use threads in order to divide the n. Then when you finalize to mul, you can mul the final result and then make the mod.

For example:

n=4 then separate for 2 threads and each thread will the following:

int ans=1;
for(int i =0; i<n_thread;i++){
   ans = ans*a;
}

Finally, when the threads finish you have to mul the result and then make the mod of b. I will not tell you how to use threads because you have to learn in your own, but if you have doubts about threads after searching and learning about them, then you can ask for help.

calculating modulo of a^n faster than o(n)

2 Answers2