ashishranjan2828's blog

modular arithmetic
By ashishranjan2828, history, 8 years ago, In English

how to calculate a^b%mod where b is very much larger than mod

can we do b = b%mod???

e.g. mod = 1000000007

a = 2 b = 1134903170 after this can we do b = 1134903170%mod

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

You can do b = b % phi(mod)

(euler totient function)

→ Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Well, first of all, for your example you can always just do fast exponentiation, in O(log b) multiplications. If b is even, then ab = (ab / 2)2, otherwise ab = ab - 1·a. Though I never implement it recursively, but iteratively (C++):

int pot(int a, int b){
  int r = 1;
  while (b){
    if (b%2) r = mul(r, a);
    a = mul(a, a);
    b /= 2;
  }
  return r;
}

The modding is covered in the mul function.

But to answer your question, yes you can reduce b. If b is greater than φ(mod), then you can reduce b to b%φ(mod) + φ(mod). If you knew that a is relatively prime to mod then you wouldn't need the  + φ(mod), but in the general case it wouldn't work without  + φ(mod) (for example, a = 2, mod = 220, b = φ(mod) = 219, the solution is 0). φ(x) is the Euler totient function.

→ Reply