090-数论-长整型模乘

核心概述

长整型模乘（64 位安全模乘）：避免 64 位乘法溢出地计算 (a·b) mod m。常用方案：__int128 直接取模、Barrett 降余、Montgomery 乘法；为 087-数论-米勒拉宾、084-数论-因数分解 等提供基础运算。

原文引述

Description: Safe 64-bit modular multiplication. Prefer builtin 128-bit (if available), else use Barrett reduction or Montgomery multiplication for many products with fixed modulus. Time: O(1) per multiply (amortized); Montgomery/Barrett have small constant factors Status: tested

展开阐述

• 函数/接口（据实现）

  • u64 mulMod128(u64 a, u64 b, u64 m)：使用内建 __int128 计算 ((u128)a*b)%m。
  • struct Barrett { u64 m; u128 im; u64 reduce(u128 x); u64 mul(u64 a,u64 b); }：预计算 im ≈ ⌊2^128/m⌋。
  • struct Montgomery { u64 N, nInv; u128 R2; u64 red(u128 x); u64 mul(u64 aR, u64 bR); u64 toMont(u64 x); u64 fromMont(u64 xR); }（N 为奇数）。

• 核心方法

  • 128 位取模（推荐，平台支持时）
    • 返回 (u64)((__int128)a * b % m)；在 GCC/Clang/ICC 上可用，Windows MSVC 可用内建 128（或用内联汇编/内建库替代）。
    • 常数最小，适合通用 64 位 m。
  • Barrett 降余（通用，不依赖 128 乘法指令集以外特性）
    • 预处理 im = ⌊2^k / m⌋（k=128）。对 x∈[0, 2^128)：
      • q ≈ ⌊(x·im) / 2^k⌋，r = x − q·m；若 r ≥ m 则减 m（再减一次以保正确）。
    • 乘法时先做 x = (u128)a*b，再 reduce(x)。适合固定 m 多次调用，初始化 O(1)。
  • Montgomery 乘法（固定奇模，大量乘法）
    • 选择 R = 2^64，预计算 nInv ≡ −N^{-1} (mod R) 与 R2 ≡ R^2 mod N。
    • REDC：t = (x + ((u64)x * nInv)·N) >> 64；若 t ≥ N 则减 N，返回 t。
    • toMont(x) = REDC(x·R2)，mul(aR,bR)=REDC((u128)aR*bR)，fromMont(xR)=REDC(xR)。
    • 仅适用于奇数 N；多次乘法/幂时效果最佳（如 091-数论-模幂）。
  • 退而求其次：二进制乘（加倍法）
    • 反复 (res += a) 与 a<⇐1 取模，遍历 b 的比特；O(log m) 较慢，仅作兜底。

• 输出与语义

  • 所有接口返回 (a·b) mod m（或其 Montgomery 表示下的等价值）。
  • 要求将 a、b 先规约到 [0,m)；m>0。

• 复杂度

  • 128 位乘法：单次 O(1)。
  • Barrett：单次 O(1)，初始化 O(1)；常数略大。
  • Montgomery：单次 O(1)，初始化 O(1)；批量乘法/幂最优。

• 使用与注意

  • 确保使用无符号类型，避免 UB；中间计算用 __int128/u128。
  • Montgomery 仅适合奇模；若 m 为偶数请选择 128 位或 Barrett。
  • 对 128 位中间值的右移/乘加需小心写法，避免被编译器降宽。
  • 与 091-数论-模幂 联合使用以实现快速 powmod；与 087-数论-米勒拉宾、084-数论-因数分解 搭配用于大数判素/分解。
  • 批量固定模并且需要常数最小时，优先 Montgomery；跨不同模或少量运算时，优先 __int128 或 Barrett。

关联节点

• 091-数论-模幂
• 087-数论-米勒拉宾
• 084-数论-因数分解
• 088-数论-模逆