I present a new algorithm for computing binomial coefficients modulo 2N. 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 ≤ 2N − 1 can be computed modulo 2N 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(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 (O(log(P))) binomial coefficients C(P′, Q′) (or restricted types of factorials P′!) modulo 2N with 0 ≤ Q′ ≤ P′ ≤ 2N − 1.
展开▼
机译：我提出了一种计算二项式系数模块2 N 的新算法。所提出的方法具有O（N 3 ·乘积（N）+ N 4 ）预处理时间，此后的二项式系数C（P，Q）为0≤Q ≤P≤2 N -1可在O中计算模块2 N （N 2 ·log（N）·乘法（N））球队。乘法（ N ）表示将两个 N 位数字相乘的时间复杂度，范围为 O （ N > 2 ）到 O （ N ·log（ N ）·log（log（ N < / em>）））或更好。因此，用于评估 M 二项式系数 C （ P ， Q ）模块2 的总体时间复杂度 N 且0≤ Q ≤ P ≤2 N - 1是 O （（（ N 3 + M · N 2 ·log（ N ））·乘法（ N ）+ N 4 ）。经过预处理，我们实际上可以计算任意两个 R ≤ N 的二项式系数模块。对于 P 和 Q 的较大值，必须首先使用Lucas定理的变体，以便将计算减少到对（ O （log （ P ）））二项式系数 C （ P ′， Q ）（或阶乘 P ′！的受限类型！）模块2 N 且0≤ Q ′ ≤ P '≤2 N -1。
展开▼
