Find (a^b)%m where 'a' is very large - GeeksforGeeks

Find (a^b)%m where 'a' is very large - GeeksforGeeks
Given three numbers a, b and m where 1<=b,m<=10^6 and 'a' may be very large and contains upto 10^6 digits. The task is to find (a^b)%m.

This problem is basically based on modular arithmetic. We can write (a^b) % m as (a%m) * (a%m) * (a%m) * … (a%m), b times. Below is a algorithm to solve this problem :

• Since ‘a’ is very large so read ‘a’ as string.
• Now we try to reduce ‘a’. We take modulo of ‘a’ by m once (See this article) i.e; ans = a % m , in this way now ans=a%m lies between integer range 1 to 10^6 i.e; 1 <= a%m <= 10^6.
• Now multiply ans by b-1 times and simultaneously take mod of intermediate multiplication result with m because intermediate multiplication of ans may exceed range of integer and it will produce wrong answer.

unsigned int aModM(string s, unsigned int mod)

{

    unsigned int number = 0;

    for (unsigned int i = 0; i < s.length(); i++)

    {

        // (s[i]-'0') gives the digit value and form

        // the number

        number = (number*10 + (s[i] - '0'));

        number %= mod;

    }

    return number;

}

 

// Returns find (a^b) % m

unsigned int ApowBmodM(string &a, unsigned int b,

                                  unsigned int m)

{

    // Find a%m

    unsigned int ans = aModM(a, m);

    unsigned int mul = ans;

 

    // now multiply ans by b-1 times and take

    // mod with m

    for (unsigned int i=1; i<b; i++)

        ans = (ans*mul) % m;

 

    return ans;

}

Read full article from Find (a^b)%m where 'a' is very large - GeeksforGeeks