Finding nCk that can have huge values of n and k

Question

Firstly this is not my homework ..I am stuck on a question during my practice.

I want to compute the value of this expression: ans=(2^huge)%p..

where:

huge=n1Ck1+ n2Ck2 +n3Ck3 ..... [n1,n2.. can be as large as 10^4 and k1,k2.. are less than 10]

p=a prime number less than 2^32

I know how to find out (a^b)%p using fast right to left binary method , but my problem is how to find the combination [nCk] of a numbers like 10000C9 that can result in such a huge number and then later use that in the modular exponentiation method ??

possible duplicate of [Fast n choose k mod p for large n?](http://stackoverflow.com/questions/10118137/fast-n-choose-k-mod-p-for-large-n) — Daniel Fischer, Aug 01 '12 at 21:29
But can I then use the remainder value (suppose r) in (2^r)%p??Will it be correct?? — Wayne Rooney, Aug 01 '12 at 21:46
Do you want to calculate `x ^ C(n,k) % p` for some `x`? In that case, you don't need `C(n,k) % p` but `C(n,k) % (p-1)`. — Daniel Fischer, Aug 01 '12 at 21:49

score 4 · Accepted Answer · answered Aug 01 '12 at 21:53

4

Because 2^(p-1)==1 mod p, you can do all the calculations of the exponents modulo p-1.

answered Aug 01 '12 at 21:53

Keith Randall

22,985
2
35
54

In the case p == 2 then a is either 0 or 1 mod 2. If a = 0 then the answer is 0. If a = 1 then we only need to know if huge = 0. – mcdowella Aug 02 '12 at 03:59

Finding nCk that can have huge values of n and k

1 Answers1