如何在Rust中优雅实现无溢出的u64/u128类型模乘运算

好问题！在Rust里处理u64/u128类型的(a * b) % m运算，既要避免溢出，又不想依赖BigUInt或无人维护的第三方crate，确实有简洁高效的方案，分两种场景来看：

针对u64类型的极简实现 #

对于u64来说，我们可以利用Rust原生支持的u128类型作为中间载体——因为两个u64的乘积最大值是(2^64 - 1)^2 = 2^128 - 2^65 + 1，刚好能被u128完全容纳，不会产生溢出。这种方法代码简洁、性能拉满，完全符合你想要的“优雅”：

fn mul_mod_u64(a: u64, b: u64, m: u64) -> u64 {
    // 先对a和b取模，减少后续乘法的数值大小
    let a_mod = a % m;
    let b_mod = b % m;
    // 转换为u128计算乘积后取模，再转回u64
    ((a_mod as u128) * (b_mod as u128) % m as u128) as u64
}

这个实现完全不需要额外依赖，利用原生类型的特性就解决了溢出问题，而且现代CPU对u128的运算有原生支持，性能几乎和普通u64乘法无异。

针对u128类型的无溢出实现 #

如果是u128类型，我们没有更大的原生无符号整数类型可用，这时候可以用二进制分解法（也叫“俄罗斯农民乘法”的变种）来逐步计算模乘，全程避免溢出：

fn mul_mod_u128(mut a: u128, mut b: u128, m: u128) -> u128 {
    // 提前取模，缩小计算范围
    a %= m;
    b %= m;
    
    let mut result = 0;
    while b > 0 {
        // 如果当前b的最低位是1，将a加到结果中并取模
        if b & 1 == 1 {
            result = (result + a) % m;
        }
        // 将a翻倍并取模，b右移一位（相当于除以2）
        a = (a << 1) % m;
        b >>= 1;
    }
    result
}

这个方法的核心是把乘法拆解成一系列加法和移位操作，每一步都对模数取模，确保不会超过u128的范围。如果你的场景需要高频执行模乘，还可以进一步优化为Montgomery乘法——不过这种方法需要预处理模数，适合多次使用同一模数的场景，普通场景下二进制分解法已经足够简洁高效。

额外补充：利用标准库的溢出检查工具 #

如果你想更严谨地处理溢出场景（比如debug模式下触发 panic），还可以结合Rust标准库的checked_mul和checked_add方法来实现，但对于模乘场景来说，上面两种方法已经足够实用。

内容的提问来源于stack exchange，提问作者Jakob E.