Paper 2026/2111

Computing C(N, R) mod m for Arbitrary Composite Moduli and N <= 10^18: A Prime-Power Decomposition Engine with Two Memory Regimes and Division-Free Arithmetic

Abstract

Binomial coefficients modulo an integer, $\binom{N}{R} \pmod m$, are a primitive of combinatorial counting, yet the two textbook methods collapse at scale: the Pascal recurrence costs $\Theta(NR)$ time, and the factorial-table method costs $\Theta(N)$ memory, requires a prime modulus, and requires $N < m$. Composite moduli are harder still, because factorials are not invertible modulo prime powers and the exact power of $p$ dividing the coefficient must be tracked. We present a complete, provably correct engine for arbitrary $m < 2^{62}$ and $N < 2^{64}$. Methodology. The modulus is factored as $m = \prod p_i^{k_i}$ by trial division, deterministic Miller-Rabin, and Pollard-Brent rho. For each prime power we prove and implement the decomposition $\binom{N}{R} \equiv p^e F_p(N) F_p(R)^{-1} F_p(N-R)^{-1} \pmod{p^k}$, where $F_p$ is the $p$-free part of the factorial and $e$ is Kummer's carry count; the same count yields an $O(\log_p N)$ short-circuit that decides $p^k \mid \binom{N}{R}$ before any multiplication. A periodicity lemma derived from Gauss's generalization of Wilson's theorem compresses the state of Pascal's triangle modulo $p^k$ to $p^k$ prefix products, giving two regimes with proven bounds: a table regime answering queries in $O(\log_p N)$ multiplications after $O(\min(p^k, N_{\max}))$ preprocessing, and a direct regime costing $O(R + \log_p N)$ multiplications for $R < p^k$ with $O(1)$ memory. Residues are recombined by the Chinese Remainder Theorem. The hot loops are division-free: Montgomery arithmetic exploits an incremental-form identity so that every unit costs one multiply and one add, and moduli $2^k$ reduce by a bit-mask. Four modular-inverse strategies are compared, including Fermat-Hensel lifting and an inverse-prefix table built with a single inversion. Validation. 3,139,684 oracle checks against Pascal's triangle, Lucas' theorem, Gauss's theorem, and literature constants, plus 3,004 exact big-integer comparisons, passed with zero failures; all 101 benchmark checksums are bit-identical across a Windows GCC 16 12th-gen Intel laptop and a Linux GCC 11 Xeon server. Results. At $N \approx 10^{18}$ a query costs 1.4 to 6.9 microseconds for composite moduli and scales linearly in $\log N$ at 15 to 36 ns per base-$p$ digit. For prime moduli the table regime answers queries in 0.09 to 0.27 microseconds independently of $p$, and building the table costs 0.36 to 0.85 of a single worst-case direct query, so it pays for itself immediately. Montgomery arithmetic is 2.0 to 3.1 times faster than 128-bit modulo and bit-masking up to 6.7 times; Fermat-Hensel inversion is 16 to 20 times faster than the extended Euclidean algorithm at $2^{40}$ and 1.4 to 2.0 times faster for large odd prime powers. Against the Pascal recurrence the engine is already 7,100 to 12,800 times faster at $N = 4 \times 10^4$; at $N = 10^9$ the recurrence would need 4.6 to 5.8 CPU-years and a 4 GB row, whereas the engine answers in about 2 microseconds from a 244-byte table. With uniformly random $R$, the Kummer short-circuit resolves 95% to 99.998% of prime-power solves in $O(\log N)$ time, a rate predicted exactly by Fine's theorem. We also report the honest wall: for a prime $p \approx 10^9$ with $R \approx N/2$ no table fits in memory and a query costs 3.4 to 4.5 seconds—the intrinsic $\Theta(p^k)$ bound that only sub-linear factorial algorithms could remove.