Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|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 at 22:20

1 Answer 1

up vote 3 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|improve this answer
    
Thanks. Is there another efficient method if the factorization of the modulus is not initially known? –  Ari Jul 21 at 17:53
    
Nothing that I'm aware of. –  Yuval Filmus Jul 21 at 18:38

Your Answer

 
discard

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.