Does anyone know of a fast algorithm to compute factorials and/or binomial coefficients in general or modulo a composite number in particular (for composite moduli I am interested in the case where the factorization is not necessarily known) I know that for primes and factorials we can apply Wilson's Theorem but I was wondering if there is also a fast method for composite numbers. For binomial coefficients I was thinking of using recursion and the addition rule: $$\binom{n}{x} + \binom{n}{x+1} = \binom{n+1}{x+1}$$ somehow but I'm not sure really how to go about it. Any suggessions? Thanks.
1
-
$\begingroup$ Do you know the factorization of the modulus? Please edit the question to specify, as that makes a tremendous difference to the best answer. $\endgroup$– D.W. ♦Jul 21, 2014 at 22:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
If $p$ is prime and $n = n_\ell \ldots n_0$, $x = x_\ell \ldots x_0$ in base $p$, then (Lucas' theorem) $$ \binom{n}{x} \equiv \binom{n_\ell}{x_\ell} \cdots \binom{n_0}{x_0} \pmod{p}. $$
For a product of distinct primes, you can apply the Chinese remainder theorem. So it remains to deal with prime powers. Such a method is described in this paper of Andrew Granville, though it's not as nice as the formula above.
answered Jul 21, 2014 at 17:31
-
$\begingroup$ Thanks. Is there another efficient method if the factorization of the modulus is not initially known? $\endgroup$– AriJul 21, 2014 at 17:53
-
-
$\begingroup$ I implemented Andrew Granville's algorithm here : github.com/elaqqad/HackerRank/blob/master/… $\endgroup$– ElaqqadDec 20, 2016 at 8:33