A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two

Abstract EN

I present a new algorithm for computing binomial coefficients modulo 2N.

The proposed method has an O(N3·Multiplication(N)+N4) preprocessing time, after which a binomial coefficient C(P,Q) with 0≤Q≤P≤2N-1 can be computed modulo 2N in O(N2·log(N)·Multiplication(N)) time.

Multiplication(N) denotes the time complexity of multiplying two N-bit numbers, which can range from O(N2) to O(N·log(N)·log(log(N))) or better.

Thus, the overall time complexity for evaluating M binomial coefficients C(P,Q) modulo 2N with 0≤Q≤P≤2N-1 is O((N3+M·N2·log(N))·Multiplication(N)+N4).

After preprocessing, we can actually compute binomial coefficients modulo any 2R 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 OlogP binomial coefficients C(P′,Q′) (or restricted types of factorials P′!) modulo 2N with 0≤Q′≤P′≤2N-1.