Find (num * (pow(b, p) - 1) / den) % mod where p is very large(10 ^ 18)

Question

I want to find (num * (pow(b, p) - 1) / den) % mod. I know about binary exponentiation. But we can't do it straightforward. It is guaranteed that the numerator is divisible by the denominator. That means

[num * (pow(b, p) - 1)] % den == 0

constraints on mod: are 1 <= mod <= 10 ^ 9 and mod might be prime or composite

constraints on b: 1 <= b <= 10

constraints on p: 1 <= p <= (10^18)

constraints on num: 1 <= num <= (10^9)

constraints on den: 1 <= den <= (10^9)

Here pow(b, p) means b raised to power p(b ^ p). It is guaranteed that the numerator is divisible by the denominator. How can I do it with binary exponentiation

Answer 1

Your expression should rewritten to simplIfy it. First let k=num/den, with k integer according to your question.

So you have to compute
(k×(b^p-1))mod m=( (k mod m) × ((b^p -1) mod m) ) mod m
                           = ( (k mod m) × ( (b^p mod m) -1 mod m ) mod m ) mod m
                           = ((k mod m) × ((b^p mod m) + m-1) mod m) mod m             (1)

So the real problem is to compute b^p mod m

Many languages (python, java, etc) already have a modular exponentiation in their standard libraries. Consult the documentation and use it. Otherwise, here is a C implementation.

unsigned long long modexp(unsigned long long b, unsigned long long e, unsigned long long m) {
  if (m==1) return 0;
  unsigned long long res=1;
  unsigned long long bb = b % m;
  while (e) {
    if (e & 1) 
      res = (res*b) % m;
    e >>= 1;
    bb = (bb*bb) % m;
  }
  return res;
}

The implementation uses long long to fit your constraints. It relies on the classical trick of binary exponentiation. All values of b^l, where l is a power of two (l=2^t) are computed and stored in var bb and if the corresponding t^th bit of e is set, this value of b^l is integrated in the result. Bit testing is done by checking the successive parities of e, while shifting e rightward at each step.

Last, the fact that (a×b)mod m=((a mod m)×(b mod m))mod m is used to avoid computation on very large numbers. We always have res<m and bb<m and hence res and bb are codable on standard integers.

Then you just have to apply (1) to get the final result.

EDIT according to the precisions given in the comments
To compute n=(3^p-1)/2 mod m, one can remark that
(3^p-1)/2 = x*m + n (as 3^p-1 is even, x is an integer, 0≤n<m)
3^p-1=x*2*m+2n (0≤2n<2m)
so 2n=(3^p-1) mod 2m

We can just apply the previous method with a modulo of 2*m, and divide the result (that will be even) by 2.