4
$\begingroup$

While procrastinating, I decided to play around with computing binomial symbols modulo $m$, $\binom{n}{r} \equiv q \pmod{m}, 0 \leq q < m.$ Using Pascal's formula, I discovered that this may be done with matrix multiplication as follows. Let $N_{r}$ be the $(r+1)$ by $(r+1)$ matrix $N_r = [a_{ij}] = \begin{pmatrix} {1}&{1}&{0}&{0}&{0}&{\dots}\\{0}&{1}&{1}&{0}&{0}&{ }\\{0}&{0}&{1}&{1}&{0}&{ }\\{0}&{0}&{0}&{1}&{1}&{\dots}\\{0}&{0}&{0}&{0}&{1}&{ }\\{\vdots}&{ }&{ }&{\vdots}&{ }&{\ddots}\\ \end{pmatrix}.$ Let $N_r^n = [b_{ij}]$. Then $\binom{n}{r} = b_{1(r+1)}$. Obtain $N_r^n \pmod{m}$ using repeated squaring with the binary representation of $n$, and hence $q$. The complexity seems to be $O ((r+1)^3 \log_2(n))$, not amazing compared with just computing $\frac{n (n-1) \dots (n-r+1)}{r(r-1) \dots 1}$. Of course there will be almost identical rows of $N_r^k$ which may be exploited in computing $q$ in this way so being clever might reduce the complexity to $O ((r+1)^2 \log_2(n))$.

Question: Can this algorithm for computing $q$ be improved? If this has been done, what is a reference?

1 Answers 1

2

When $m$ is prime the answer is given by Lucas' theorem. The problem reduces to computing the digits of $n$ and $r$ in base $p$ which can be done in time $O(\log n)$ (there is also a constant here depending on $m$).

The general problem reduces to the case that $m$ is a prime power by the Chinese remainder theorem. The answer in this case is apparently known but I'm not familiar with it; see this paper / website by Granville.

  • 0
    Thanks Qiaochu! Most of the amusement for me is to compute $\binom{n}{r} \pmod{p_1 p_2}$, where $p_1$ and $p_2$ are distinct primes. A while ago, I thought about factorization using $\binom{n}{r} \pmod{p_1 p_2}$, http://arxiv.org/abs/1107.5709v1 again just playing around.2012-09-28