Is it possible to compute $\sum_{x=1}^K \binom{N}{x}$ $\text{mod }p$ in better than $O(K^2\log p)$

Question

We can compute $\binom{N}{x}$ mod ${p}$ by Fermat's little theorem in $O(x\log p)$.

So if we do same for all $x=1$ to $K$ then,

$$\sum_{x=1}^K \binom{N}{x}\text{ mod }p$$

would take $O(K^2\log p)$.

I suspect using FFT or similar techniquies we might be able to do it faster.

Note I don't need to sum till $N$, I need to sum till $K$, where $K \le N$ and $p$ is a prime.

Answer 1

Let me expand my comment. We run the following pseudocode:

let $B = 1$;
let $S = 0$;
for $i$ in $\{1, \ldots, K\}$:
$\qquad$ $B = B \cdot (N + 1 - i) \cdot i^{-1} \pmod{p}$;
$\qquad$ $S = S + B \pmod{p}$;
return $S$;

What the above algorithm do is to compute the following recursive formula modulo $p$:

\begin{align*} B_0 &= {\textstyle \binom{N}{0}} = 1, & B_i &= B_{i-1} (N+1 - i)i^{-1}, \\ S_0 &= 0, & S_i &= S_{i-1} + B_i. \end{align*}

Then it is easy to check that $B_i = \binom{N}{i}$ for all $i$ and $S_i = \sum_{j=1}^{i} B_j = \sum_{j=1}^{i} \binom{N}{j}$. This means that the above algorithm returns the value of $\sum_{i=1}^{K} \binom{N}{i} \pmod{p}$.

Moreover, each step in the loop takes $\mathcal{O}(\log p)$, with the most expensive one being the computation of $i^{-1}$ modulo $p$. Hence, the entire loop takes $\mathcal{O}(K\log p)$.