A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two

I present a new algorithm for computing binomial coefficients modulo 2(N). The proposed method has an O(N (3) · Multiplication(N) + N (4)) preprocessing time, after which a binomial coefficient C(P, Q) with 0 ≤ Q ≤ P ≤ 2(N) − 1 can be computed modulo 2(N) in O(N (2) · log(N) · Multiplication(N)) time. Multiplication(N) denotes the time complexity of multiplying two N-bit numbers, which can range from O(N (2)) to O(N · log(N) · log(log(N))) or better. Thus, the overall time complexity for evaluating M binomial coefficients C(P, Q) modulo 2(N) with 0 ≤ Q ≤ P ≤ 2(N) − 1 is O((N (3) + M · N (2) · log(N)) · Multiplication(N) + N (4)). After preprocessing, we can actually compute binomial coefficients modulo any 2(R) with R ≤ N. For larger values of P and Q, variations of Lucas' theorem must be used first in order to reduce the computation to the evaluation of multiple (O(log⁡(P))) binomial coefficients C(P′, Q′) (or restricted types of factorials P′!) modulo 2(N) with 0 ≤ Q′ ≤ P′ ≤ 2(N) − 1.