Thread: How to calculate ((a+b)!/a!b!) mod p

Hi

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

for example if a=10 and b=7 and p=3 then we need to find (17!/10!.7!) mod 3
answer =2

The above can be reduced to (17.16.15.14.13.12.11/7.6.5.4.3.2.1) mod 3

The problem i am facing is a and b can have a very high value i.e 1<=a<=1000000000 and 1<=b<=1000000000 and value of p is say 531169.
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 ?

Thanks for your patience
Regards
lali

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

'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]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

Suppose a=10 b =7 and p=3( p is always prime in my case)

So by the above approach i get numberator as 0 and both the denominators as 0.

However the correct answer is 2. If i use extended euclidean method to solve above problem i get answers i.e 0,1 and 2. However if you do the calculation by hand, the correct answer comes out to be 2.


By the way, what is the method used to calculate (a/b) mod p ???
Is extended euclidean method used to calculate (a/b) mod p ????

Regards
lali