Calculating (a^b)%MOD

Question

I want to code for calculating the value of pow(a,b)%MOD. I use C++ to code.

But the problem is the value of b can be very large. I know the log(b) time complexity method. But, the value of b might not fit in the data type "long long" of C++. For example b can be 1000000000 th Fibonacci number. Exact calculation of such a big number is itself, not possible (in time limits).

P.S. :

• pow(a,b) means a*a*a*a*... b times.
• X % MOD means the remainder obtained on dividing X by MOD.

Solution 1

That's a typical task. Please (or, really, PLEASE!) read about the Euler's totient function.

And then the Euler's theorem.

The thing is you can dramatically reduce a^b to a^(b % phi(MOD)). Yes, you will need some kind of an integer factorization method, but still, no crazy ideas about actually calculating the power needed.

We did such samples by hand in my youth :) Even when the numbers where far beyond 32/64 bit range.

EDIT: Well, you live and learn. In 2008 the result is obtained:

"The totient is the discrete Fourier transform of the gcd: (Schramm (2008))"

So to calculate phi(b) one does not need to know its factors.

EDIT(2):

And the Carmichael's function is what you need to calculate to get the correct answer for any a, b and MOD.

Solution 2

I use this function to solve this problem

UVA 374 - Big Mod

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=310

// a^b % T

// with Exponentiation by squaring (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method)

// if a very large use
// R=(unsigned long long)(R*a)%T;

int restOfPot(long long a,int b,int T)
{
    a%=T;
    long long R=1;

    while(b)
    {
        if(b&1) R=(R*a)%T;
        a=(a*a)%T;
        b>>=1;
    }

    return int(R);
}

Solution 3

For dealing with very large numbers, take a look at boost's Multiprecision library. It has a powm() function that works for this purpose well.

From Generic Integer Operations ：

template <class Integer>
Integer powm(const Integer& b, const Integer& p, const Integer& m);

Returns b^p % m.

Example:

#include <boost/multiprecision/cpp_int.hpp>

boost::multiprecision::cpp_int pow("8912627233012800753578052027888001981");
boost::multiprecision::cpp_int mod("0x86f71688cdd2612c117d1f54bdae029");
boost::multiprecision::cpp_int base(12345);

boost::multiprecision::cpp_int result = powm(base, pow, mod);

std::cout << "result is: " << result << std::endl;

prints:

result is: 5758534182572671080415167723795472693

Comments

[Viktor Latypov]

Guys, when it comes to number theoretical tasks, brute-force approaches are, to say the least, not the best way to solve the problem. A little NumberTheory 101 and you know about classical Euler's theorem. My answer has the appropriate link. I believe MOD is a usual integer which fits in a CPU's register and this makes the task a simple exercise in modular arithmetics.

[phuclv]

possible duplicate of Calculating pow(a,b) mod n

[Viktor Latypov]

It's a number-theoretic question, really. No need to brute-force here. The whole point of the task is to show the superiority of some simple classic theorems. See my answer.

[Gurpreet Singh]

Thanks Viktor. I got what was desired. Thanks for the help... :-) BTW, I knew about the totient function, but not about that Euler's theorem...

[Mario]

Interesting, guess you just stole my weekend's spare time, going to read up on that. :)

[Viktor Latypov]

This book is nice: books.google.ru/books/about/Number_Theory.html?id=njgVUjjO-E‌​AC Also the Ivan Vinogradov's books are good. The Jean-Pierre Serre's "Course d'arithmetique" opens even more possibilities.

[Mark Dickinson]

"So to calculate phi(b) one does not need to know its factors." This hardly looks like a practical method for computing phi(b), though.

[Viktor Latypov]

@MarkDickinson: Yes, that's why I added the remark about Schramm's paper. There's only a single discrete Fourier transform involved.

[Mark Dickinson]

Sorry; that's what I meant: computing via the Fourier transform isn't going to be any more efficient than computing via factoring. (BTW, I believe the result on wikipedia attributed to Schramm is actually much much older.)

[Viktor Latypov]

I also believe that Schramm's result might have been known for a long time. The thing with Fourier... Yes, I see the weakness of my answer. Not a number theorist, unfortunately.

[chux - Reinstate Monica]

Minor: Fails corner case: restOfPot(a,0, 1), Fix-able with long long R=1%T;

[Liju Thomas]

Can you summarize what you have done along with the solution?