Calculating pow(a,nCr) % m efficiently

Question

I think there are some process for calculating pow(a,nCr)%b? But I want to know how I can efficiently solve this problem in programming?

Answer 1

I can think of a way that's only ~O(n^2*log(m)) and doesn't require the use of big integers. I have a notion of a faster (something like O(k*log(m)*log(n))) approach if you can factor m and you can factor totient(m/gcd(a^k,m)) for some k, but it gets pretty hairy.

In any case for the O(n^2*log(m)) approach, we'll make use of the fact that nCr == (n-1)C(r-1) + (n-1)Cr

Here's a computation of nCr which exploits that:

def nCr(n0,r0):
  memoized = {}

  def go(n,r):
    if r == 0 or r == n:
      return 1
    if (n,r) not in memoized:
      memoized[(n,r)] = go(n-1,r-1) + go(n-1,r)
    return memoized[(n,r)]

  return go(n0,r0)

The code for your powChooseMod function would be almost identical:

def powChooseMod(a,n0,r0,m):
  memoized = {}

  def go(n,r):
    if r == 0 or r == n:
      return a
    if (n,r) not in memoized:
      memoized[(n,r)] = go(n-1,r-1) * go(n-1,r) % m
    return memoized[(n,r)]

  return go(n0,r0)