Computing n choose k modulo composite m

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
[Iasi] georgepopoiu
New poster
Posts: 3
Joined: Thu Aug 07, 2014 12:47 pm

Computing n choose k modulo composite m

Post by [Iasi] georgepopoiu » Sun Nov 09, 2014 4:12 pm

Hello, I am trying to compute C(n, k) = n! / ( (n - k)! * k! ) mod m without using the recurrence relation C(n, k) = C(n - 1, k) + C(n-1, k-1).

m might be a composite number and we might have n >= m. I know how to do it mod p where p is prime and we have n < p, but in my case the modulus is composite and n can also be larger than the modulus... I have found some information on the web, but nothing explained clearly.

Can someone help me ?

Thanks in advance !

lsonrdrt
New poster
Posts: 2
Joined: Thu Aug 04, 2016 10:45 am

Re: Computing n choose k modulo composite m

Post by lsonrdrt » Thu Aug 04, 2016 11:18 am

GREAT POST

Post Reply

Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest