1

I have two numbers A and B

where A and B can be in the range 1<= A,B <=100^100000

How can we find the value of A^B modulo some M in C++ ??

jaig
  • 107
  • 2
  • 2
  • 6
  • 2
    you need to use an arbitrary precision arithmetic library. Boost and OpenSSL both have implementations. And others are available if you look around. – Mark Hendrickson Nov 17 '13 at 04:43
  • 1
    The only important point here is what are the bounds of M. Can M fit into a 32/64 bit integer? If M is prime there is a trivial solution, just a little more complicated for all the other M. – sbabbi Nov 17 '13 at 05:44
  • Can A and B be written as p^q (p,q integer)? Otherwise you will need arbitrary precision libraries (you might have 200,000 digits...). And the trick I copied in my answer below would not work. – Floris Nov 17 '13 at 14:52

4 Answers4

4

In the duplicate I pointed out, the solution I particularly like is https://stackoverflow.com/a/8972838/1967396 (see there for attribution and references)

For your convenience I reproduce the code here (wrapped into an SCCE - but using C, not C++):

#include <stdio.h>

int modular(int base, unsigned int exp, unsigned int mod)
{
    int x = 1;
    int i;
    int power = base % mod;

    for (i = 0; i < sizeof(int) * 8; i++) {
        int least_sig_bit = 0x00000001 & (exp >> i);
        if (least_sig_bit)
            x = (x * power) % mod;
        power = (power * power) % mod;
    }

    return x;
}

int main(void) {
  printf("123^456mod567 = %d\n", modular(123, 456, 567));
}

Amazing, isn't it.

Community
  • 1
  • 1
Floris
  • 45,857
  • 6
  • 70
  • 122
  • The quantities in this problem are *significantly* larger than the one you copied from. But yes, binary exponentiation makes it a lot faster than the naive method. – Ben Voigt Nov 17 '13 at 05:05
  • @BenVoigt - you are right. 100^100000 is a very very large number. The underlying principle stands, but it needs a bit more thought to get a correct implementation. – Floris Nov 17 '13 at 11:09
2

use the formula (a*b)mod m = (a*(b (mod m))) (mod m). For more details see the wiki page Modular exponentiation

deeiip
  • 3,319
  • 2
  • 22
  • 33
  • Note that OP wants to do `(a^b)mod m`, not `(a*b) mod m`… might be a typo on your part? – Floris Nov 17 '13 at 04:57
  • 1
    No no that will(replacing * with ^) magically decrease complexity (so unpractical!). It is :(a^b) = (a*a*a.....). Now the formula will be used. @Floris – deeiip Nov 17 '13 at 05:02
  • 1
    I understand your point now. You keep applying this formula B times. In fact with `(a (mod m ) * (b mod m) ) mod m` you keep the size if the numbers needed down a lot. And a bit of dynamic programming means you don't do this B times but only O(log(B)). Which is a big deal. – Floris Nov 17 '13 at 14:59
1

Another solution assumes that your M is fixed (or at least that you need to compute A^B many times with the same M).

Step 1: compute the Euler's totient function (this requires a factorization of M, so it's quite expensive). Let's call this number k.

Due to the Fermat's little theorem, your answer is simply:

(a % M)^(b % k)

Now, unless M is a large prime number, this greatly simplify the problem.

sbabbi
  • 11,070
  • 2
  • 29
  • 57
  • +1 This is a very good answer indeed. It specifically tells when you can reduce the power as you require, for eg consider this problem : To find : 3^3^3 mod 1000000007 – Akash Aug 06 '17 at 19:13
  • Can you please provide a link to understand the proof for this result ? – Akash Aug 06 '17 at 19:38
0

The above problem can be solved using the code snippet below. Thus to ensure this code does not overflow, check that n * n <= 2 ^ 31.

int modPow(int base, int exp, int n) {

base = base%n;

if (exp == 0)
    return 1;

else if (exp == 1)
    return base;

else if (exp%2 == 0)
    return modPow(base*base%n, exp/2, n);

else
    return base*modPow(base, exp-1, n)%n;

}

Amit Kumar
  • 1,477
  • 1
  • 16
  • 27
  • 1
    This is not tail recursive, so it surely will cause a stack overflow for the numbers presented in the question (I assume changing from int to some big integer library) – Ben Voigt Nov 17 '13 at 13:21