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.

Answer 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.