Originally Posted by

**lali** Hi

I am looking for an efficient way to calculate ((a+b)!/a!b!) mod p. p is prime.

...

So how would i programmatically calculate the value, since intermediary calculations might overflow an int variable.

Since (a/b)mod p != ((a%p)/(b%p)) mod p. Right ?

Is there a trick involved ?

There is no "trick", you just need to be systematic.

You can reduce the magnitude of the numbers by taking the residue of the number mod your prime value.

If you are going to write a program to arrive at a solution, then getting the answer appears to be more important than efficiency.

However, if you are doing this by chalk & chalkboard, efficiency is extremely critical.

My theory is that computer time is cheaper than my time.

It's a theory because my teachers say my time is worth nothing.

This may not be efficient but it should be easy to understand:

suppose:

Code:

a=57
p=3711
'function Factorial_Mod_p(a,p)
r=1 ''<-- the residue of a number mod p
for i = 2 to a 'you already have 1 as the first residue
r = (r * i) mod p
next i
return (r)

code the function

then call it three times:

Code:

' ((a+b)!/a!b!) mod p
'supply the real values for a, b, & p
numerator = Factorial_Mod_p( a+b, P )
denominator_a = Factorial_Mod_p( a, p )
denominator_b = Factorial_Mod_p( b, p )

Since a division is involved you will need to calculate the modular inverse of

(denominator_a * denominator_b ) mod p

All of the intermediate values will not exceed p*p