A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two

Abstract

I present a new algorithm for computing binomial coefficients modulo . The proposed method has an preprocessing time, after which a binomial coefficient with can be computed modulo in time. denotes the time complexity of multiplying two -bit numbers, which can range from to or better. Thus, the overall time complexity for evaluating binomial coefficients modulo with is . After preprocessing, we can actually compute binomial coefficients modulo any with . For larger values of and , variations of Lucas’ theorem must be used first in order to reduce the computation to the evaluation of multiple binomial coefficients (or restricted types of factorials ) modulo with .