Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Do you know the factorization of the modulus? Please edit the question to specify, as that makes a tremendous difference to the best answer. – D.W. Jul 21 '14 at 22:20
up vote 4 down vote accepted

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.

share|cite|improve this answer
Thanks. Is there another efficient method if the factorization of the modulus is not initially known? – Ari Jul 21 '14 at 17:53
Nothing that I'm aware of. – Yuval Filmus Jul 21 '14 at 18:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.