A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two

摘要

I present a new algorithm for computing binomial coefficients modulo2N. The proposed method has anO(N3·Multiplication(N)+N4)preprocessing time, after which a binomial coefficientC(P,Q)with0≤Q≤P≤2N-1can be computed modulo2NinO(N2·log(N)·Multiplication(N))time.Multiplication(N)denotes the time complexity of multiplying twoN-bit numbers, which can range fromO(N2)toO(N·log(N)·log(log(N)))or better. Thus, the overall time complexity for evaluatingMbinomial coefficientsC(P,Q)modulo2Nwith0≤Q≤P≤2N-1isO((N3+M·N2·log(N))·Multiplication(N)+N4). After preprocessing, we can actually compute binomial coefficients modulo any2RwithR≤N. For larger values ofPandQ, variations of Lucas’ theorem must be used first in order to reduce the computation to the evaluation of multipleOlogPbinomial coefficientsC(P′,Q′)(or restricted types of factorialsP′!) modulo2Nwith0≤Q′≤P′≤2N-1.